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$

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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