I don't know if I overcomplicated this problem, but anyway... here is my solution: Let's take some odd prime $p$ such that $p \mid f(a)$. Then we have that $-ab$ is a quadratic residue in $\mathbb{Z}/p\mathbb{Z}$ for all $b \in \mathbb{N}$. Therefore, if $p \nmid a$ we have that $-ab$ generates the complete residue system ${0, 1, ... p-1}$ as we iterate over $b$. But we know that the set formed by the quadratic residues is $0^2, 1^2, ..., (\dfrac{p-1}{2})^2$ so there are exactly $\dfrac{p-1}{2}$ non quadratic residues. Since $p \geq 3$, $\exists c$ in $\mathbb{Z}/p\mathbb{Z}$ which is non quadratic and simply taking $b = -c \cdot a^{-1}$ in $\mathbb{Z}/p\mathbb{Z}$ generates a contradiction. After this, we have our lemma: Quote: If $p \mid f(a)$ where p is an odd prime, then $p \mid a$

What we'll do instead, is to prove that $f(p) = p$ for all primes $p > 2$. In the "Slightly Fake Solution" we showed that $4 \nmid f(x)$ for all odd $x$. Now, using the lemma, we only have to worry about two cases: $\star$ Case 1 $f(p) = 2 \cdot p^m$ where $m$ is non negative. $\centerdot$ If $m \geq 2$ then we have that $f(p)f(p+1) - p$ is a square divisible by p. Therefore, $p^2 \mid f(p)f(p+1) - p$ but since $p^2 \mid f(p)$ we end up with $p \mid 1$ $(\Rightarrow \Leftarrow)$ Now, since $f(p)f(2p) - p^2$ is an odd square, it's congruent to $1$ mod $8$ and also $p^2$ too. Therefore, $f(2p)$ is odd and using the lemma... $\exists k \geq 0$ with $f(2p) = p^k$. $\centerdot$ If $k = 0$, then $f(p) - p^2$ is square which implies that $p^2 \leq f(p) \leq 2p$ $(\Rightarrow \Leftarrow)$ $\centerdot$ If $k \geq 2$, then $f(2p)f(2p+1) - 2p$ is a square divisible by $p$. Therefore $p^2 \mid f(2p)f(2p+1) - 2p$ but since $p^2 \mid f(2p)$ we end up with $p \mid 2$ $(\Rightarrow \Leftarrow)$ So, $k = 1$ and $f(2p) = p$. Then $f(p)f(2p) - p^2 = pf(p) - p^2$ which implies that $p \mid f(p)$ so $m = 1$ and $f(p) = 2p$. Furthermore, $f(p)f(3p) - 2p^2 = 2p(f(3p) - p)$ and $f(p)f(7p) - 6p^2 = 2p(f(7p) - 3p)$ so $f(3p) = p \cdot z_{1}$ and $f(7p) = p \cdot z_{2}$ where $z_{1}$ and $z_{2}$ are odd naturals. Then $f(2p)f(3p) - 2p^2 = p^2(z_{1} - 2)$ and $f(2p)f(7p) - 10p^2 = p^2(z_{2} - 10)$ which implies that $z_{1} - 2$ and $z_{2} - 10$ are odd squares. Thus, they're congruent to $1$ mod $8$ and $z_{1}$, $z_{2}$ are congruent to $3$ mod $8$. Then $f(3p)f(7p) - 12p^2 = p^2(z_{1} \cdot z_{2} - 12)$ which implies that $(z_{1} \cdot z_{2} - 12)$ is an odd square so it's congruent to $1$ mod $8$ but $3 \cdot 3 - 12 \neq 1$ in $\mathbb{Z}/8\mathbb{Z}$ $(\Rightarrow \Leftarrow)$ $\star$ Case 2 $f(p) = p^m$ where $m$ is non negative. Analogously, if $m \geq 2$ then we have that $f(p)f(p+1) - p$ is a square divisible by p. Therefore, $p^2 \mid f(p)f(p+1) - p$ but since $p^2 \mid f(p)$ we end up with $p \mid 1$ $(\Rightarrow \Leftarrow)$ Therefore, we've proven that $f(p)$ is either $1$ or $p$ for all primes $p > 2$. Let's suppose that there exists some prime $r > 2$ with $f(r) = 1$. Chose any prime $s > r^2 > 2$. Then $f(r)f(s) - r(s-r)$ is square so $r(s-r) \leq f(r)f(s) = f(s) \leq s$. Thus, $r^2 \geq s \cdot (r-1) \geq s > r^2$ $(\Rightarrow \Leftarrow)$ Finally, we can say that $f(p) = p$ for all primes $p > 2$. Now, here is the final idea: Final Key Idea wrote: It suffices to show that there exists an infinite sequence of fixed points with respect to the function $f$. Let's say that we have some infinite sequence $y_{n}$ such that $f(y_{n}) = y_{n}$. Now take any natural $x$. Since $y$ is infinite, $\exists z \geq 1$ such that $y_{z} > x^2 > x$. By contradiction, let's say that $f(x) < x$. Hence $f(x) \leq x-1$. Since $f(x)f(y_{z}) - x(y_{z} - x)$ is square, then: $x \cdot (y_{z} - x) \leq f(x)f(y_{z}) \leq (x-1)f(y_{z}) = (x-1) \cdot y_{z}$ which implies that $y_{z} \leq x^2$ $(\Rightarrow \Leftarrow)$ So, if we somehow obtain infinite fixed points, then it's over. And that's it because we already proved that all odd primes are fixed points. Hence, we're done.

As usual, let $P(a,b)$ denote the given assertion. First, suppose there exists a prime $p$ such that $p | f(x)$ but $p \nmid x$. First, $\nu_p(f(x)) = 1$ as otherwise $P(x,p)$ gives that $\nu_p(f(x)f(x+p) - xp) = 1$, and so cannot be a perfect square. Also note that we can get $\nu_p(f(x+p^k)) = 1$ for $k \geqslant 2$ while $\nu_p(f(x+mp)) = 0$ if $p \nmid m$. So there exist arbitrarily large numbers congruent to $x \pmod p$, which have $\nu_p$ both $0$ and $1$, pick $2$ of these that are big enough, say $m,n$. Then consider $P(p,m-p)$ and $P(p,n-p)$ which again gives a $\nu_p$ contradiction. So we have that $p | f(x) \implies p | x$. From $P(q,x-q)$ for some prime $q$ and $q \nmid x$, we have that $f(q) = q$, so there is an infinite set of numbers that $f$ fixes. To finish, take $P(x,q-x)$ to get that $q(f(a) - a) + a^2$ is a perfect square for all big primes $q$. But first pick $q \equiv 1 \pmod a$ to get that $f(a)$ is a QR $\pmod a$, and then pick $q \equiv z \pmod a$ where $z$ is an NQR coprime with $a$ (possible to find when $a \geqslant 3$), so we get that $a | f(a)$, so if $f(a) = (k+1)a$, then we have that $a(a+qk)$ is a perfect square for all primes $q$. There's many ways to finish but here's the funniest I can think of. Since its known that for infinitely many $n$, we have $p_{n+1} - p_n < C$ for some constant $C$, pick these pairs of primes to be $q$, so we get that the difference of infinitely many pairs of squares is at most $Ck$, which is impossible unless $k = 0$, which finishes the problem. $\blacksquare$

This problem was proposed by me, Nuno Arala, from Portugal. In case anyone is interested, I'm leaving the original submission (in broken Spanish) here!

Let $p$ be an odd prime and assume that $\nu_p(f(a))>\nu_p(a)$. Letting $b=1$, it follows that \[2\mid \nu_p(f(a)f(a+1)-a)=\nu_p(a).\]Let $\nu_p(a)=2\alpha$. As $ab+t^2=f(a)f(a+b)$, we have \[\frac{a}{p^{2\alpha}}\cdot b+\left(\frac{t}{p^\alpha}\right)^2=\frac{f(a)}{p^{2\alpha}}\cdot f(a+b),\]the right-hand side being divisible by $p$. Consequently, for all $b$ relatively prime to $p$ we have \[\left(\frac{(a/p^{2\alpha})\cdot b}{p}\right)=\left(\frac{-1}{p}\right).\]This is a contradiction, since $(a/p^{2\alpha})\cdot b$ may be any nonzero residue modulo $p$. Consequently, $\nu_p(f(a))\leqslant\nu_p(a)$. If $p=2$ and $\nu_2(f(a))>\nu_2(a)+1$, then we may choose $b\in\{1,2\}$ accordingly, so that \[\nu_2(f(a)f(a+b)-ab)=\nu_2(ab)\]is odd, giving us a contradiction. So, for $p=2$ we have the weaker bound $\nu_2(f(a))\leqslant\nu_2(a)+1.$ Combining this with the previous estimate, we infer that $f(n)\mid 2n$. Notice that $f(1)\in\{1,2\}$ and $f(2)\in\{1,2,4\}$ and because $f(1)f(2)-1$ is a perfect square, it follows that $f(1)=1$. Therefore, $f(n)\geqslant n-1$ for all $n$ so as $f(n)\mid 2n$, we may infer that $f$ is the identity.

oVlad wrote: […]Notice that $f(1)\in\{1,2\}$ and $f(2)\in\{1,2,4\}$ and because $f(1)f(2)-1$ is a perfect square, it follows that $f(1)=1$. Therefore, $f(n)\geqslant n-1$ for all $n$ so as $f(n)\mid 2n$, we may infer that $f$ is the identity. Everything’s fine up to this point, where (I think) you haven’t ruled out $f(1)=2$, $f(2)=1$ and $f(n)=2n$ in general.

Justpassingby wrote: oVlad wrote: […]Notice that $f(1)\in\{1,2\}$ and $f(2)\in\{1,2,4\}$ and because $f(1)f(2)-1$ is a perfect square, it follows that $f(1)=1$. Therefore, $f(n)\geqslant n-1$ for all $n$ so as $f(n)\mid 2n$, we may infer that $f$ is the identity. Everything’s fine up to this point, where (I think) you haven’t ruled out $f(1)=2$, $f(2)=1$ and $f(n)=2n$ in general. Oh whoops, I forgot to mention what happens in that case. If $f(2)=1$ then let $a=2$ and notice that $f(n+2)-2n$ is always a perfect square. Since $f(n+2)\leqslant 2n+4$ it follows that $f(n+2)-2n\in\{0,1,4\}$ so $f(n+2)\in\{2n,2n+1,2n+4\}$. As $2n$ and $2n+1$ do not divide $2n+4$ for $n\geqslant 3$, it follows that $f(n+2)=2n+4$ for $n\geqslant 3$, or, in other words, $f(k)=2k$ for $k\geqslant 5$. Now we get a contradiction by setting $a=b=5$, for instance.

A step by step solution with elementary steps. Step 1, possible values of $f(1),f(2),f(p),f(2p)$.

Step 2, actual values of $f(1),f(2),f(p),f(2p)$ and lower bound for $f(n)$.

Step 3, $f(4)$.

Step 4, conclusion.

Step 5, verification.

Late-night proof so ditzy a_507_bc wrote: Find all functions $f:\mathbb{N} \rightarrow \mathbb{N}$, such that $f(a)f(a+b)-ab$ is a perfect square for all $a, b \in \mathbb{N}$. Let $p \mid f(n)$ be a prime, then $(-m)n$ is a quadratic residue modulo $p$ for every $m \ge 1$, hence $p \mid n$. So if $q$ is a prime power, then $f(q)$ is a non-negative power of the unique prime factor of $q$. Let $f(p^n)=p^{x_n}$ for $(x_n)_n$ a sequence of non-negative integers. Also, $x_0=0$ as $f(1)=1$. We will show that $x_{2k}=2k$ for all $k \ge 1$. Plug $a=p^n, b=p^{n+1}-p^n$ to get $p^{x_n+x_{n+1}}-p^{2n}(p-1) = g_n^2$ for some integer $g_n \ge 1$. Thus, $x_n+x_{n+1}>2n$ or $x_{n+1} \ge n+1$ and so $g_n=p^nh_n$ for some integer $h_n \ge 1$ and $h_n^2 = p^{x_n+x_{n+1}-2n}-(p-1)=p^{x_{n+1}-n}-p+1$. If $x_{n+1} \equiv n \pmod{2}$ then $h_n^2$ lies between two consecutive squares, so $x_{n+1} \equiv n+1 \pmod{2}$. Plug $a = p^n, b = p^{n+2}-p^n$ to get $p^{x_n+x_{n+2}}-p^{2n}(p^2-1)$ is a square. So $x_n+x_{n+2}>2n+1$ hence $x_{n+2} \ge n+2$ so $p^{x_{n+2}-n}-(p^2-1)$ is a square. If $x_{n+2} \equiv n \pmod{2}$ then either $x_{n+2}=n+2$ or the previous number is sandwiched between two consecutive squares. Thus, either $x_{n+2}=n+2$ or $x_{n+2} \equiv x_{n+1} \pmod{2}$. In the latter case, since $p^{x_{n+1}+x_{n+2}}-p^{2(n+1)}(p-1)$ is a square, so $p^{x_{n+1}+x_{n+2}-2(n+1)}-(p-1)$ is a square, but the exponent is even, so we get a contradiction. So $x_{n+2}=n+2$. So we have shown that $x_n = n \implies x_{n+2}=n+2$ and $x_{n+1} \equiv n+1 \pmod{2}$. Thus, $x_{2k}=2k$ and $x_{2k+1}$ is odd for all $k \ge 0$. Now pick an integer $a \ge 1$ and prime $p>2a$ and let $b=p^{2k}-a$ for some $k \ge 1$. Then, $p^{2k}f(a)-a(p^{2k}-a)=p^{2k}(f(a)-a)+a^2$ is a perfect square, say $y^2$. So $(y-a)(y+a)=p^{2k}(f(a)-a)$. Now, $p \nmid 2a$ so $p \mid y-a$ or $p \mid y+a$, implying $p^{2k}$ divides only one of them, hence $y \ge p^{2k}-a$ so $f(a)-a \ge p^{2k}$ which fails by choosing $p$ sufficiently large (in fact, we only needed $f(p^2)=p^2$ all along). This is absurd unless $y=a$ and $f(a)=a$. So $f$ is the identity function, which works as well. EDIT: to rewrite this in simpler terms, I will just show $f(p^2)=p^2$ and ignore the middle paragraph entirely. Pick $a = 1$ and $b = p-1$ to get $f(p)-(p-1)$ is a square, and pick $a=1, b=p^2-1$ to get $f(p^2)-p^2+1$ is a square. These force $f(p), f(p^2)$ to both be odd powers of $p$ by sandwiching between consecutive squares, or $f(p^2)=p^2$. In the former case, plug $a=p, b=p^2-p$ to get $f(p)f(p^2)-p^2(p-1)$ is a square. Removing the $p^2$ factor, we get $p^{\text{even}}-(p-1)$ is a square, which is impossible. Thus, $f(p^2)=p^2$ is always true.

$p$ denotes a prime. Step 1. If $p^{2\alpha}|f(a)$ then $p^{2\alpha}|a$

Step 2. If $p^{2\alpha+1}|f(a)$ then $p^{2\alpha+1}|f(a)$.

So $v_p(f(a))\le v_p(a)$ i.e. $f(a)|a$. Step 3(easy). $f(n)=n\forall n\in \mathbb{N}$