Suppose that $f : \mathbb{N} \rightarrow \mathbb{N}$ is a function for which the expression $af(a)+bf(b)+2ab$ for all $a,b \in \mathbb{N}$ is always a perfect square. Prove that $f(a)=a$ for all $a \in \mathbb{N}$.
Problem
Source: Iran TST 2011 - Day 4 - Problem 3
Tags: function, pigeonhole principle, induction, modular arithmetic, number theory proposed, number theory
14.05.2011 19:20
$a f(a)$ is perfect square mod $p$ for every $p$ so $a f(a)=g(a)^2$ . So for prime $q$ we have $f(q)=q .T(q)^2$. Put $a=b=q$ in main equation we get $T(q)$ is odd . Now if there is a prime $p$ not equal to $q$ such that $p \mid T(q)$ look at the equation at $(a,b)=(p,q)$ mod $p^2$ to reach contradiction . So $f(p)=p^k$ for every prime $p$ . Also in the same way we can prove $f(1)=1$ (i.e $f(1)$ has no prime divisor) From $(a,b)=(p,1)$ , $(a,b)=(p,2)$ we obtain $f(p)=p$ for all prime $p$ . Choose $(a,b)=(a,p)$ we have $af(a) + p^2 + 2ap$ and $a^2 + p^2 +2ap$ are perfect square for all $p$ . But their diffrence is $a(a-f(a))$ which is constant . But the gap between perfect squares go infinite as the numbers grow . So $f(a)=a$ .
15.05.2011 16:36
mahanmath wrote: Now if there is a prime $p$ such that $p \mid T(q)$ look at the equation at $(a,b)=(p,q)$ mod $p^2$ to reach contradiction . For p=2, I can't find any obvious contradiction.
15.05.2011 19:35
As I mentioned $T(q)$ is odd .
16.05.2011 00:30
Put $a=b=p$ where $p$ is prime. Easily we have $p|f(p)$ for $p>2$. Now put $a=p$ and $b=1,2$ $pf(p)+2p+f(1)=m^2$ and $pf(p)+4p+2f(2)=n^2$ Now since $2f(2)-f(1)$ is constant and $p|f(p)$ easily we have $p=f(p)$ for large $p$. Now for every number $t$ put $q$ prime large enough such that $tf(t)+q^2+2tq<(q+t+1)^2$ Therefore for each $t$ we have $f(t)=t$
16.05.2011 02:54
Thanks, there are two other parts I don't understand. mahanmath wrote: From $(a,b)=(p,1)$ we obtain $f(p)=p$ for all prime $p$ . mahanmath wrote: $a(a-f(a))$ which is constant .
16.05.2011 13:51
in the exam day, i proved that for all a in N where their prime factors are 8k $\pm$ 3 we have f(a)=a and then we r done. but i really complicated my life when i see sumita's solution ...
24.05.2011 11:47
Here is my solution ... I hope it is true ... 1) Lets prove that $ af(a) $ is perfect square for all $ a\in\mathbb{N} $ Otherwise, there is a prime number $ p $, such that $ a_{0}f(a_{0}) $ is divisible by $ p^{2m+1} $ but not by $ p^{2m+2} $ Then let $ b=p^{2m+2}$ and $ a=a_{0} $ $ \Rightarrow a_{0}f(a_{0}) + p^{2m+2}(f(p^{2m+2}) + 2a_{0} ) = x^2 $ $ \Rightarrow x $ is divisible by $ p^{m+1} $ $ \Rightarrow x^2 $ is divisible by $p^{2m+2}$ $ \Rightarrow a_{0}f(a_{0}) $ is divisble by $ p^{2m+2}$ Contradiction! 2) Now if any prime number $ p|f(a) \Rightarrow p|a $ Let $ p|f(a_{0}) $ and if $ a_{0}$ is not divisble by $ p$ $\Rightarrow p^{2n}|f(a_{0})$ (since $af(a)$ is perfect square) then let $ a=a_{0} $ and $ b=p^{2n-1}$ $\Rightarrow a_{0}f(a_{0}) + p^{2n-1}(f(p^{2n-1}) + 2a_{0}) = x^2 $ $ \Rightarrow x $ is divisible by $ p^{n} $ $ \Rightarrow x^2 $ is divisible by $p^{2n}$ $ \Rightarrow f(p^{2n-1}) + 2a_{0} $ is divisble by $ p $ Since $ p^{2n-1}f(p^{2n-1}) $ is square $ \Rightarrow p|f(p^{2n-1})$ $ \Rightarrow p|2a_{0} $ And let $ b=a $ $\Rightarrow 2(af(a) + a^2) = x^2 \Rightarrow$ if $ a $ is odd/even $\Rightarrow af(a) $ is odd/even Proved 3) $ f(1) = 1 $ Otherwise let $ f(1) = c^2 \Rightarrow p|c \Rightarrow p|1 \Rightarrow $ contradiction ! 4) $ f(a) \leq a $ Otherwise let $ f(a) \geq a+1 $ for some $ a \in N$ $b=1 \Rightarrow af(a) + 2a + 1 = M^2$ $(\sqrt{af(a)} + 1)^2 > M^2 > (\sqrt{af(a)})^2 \rightarrow $ contradiction ! 5) Let $ f(x)=x $ for $ x=1,2, ... ,a-1 $ and we must prove that $ f(a) = a $ otherwise $ f(a) \leq a-1 $ Let $ M_{i}^2 = af(a) + i^2 + 2ai $ for $ i=1,2 ... a-1 $ $ \Rightarrow M_{1}^2, M_{2}^2 ... ,M_{a-1}^2 = { 2^2, 3^2 ... (2a-2)^2 } $ $ \Rightarrow $ from Pigeonhole Principle there will be a $ k (0<k<a) $ such that $ M_{k+1} = M_{k} + 1 $ $ \Rightarrow $ $ (\sqrt{af(a) + 2ak + k^2} + 1)^2 = afa + 2a(k+1) + (k+1)^2 $ $ \Rightarrow $ $ f(a) = a $ $ \Rightarrow $ contradiction proved
07.07.2011 20:35
sumita wrote: Put $a=b=p$ where $p$ is prime. Easily we have $p|f(p)$ for $p>2$. Now put $a=p$ and $b=1,2$ $pf(p)+2p+f(1)=m^2$ and $pf(p)+4p+2f(2)=n^2$ Now since $2f(2)-f(1)$ is constant and $p|f(p)$ easily we have $p=f(p)$ for large $p$. Now for every number $t$ put $q$ prime large enough such that $tf(t)+q^2+2tq<(q+t+1)^2$ Therefore for each $t$ we have $f(t)=t$ hello i dont know how can you deduce that '' easily'' that f(p)=p also can you explain me why tf(t)+q^2+2tq<(q+t+1)^2 implies that f(t)=t? thanks
07.07.2011 21:54
Salom. Please explained to me)))
09.07.2011 00:56
khusrav wrote: Salom. Please explained to me))) If we have $f(p)>p$ so both $n$and $m$ are greater than $\sqrt{2} p$ (since we have $f(p)\geq 2p$) Now $2\sqrt{2}p-1<n^2-m^2=2p+(2f(2)-f(1))$ Therefore for large $p$ we have $f(p)=p$ For second problem we have $(t+q)^2 \leq t f(t)+q^{2}+2tq<(q+t+1)^{2}$
14.07.2011 16:45
tahnks!! for you
30.10.2011 10:49
My solution is essentially the same as Altunshukurlu's. Let $G (a, b) = af(a) + bf(b) + 2ab$. Lemma 1: $xf(x)$ is a perfect square for all $x$. Proof: Assume for the sake of contradiction that there exists a $c$ such that $cf(c)$ is not a perfect square. Then $p^{2k+1} || cf(c)$ for some prime $p$ and positive integer $k$. Thus, if we choose an integer $d$ such that a sufficiently large power of $p$ divides $d$, then $p^{2k+1} || cf(c) + df(d) + 2dc$, so $G(d, c)$ is not a perfect square, a contradiction. Lemma 2: If a prime $p | f(x)$, then $p | x$. Proof: Assume for the sake of contradiction that a for an integer $c$, a prime $q$ divides $f(c)$ but does not divide $c$. Note that the power of $q$ that divides $f(c)$ must be greater than or equal to $2$. Take $d$ such that $q^1 || d$. Then $G(c, d) = cf(c) + df(d) + 2dc$. Note that $q^2 | f(c)$ and $q^2 | f(d)$, but $q^1 || 2dc$, so $q^1 || G(c, d)$, contradicting $G (c, d)$ is a perfect square. By Lemma 2, we can conclude that $f(1) = 1$. Now we use induction to show that $f(x) = x$. By trial and error, we can arrive at the base cases $f(1) = 1$, $f(2) = 2$, $f(3) = 3$, and $f(4) = 4$. Assume that for $x = 1, ... k-1$, $f(x) = x$. From Lemma 1, we can write $kf(k) = a^2$. I will first show that $a \le k$. From $G(1, k)$ is a perfect square, we get $kf(k) + 1 + 2k = (z_1)^2$ for some $z$. Thus, we have $(z_1)^2 - a^2 = 2k + 1$. However, we also have $(k+1)^2 - k^2 = 2k + 1$, so if $a > k$, $(z_1)^2 - a^2 > 2k + 1$, a contradiction. Therefore, $a \le k$. Now I will show that $a = k$. Assume for contradiction that $a < k$. Note that for all $1 \le d < k-1$, unless $a = k$, $\sqrt {G(d, k)} + 2 \le \sqrt {G(d+1, k)}$. However, from $a < k$ we also have $\sqrt {G(k - 1, k)} \le 2k - 1$. Since our base case assumes that $k \ge 5$, we also have $G(1, k) = 1 + 10k + kf(k) > 3^2$. Thus, by pidgeonhole, there must be an integer $1 \le e < k - 1$ such that $\sqrt {G (e, k)} = \sqrt {G (e + 1, k)}$, a contradiction. Therefore, $a = k$. This completes the inductive hypothesis, and we can conclude that $f(x) = x$ for all natural $x$.
05.02.2013 17:15
a great problem by Mohsen Jamali
05.02.2013 18:30
I have the same solution as altinsukru a little easer: in the last part we use induction so we consider f(1)=1,...f(n-1)=n-1 now we have f(n)<=n so it's equal to n or f(n-k)=n-k now we give a=n , b=a-k it's easy to proof the result is between two squares so it cant be a square it self!!!!
10.04.2013 08:41
First of all certainly $p|f(p)$ now let $f(p)=px$ where $x$ is not a square.Now take a prime divisor of $x$ and call that $q$ such that $v_q(x)$ is odd.Now choose $a$ such that $v_q(a)>v_q(x)$. Certainly now we get $af(a)+bf(b)+2ab$ isn’t a square. Now so finally we get like $f(p)=px^2$.Similarly we’ve $f(a^2)=b^2$ for all $a\in\mathbb N$. Now so $f(1)$ is indeed a square, let $f(1)=y^2$. Now suppose a large prime we’ve $f(p)\geq 4p$ then obviously we’ve $(\sqrt{pf(p)}+1)^2>pf(p)+2p+y^2>(\sqrt{pf(p)})^2$. That’s absurd,so we get after some stage $f(p)<4p$ where $p$ is a prime. Now clearly we get like $f(p)=p$ for all $p>P$ where $P$ be a fininte prime.Now so we’ve $af(a)+p^2+2ap$ is square for all $p>P$ and for all $a\in\mathbb N$. So $a(f(a)-a)+(a+p)^2$ is a square.Now suppose $f(a)>a$ for some $a$ then $a(f(a)-a)>2(a+p)+1$ certainly it’s absurd for all $p>P$ , again if there exist $a$ such that $f(a)<a$ then $a(a-f(a))>2(a+p)-1$ and similarly again it’s absurd. Thus finally we’ve $f(a)=a$ for all $a\in\mathbb N$.
11.02.2015 09:05
I didn't read the previous proofs. So, sorry, if this proof is essentially the same.
30.10.2015 09:58
I probably won't post my solution being essentially the same but would just remark: 1.) A wonderful problem with rich a number theoretic and a blend of analytic flavors,would love to see it on an ISL. 2.) The ideas of using primes,quadratic residues,convergence of integer sequences meaning they are constant etc(in my solution) though natural,were suitably hard for a #3 unless you have seen: "Given functions $f,g:N^*\rightarrow N^*$, $g$ is surjective and $2f(n)^2=n^2+g(n)^2$, $\forall n>0$. Prove that if $|f(n)-n|\le2005\sqrt n$, $\forall n>0$, then $f(n)=n$ for infinitely many $n$." for example.(another wonderful analytically flavored Number theory by Gabriel Dospinescu)
20.02.2016 06:32
We first prove that $f(p)=p$ is true for all primes $p$. By plugging $b=n$, we have $af(a)+nf(n)+2an$ is a square, so $af(a)$ is a quadratic residue for every positive integer. By ISL 2007 N2, we have $af(a)$ is a square for all $a$. This gives us that $p|f(p^{2a-1})$ for all $a \in \mathbb{N}$ and all primes $p$. I claim that $f(1)=1$. It suffices to prove that $p|f(a) \implies p|a$. Assume otherwise. Since $v_p(a)+v_p(f(a)) \equiv 0 \pmod{2}$ and $v_p(a)=0$, we have $v_p(f(a)) \equiv 0 \pmod{2}$. Let $v_p(f(a))=2k$. Taking $b=p^{2k-1}$, we have $af(a)+p^{2k-1}(f(p^{2k-1})+2a)$ is a square. Since $f(p^{2k-1})$ is a multiple of $p$, it is clear that $v_p(af(a)+p^{2k-1}f(p^{2k-1}) + 2ap^{2k-1})=2k-1$, a contradiction. Therefore, $p|f(a) \implies p|a$, and we have $f(1)=1$. Taking $a=p$ and $b=1$, we have $pf(p)+2p+1$ is a square. Therefore, we have $pf(p)+2p+1 \ge (\sqrt{pf(p)}+1)^2 = pf(p)+2\sqrt{pf(p)}+1$, giving us $f(p) \le p$. Since $p|f(p)$, we conclude that $f(p)=p$, as desired. Now take $b=p$. We have $af(a)+2ap+p^2$ and $a^2+2ap+p^2$ are squares for all $p$. Assume that $f(a) \not= a$. Their difference is $a(a-f(a))$, which is fixed, but as $p \to \infty$, the difference between consecutive squares goes to infinity. Contradiction. Therefore, we are done with our only answer $\boxed{f(n)\equiv n}$. $\blacksquare$
07.05.2017 22:36
sumita wrote: khusrav wrote: Salom. Please explained to me))) If we have $f(p)>p$ so both $n$and $m$ are greater than $\sqrt{2} p$ (since we have $f(p)\geq 2p$) Now $2\sqrt{2}p-1<n^2-m^2=2p+(2f(2)-f(1))$ Therefore for large $p$ we have $f(p)=p$ For second problem we have $(t+q)^2 \leq t f(t)+q^{2}+2tq<(q+t+1)^{2}$ Who can explain why if we assume that there exists a prime number p such that f(p)>p,we can choose p such that the inequality will not be true(sorry if the question is stupid) and additionally,who can explain the last inequality,i did understand nothing!!
03.12.2017 11:07
if n is odd then a=b=n : 2n^2+2nf(n) is square number then f(n)+n even then f(n) is odd(2n divisible by 2 but not 4)
13.01.2021 03:34
Let $P(a,b) \Longrightarrow af(a) + bf(b) + 2ab$. $\textbf{Claim 1} \ af(a)$ is a perfect square for every $a \in \mathbb{N}$ For every prime $p$, $P(a,p) \Longrightarrow af(a) + pf(p) + 2ap \equiv af(a) \ (\text{mod} \ p)$ is a quadratic residue modulo $p$. By a well known lemma in quadratic residue, $af(a)$ is a perfect square. $\rule{25 cm}{3.5pt}$ $\textbf{Claim 2}$ For every large enough prime $p$, $f(p)=p$. By $\textbf{Claim 1}$, it is easy too see that $f(p)$ must be divisible by $p$. Now let $pf(p)= (pk)^2$ for some $k \in \mathbb{N}$. For large enough prime $p$, it is possible to get $P(p,1) \Longrightarrow pf(p) + 2p + f(1) = (pk)^2 + 2p + f(1) < (pk+2)^2$. And because $(pk)^2 + 2p + f(1) > (pk)^2$, then $(pk)^2 + 2p + f(1) = (pk+1)^2 \Longrightarrow k=1$. So, we are able to get $f(p)=p$ for every large enough prime $p$. $\rule{25 cm}{3.5 pt}$ Now we will proof $f(x)=x$ for every $x \in \mathbb{N}$. Let $xf(x)=m^2$. By taking large enough prime $p$, $P(x,p) \Longrightarrow p^2+2xp +m^2$. Since $p$ is large enough, \[ (p+x-1)^2 < p^2 + 2xp + m^2 < (p+x+1)^2\]Which force $p^2 +2xp+ m^2 = (p+x)^2 \Longrightarrow m^2 = x^2 \Longrightarrow f(x)=x$.
20.02.2021 04:11
Solved with nukelauncher. Let \(Q(a,b)\) denote the assertion. By \(Q(a,p)\), where \(p\) is prime, we know \(af(a)+pf(p)+2ap\) is a square, i.e.\ \(af(a)\) is a quadratic residue modulo \(p\). Varying \(p\), we know \(af(a)\) is a perfect square for all \(a\), so let \(af(a)=:g(a)^2\). Then \(a\mid g(a)^2\) for all \(a\), and the assertion is now \[g(a)^2+g(b)^2+2ab\quad\text{is a square}.\] Take a large prime \(P\), so \(P\mid g(P)\). By \(Q(P,1)\), we know \(g(P)^2+g(1)^2+2P\) is a square. We know \[g(P)^2+g(1)^2+2P\ge(g(P)+1)^2\implies P-g(P)\ge\frac{1-g(1)^2}2,\]which is constant. Since \(P\mid g(P)\), for large enough \(P\), this implies \(g(P)=P\), and moreover \(g(1)=1\). Finally, for large primes \(P\), take \(Q(a,P)\) to show \(g(a)^2+P^2+2aP\) is a square; that is, \[(a+P)^2+[g(a)^2-a^2]\]is a square. But \(g(a)^2-a^2\) is fixed, so we can select \(P\) large enough such that \[(a+P-1)^2<(a+P)^2+[g(a)^2-a^2]<(a+P+1)^2,\]thus forcing \(g(a)=a\).
23.03.2022 18:20
Claim : $xf(x)$ is perfect square for all $x \in \mathbb{N}$. Proof : Put $x$ instead of $a$ in main equation. Lets assume there exists $p$ such that $v_p(xf(x)) = 2k+1$. Let $b$ such that $v_p(b) > 2k+1$. Now note that $v_p(xf(x)+bf(b)+2xb) = v_p(xf(x)) = 2k+1$ but $xf(x)+bf(b)+2xb$ is perfect square so contradiction so there exists no such $p$. Claim : For some large $p$ we have $f(p) = p$. Proof : Put $p$ instead of $a$ in main equation. we have $(\sqrt{pf(p)})^2 < pf(p) + f(1) + 2p < (\sqrt{pf(p)}+2)^2$ for some large enough $p$ cause $f(1)$ is constant and LHS has at least $4p$ so if $pf(p) + f(1) + 2p$ is perfect square then $pf(p) + f(1) + 2p = (\sqrt{pf(p)}+1)^2 \implies 2p = 2\sqrt{pf(p)} \implies f(p) = p$ Claim : $f(b) = b$ for all $b \in \mathbb{N}$. Proof : Let $bf(b) = k^2$. we have $p^2 + 2bp + k^2$ is perfect square but again $k$ is constant so for some large enough $p$ we have $(p+b-1)^2 < p^2 + 2bp + k^2 < (p+b+1)^2$ so $p^2 + 2bp + k^2 = (p+b)^2 \implies k^2 = b^2 \implies f(b) = b$.
25.03.2022 11:51
Mahdi_Mashayekhi wrote: $pf(p) + f(1) + 2p < (\sqrt{pf(p)}+2)^2$ for some large enough $p$ Why is this inequality true?