Classical indeed. I claim $f(n)=n$ for all $n$. Denote by $P(a,b)$ the given assertion. $P(1,1)$ yields $f(1)\mid 2$. Case 1: $f(1)=1$. Let $p$ be a prime. Then $P(1,p-1)$ yields $f(p-1)+1\mid p^2$. Thus, $f(p-1)\in\{p-1,p^2-1\}$. Assume first that $f(p-1)=p-1$ infinitely often. Then, $P(p-1,n)$ yields $p-1+f(n)\mid (p-1+n)^2\iff p-1+f(n)\mid (n-f(n))^2$. Sending $p\to\infty$, we recover $f(n)=n$. Now, suppose there is an $N$ such that for all $p\ge N$ prime, $f(p-1)=p^2-1$. Take $p,q>N$ and inspect $P(p-1,q-1)$ to get $p^2+q^2-2\mid (p+q-2)^2$. This implies \[ p^2+q^2-2\mid p^2+q^2+4-4p-4q+2pq\iff p^2+q^2-2\mid 2pq-4p-4q+6. \]This, however, is clearly false by size considerations. Case 2: $f(1)=2$. Once again, $P(p-1,1)$ for $p$ prime yields $f(p-1)+2\mid p^2$, that is $f(p-1)\in\{p-2,p^2-2\}$ for every prime $p$. Assume again $f(p-1)=p-2$ infinitely often. Taking such $p,q$ and looking at $P(p-1,q-1)$ we get $p+q-4\mid (p+q-2)^2$. As $p+q\equiv 4\pmod{p+q-4}$, we get $p+q-4\mid 4$, a clear contradiction. The second case is handled exactly the same way as above.

Indeed, quite classical; the idea from IMO 2010/3 works here as well (hence this is a bit different from the above solution). The answer is $f(n)=n$. Firstly, $f$ is injective, otherwise $f(a)=f(b)$ and plugging $(n, a)$, $(n, b)$ for $n$ such that $(a+n, b+n)=1$ gives contradiction. Now we aim to prove that for all $a$, $|f(a+1)-f(a)|=1$ (after proving this, the difference will be always $1$ and the function is linear). Suppose that a prime $p$ divides $f(a+1)-f(a)$. Plugging $(n, a), (n, a+1)$ gives that $(f(n)+f(a), f(n)+f(a+1))=1 \iff (f(n)+f(a), f(a+1)-f(a))=1$. We will find $n$ which forces $p \mid f(n)+f(a)$, which will be a contradiction. Indeed, just take $n=p^k-a$, which will force $f(n)+f(a)=1$, impossible. Now let $f(n)=n+c$ and plug $(1, p-1)$ to get $p+2c \mid p^2$, which is impossible unless $c=0$ and we are done (otherwise $p+2c=p^2$, but this isn't possible for large enough $p$).

The only solution is $\boxed{f(n) = n}$, which works. Let $P(a,b)$ denote the given assertion. $P(a,a): f(a)\mid 2a^2$. In fact, this implies $f(1)\in \{1,2\}$. For any prime $p$, $P(p-1,1): f(p-1) + f(1)\in \{p,p^2\}$. If $f(p-1) = p^2 - f(1) $ for some large prime $p$, we get $p^2 - f(1) \mid 2(p-1)^2$. However, $p^2 - f(1)> \frac{2(p-1)^2}{2}$, so we must have $p^2 - f(1) = 2(p-1)^2$, which is not true for large $p$. Thus, we get $f(p-1) = p-f(1)$ for all sufficiently large primes $p$. Note that if $f(1) = 2$, then we have $x-1\mid 2x^2$ for some large $x$, which is not possible as $x-1$ and $2x^2$ are coprime. Thus $f(1) = 1$. Let $M$ be set as a sufficiently large fixed point of $f$ (which we know exists). $P(M,n): f(n) + M \mid n^2+ 2Mn + M^2$. So $f(n)+M$ divides \[n^2 + 2Mn + M^2 + (f(n) + M)(f(n) - M - 2n) = (n-f(n))^2\] Since $M$ is sufficiently large, we get $(n-f(n))^2 = 0$, so $f(n) = n$, as desired.

Stronger problem !! : https://artofproblemsolving.com/community/c6h213442p1178417

there is a prime number between n and 2n........