Find all the functions $f: \mathbb{N} \to \mathbb{N} $ such that $(m+f(n))(n+f(m))$ is a perfect square for all $m,n$

When we have two numbers $a, b$ whose product is a perfect square, we can trace two observations on them:

Obs. 1: If $a$ is a square then $b$ is a square too.

Obs. 2: If $p$ is a prime and $p^k||a$ (short for "$p^k|a$ but $p^{k+1}\not|a$") and $p^l||b$, then $k+l$ is even; in particular, if $k$ is odd, then $l$ is odd (and it implies an obvious but useful thing: odd numbers can't be zero).

Obviously, constant functions aren't solutions for our problem. And by simple verification $f(x)=x+C$ with C natural works. We want to show there are no others.

Lemma 1: for every prime $p$ and integers $a,b$ such that $p|a-b$, there exists a constant $k$ such that there are odd numbers $\alpha, \beta$ such that $p^\alpha||a+k$ and $p^\beta||b+k$.

Proof:

Let $z$ the smallest natural number such that $p|a+z$. Obviously, $p|b+z$ too. Now some case-by-case analysis:

• $p^2|a+z$ and $p^2|b+z$. That way, $a+z+p \equiv p \not\equiv 0 \pmod{p^2}$ but $a+z+p \equiv 0 \pmod{p}$, and we can choose $k=z+p$, and $\alpha=1,\beta=1$.

• $p^2 \not |a+z$. More cases!

  • $p^2 \not| b+z$. Well, just add $p^3$ to both! It will give us $\alpha=1,\beta=1$.
  • $p^3 \not| b+z$. Now we can choose $k=C \cdot p^3-b-z$ with $C$ a very large non-multiple of $p$ (in order to $k>0$). That way, we have $a+z+k=Cp^3+a+z$ is multiple of $p$ but not $p^2$, and $b+z+k=Cp^3$ multiple of $p^3$ but not $p^4$. That way we can take $\alpha=1, \beta=3$.
  • $p^4 \not| b+z$. Just add $p^5$, it will give us $\alpha=1, \beta=3$.
  • $p^4 | b+z$. Just add $p^3$, it will give us $\alpha=1, \beta=3$.

Now we need to show that $f(n+1)-f(n)=1$ for any $n$.

If there was a prime $p$ such that $p|f(n+1)-f(n)$, then by the Lemma abiove we can choose $k$ such that $p^\alpha||k+f(n+1)$ and $p^\beta||k+f(n)$ with $\alpha, \beta$ odd.

But $(k+f(n+1)) \cdot (f(k)+n+1)$ is a perfect square. By the Obs. 2, $p|(f(k)+n+1)$. The same way, $p|(f(k)+n)$ too, and then $p|1$, contradiction.

Then $p$ does not exist, and so $f(n+1)=f(n)+1$ or $f(n+1)=f(n)-1$

If there was an $N$ such that $f(N+1)=f(N)-1$, then $(N+f(N+1)) \cdot (N+1+f(N)) = (N+f(N)-1) \cdot (N+f(N)+1) = (N+f(N))^2-1$ would be a perfect square, and it can occur if and only if $N+f(N)=0$, or $f(N)=0, N=0$.

Then we can split it in two cases:

• $f(0) = 0$. Then $f(N+1) = f(N)-1$ only if $N=0$. That way, $f(1)=0-1<0$, contradiction.

• $f(0) \not = 0$. Then $f(N+1) \not= f(N)-1$ for every $N$, and then $f(N+1) = f(N)+1$ for every $N$.

Problem solved! By naive induction, $f(n)=n+C$ with $C=f(1)-1$.