12
$\begingroup$

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?

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What if $m=1$? What if $2$ divides $1+a_0+a_1m+\ldots+a_km^k$? $\endgroup$ – Batominovski Aug 27 '17 at 18:20
  • $\begingroup$ 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. $\endgroup$ – Rishabh Jain Aug 28 '17 at 18:49
-3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Someone help me why are people downvoting my post? $\endgroup$ – user160110 Aug 27 '17 at 18:12
  • 5
    $\begingroup$ 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$. $\endgroup$ – Batominovski Aug 27 '17 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.