My solution:

Attachments:

Let $P(x,y)$ be assertion given. i) $f$ is unbounded. Suppose that $f(n) < M$. for sufficiently large prime $p = 2k+1$, $P(k+1,k)$ gives $f(k) + f(k+1) | p$ since $1 < f(k) + f(k+1) < 2M < p$ which is absurd. ii) $f$ is injective suppose that $f(a) = f(b), a>b$. $P(y,a) - P(y,b)$ gives $f(a) + f(y) | a^2 - b^2$, and it is false because $f$ is unbounded iii) $f(n) = n$ for all positive integers $n$. $P(1,2), P(1,3), P(2,3)$ easily gives $f(1)=1$. suppose that $f(i) = i$ for all $i<N$ $P(N,N-1) : f(N) + N-1 | 2N-1, f(N) \leq N$ since $f$ is injective, $f(N) = N$

Darkztar wrote: Let $P(x,y)$ be assertion given. i) $f$ is unbounded. Suppose that $f(n) < M$. for sufficiently large prime $p = 2k+1$, $P(k+1,k)$ gives $f(k) + f(k+1) | p$ since $1 < f(k) + f(k+1) < 2M < p$ which is absurd. ii) $f$ is injective suppose that $f(a) = f(b), a>b$. $P(y,a) - P(y,b)$ gives $f(a) + f(y) | a^2 - b^2$, and it is false because $f$ is unbounded iii) $f(n) = n$ for all positive integers $n$. $P(1,2), P(1,3), P(2,3)$ easily gives $f(1)=1$. suppose that $f(i) = i$ for all $i<N$ $P(N,N-1) : f(N) + N-1 | 2N-1, f(N) \leq N$ since $f$ is injective, $f(N) = N$ I always suppose that $\mathbb{N}$ is set of positive integers unless there is a comment.

$f(1)+f(2)|3 \implies \{f(1),f(2)\}={1,2}$ $i)$ $f(1)=2, f(2)=1 :$ $f(3)+1|5, f(3)+2|8 \implies $ contradiction. $ii)$ $f(1)=1, f(2)=2:$ I will prove that $f(x)=x$ by induction. $f(1)=1$, assume that $f(n)=n$ then $f(n+1)+f(n)|2n+1\implies f(n+1)+n|f(n+1)-(n+1)$. We have $|f(n+1)-(n+1)| \le n$ because of $f(n+1)+f(n)|2n+1$. If $|f(n+1)-(n+1)|\neq 0$ then $f(n+1)+n \le |f(n+1)-(n+1)| \le n$ contradiction. Thus $|f(n+1)-(n+1)|= 0 \implies f(n+1)=n+1$