# 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$

Let $N$ be the set of natural number. Find all functions $f: \mathbb N \to \mathbb N$ , such that the number $(m+f(n))(n+f(m))$ is perfect square for all natural numbers $m$ and $n$.

I was unable to solve this problem so I need a solution to it, I know that the condition that $(m+f(n))(n+f(m))$ is a perfect square would imply that if $n = m$ then $f(n) = f(m)$ but how would that help me in solving the problem?

• If $n=m$, then $f(n)=f(m)$ anyway because $f$ is a function... – Michael L. Aug 26 '17 at 22:04
• @Michael Lee, Thanks but how to solve the problem? – Icosahedron Aug 26 '17 at 22:19
• $f(p)=p$ is a solution. – N74 Aug 26 '17 at 22:25
• @N74 So is $p+c$ with $c$ constant, but even that might not be the most general solution. – J.G. Aug 26 '17 at 22:35
• This is problem #3 from IMO 2010. See here. – shrimpabcdefg Aug 27 '17 at 6:34

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$$.

here is my proof. first let $$T(m,n)=(f(m)+n)(f(n)+m)$$ we porve if $$p|f(m)-f(n)$$ then $$p|m-n$$ to do so assume : $$(f(m)+t)(f(t)+m)=g(t,m)^2$$ first assume $$V_p(f(m)-f(n))>1$$ now let $$t=q^{f(m)+f(n)}p-f(n)$$ where $$q$$ is a prime other than $$p$$ so we have $$p|f(m)-f(n)+q^{f(m)+f(n)}p$$ but we dont have $$p^2|f(m)-f(n)+q^{f(m)+f(n)}p$$ so we must have $$p|f(q^{f(m)+f(n)}p)+m$$ now look at $$T(q^{f(m)+f(n)}p-f(n),f(n)$$ this gives again $$p|f(q^{f(m)+f(n)}p-f(n))+n$$ taking the difference gives $$p|m-n$$. so this is done now if $$V_p(f(m)-f(n))=1$$ checking $$T(p^{f(m)+f(n)}-f(n),m)$$ gives $$p|f(p^{f(m)+f(n)}-f(n))+m$$ and from $$T(p^{f(m)+f(n)}-f(n),n)$$ we get $$p|f(p^{f(m)+f(n)}-f(n))+n$$ so again taking the difference gives $$p|n-m$$ this means there is no prime such that $$p|f(n+1)-f(n)$$ so we must have $$(f(n+1)-f(n))^2=1$$ now we prove the fucntion is injective. assume $$f(a)=f(b)$$ we have from $$T(a,m)T(b,m)=(f(a)+m)^2(f(m)+a)(f(m)+b)$$ is a perfect square then so is : $$(f(m)+a)(f(m)+b)$$ now if we prove $$f$$ is not bounded we are done. since a polynomial of second degree can not be infinitly many times an square unless the polynomial has $$2$$ equal roots. which in our case they are assumed to be different . for proving that $$f$$ is unbounded simply look at $$T(p-f(1),1)$$ where $$p$$ is a prime greater than $$f(1)$$ so we have $$p(f(p-f(1))+1)$$ is a perfect square so $$p|f(p-f(1))+1$$ so we must have $$f(p-f(1)) \ge p-1$$ now taking $$p$$ big enough we are done. ass the function is injective we must always have $$f(n)+1=f(n+1)$$ which gives the answer $$f(n)=n+c$$ for some constant positive natural $$c$$ and all these functions work

In this question, you can prove that the function is not a polynomial. Let's say that $g(x)=a_0+a_1x+a_2x^2+....+a_kx^k$. Now, let us choose n=1 and $m=a_0+a_1+a_2+....+a_k$. Now, your expression becomes $(m+a_0+a_1+.....a_k)*(1+a_0+a_1m+a_2m^2+....+a_km^k)=(m+m)*(1+a_0+a_1m+a_2m^2+....+a_km^k)$.

Now, this expression is a perfect square. So, either m is itself a perfect square or the number in the second bracket is divisible by m. Let's suppose that m is not a perfect square. It would mean that $a_0+1$ is divisible by m .This would imply that $a_0+1>=m$. Substituting the value of m , you would get $a_1+a_2+....a_k<=1$. Now, it's simple to prove that either $a_1=1$ or all are zero. If any other coefficient was 1, then you can choose n=1 and easily see that the expression won't form a perfect square for every m by using the identity $m^k+1^k=(m+1)*(....)$.

Now, suppose m is a perfect square.But you could also take m as being $(a_0+a_1+a_2+....+a_k)^2$ which would have given you that the second bracket is divisible by either $(a_0+a_1+a_2+....+a_k)$ or $(a_0+a_1+a_2+....+a_k+1)=t(let's\ say)$ as both cannot be perfect squares. Now, t is not a perfect square. The second bracket dividing $t$ would imply that $1+a_0-a_1-a_2-....-a_k \equiv 0(mod(t))$. After simplifying using the expression of t, you will get $2*(1+a_0)\equiv 0(mod\ t)$.The rest of the proof follows from above.

• What if $m=1$? What if $2$ divides $1+a_0+a_1m+\ldots+a_km^k$? – Batominovski Aug 27 '17 at 18:20
• Are you taking m and n both to be 1? I have chosen a specific expression for m which will be an integer, thus, should satisfy the above property. – Rishabh Jain Aug 28 '17 at 18:49

There are only two ways that $(n+f(m))(m+f(n))$ can be a perfect square.

1. $(n+f(m))$, $(m+f(n))$ are perfect squares for every natural number $n,m$.

2. $(n+f(m))=A=(m+f(n))$ in which case $(n+f(n))(m+f(n))=A^2$

The first way cannot happen, because if $(n+f(m))$ is a perfect square $$((n+1)+f(m))=(n+f(m))+1$$ isn't. You cannot add one to a perfect square and get another perfect square here is a list to convince you:

$$1,4,9,16,25,36,49,...$$

So the only way $(n+f(m))(m+f(n))$ is a perfect number is if$$n+f(m)=m+f(n)$$ Set $m=n-1$ then we get

$$n+f(n-1)=(n-1)+f(n)$$

solving for $f(n)$ gives us $$f(n)=f(n-1)+1$$ Notice that

$$f(n)=f(n-1)+1=f(n-2)+2=...=f(1)+(n-1)$$

What this means is given any natural number $c$. $$f(n)=c+(n-1)$$ is a solution. Here is a check:

$$(m+f(n))(n+f(m))=(m+[c+(n-1)])(n+[c+(m-1)])=(m+n+c-1)^2$$

• Someone help me why are people downvoting my post? – user160110 Aug 27 '17 at 18:12
• If the products of two positive integers $a$ and $b$ is a square, it does not follow that $a=b$ or that $a$ and $b$ are perfect squares. An counterexample is $a=2$ and $b=18$. – Batominovski Aug 27 '17 at 18:19