If $a$ and $b$ are positive integers such that $ab \mid a^2+b^2$ prove that $a=b$
Problem
Source: Regional Olympiad - Federation of Bosnia and Herzegovina 2010
Tags: number theory, Divisibility
27.09.2018 15:57
16.10.2018 21:07
What can be the real values for $a,b $??
16.10.2018 21:23
NikoIsLife wrote:
very nice solution
17.10.2018 04:18
Alternate method: We need to show that $ab|a^2+b^2$ or $\frac{a^2+b^2}{ab}=n$ where $n$ is an integer. But $\frac{a^2+b^2}{ab}=\frac{a}{b}+\frac{b}{a}$ so $\frac{a}{b}+\frac{b}{a}=n$. Now, since integers are in the form $\frac{x}{1}$, even $a$ and $b$ should be in that form. However for $\frac{a}{b}$ AND $ \frac{b}{a}$ to be an integer, we can have $b|a$ so then $\frac{a}{b}$ will be an integer but since $a>b$, $ \frac{b}{a}$ will not be an integer. Notice that if they both divide each other, then it will be an integer. This is only possible when $a=b$.
17.10.2018 05:47
gobathegreat wrote: If $a$ and $b$ are positive integers such that $ab \mid a^2+b^2$ prove that $a=b$ We know that $a^2+b^2\ge 2ab$, therefore, either $a^2+b^2=ab$ or $a^2+b^2=2ab$. In the first case, we have that $(a-b)^2=-ab<0$ which is impossible, hence $a^2+b^2=2ab$, and $(a-b)^2=0\implies \boxed{a=b}$
17.10.2018 07:36
programjames1 wrote: We know that $a^2+b^2\ge 2ab$, therefore, either $a^2+b^2=ab$ or $a^2+b^2=2ab$ I don't think that's correct...
17.10.2018 10:13
My solution: Suppose that $a \neq b$. If $gcd(a,b)=1$, then $$gcd(a^2,ab)=gcd(ab,b^2)=1 \Rightarrow gcd(ab,a^2+b^2)=1$$This forces $ab=1$. But as $a$ and $b$ are positive integers, this gives $a=b=1$. So from now on we have $gcd(a,b) \neq 1$. Take $a=ga_1$ and $b=gb_1$, where $gcd(a_1,b_1)=1$. Then we get $g^2a_1b_1 \mid g^2(a_1^2+b_1^2) \Rightarrow a_1b_1 \mid a_1^2+b_1^2$. By a similar argument as before, we get $a_1=b_1=1$, thus giving $a=b$. $\blacksquare$
17.10.2018 10:59
ab/a^2+b^2 Implies ab/a^2 and ab/b^2 implies b/a and a/b so, a=b.
17.10.2018 11:31
debasish123 wrote: ab/a^2+b^2 Implies ab/a^2 and ab/b^2 implies b/a and a/b so, a=b. This is not always necessary Take smaller example.....say $2 | 8$ that doesnot mean that $2|5$ and $2|3$
17.10.2018 11:31
debasish123 wrote: ab/a^2+b^2 Implies ab/a^2 and ab/b^2 implies b/a and a/b so, a=b. This doesn't make sense. $ab/a^2+b^2 \neq ab/a^2+ab/b^2$
17.10.2018 12:46
gobathegreat wrote: If $a$ and $b$ are positive integers such that $ab \mid a^2+b^2$ prove that $a=b$ Let $d = \gcd(a,b)$ and $a=md, b=nd$. Thus we have \[mnd^2\mid d^2(m^2+n^2)\implies mn\mid m^2+n^2.\]Now $\gcd(m,n)=1$. \[\gcd(mn,m^2+n^2) = \gcd(mn^2, m^2+n^2) = \frac{\gcd(mn^2,m^3)}{m} = \gcd(n^2,m^2) = 1.\]But $mn\mid m^2+n^2$, thus $mn = 1$ or $m=n=1$ and we are done.
17.10.2018 12:53
\[\begin{gathered} ab\left| {{a^2} + {b^2}} \right. = > {a^2} - kab + {b^2} = 0\, \hfill \\ It's\,easily\,to\,see\,that\,k \geqslant 2 \hfill \\ Let\,S = \{ (a,b) \in {Z^ + },\frac{{{a^2} + {b^2}}}{{ab}} \in {Z^ + }\} \hfill \\ \hfill \\ Let\,({a_0},{b_0}) \in S\,is\,the\,pair\,\,which\,\operatorname{minimizes} \,the\,sum\,a + b\,over\,all\,such\,pair \hfill \\ Consider\,the\,equation:\,{a^2} - ka{b_0} + {b_0}^2 = 0\,(1) \hfill \\ With\,out\,loss\,of\,generally,\,suppose\,that\,{a_0} \geqslant {b_0} \hfill \\ The\,equation\,(1)\,has\,another\,root\,is\,{a_1}\,satisfy\,the\,following\,conditions \hfill \\ \left\{ \begin{gathered} {a_0} + a{}_1 = k{b_0} \hfill \\ {a_0}{a_1} = b_0^2 \hfill \\ \end{gathered} \right.\,Hence,\,{a_1} \in {Z^ + } \hfill \\ Then\,({a_1},{b_0})\,is\,the\,pair\,of\,root\,in\,(1) \hfill \\ We\,have:\,{a_1} + {b_0} \geqslant {a_0} + {b_0} = > {a_1} \geqslant {a_0} \geqslant {b_0} \hfill \\ = > f({b_0}) \geqslant 0 = > k \leqslant 2\,with\,f(a) = {a^2} - ka{b_0} + {b_0}^2 \hfill \\ \end{gathered} \]
17.10.2018 21:46
We use Vietta jumping. We have $a^2+b^2=kab$ for some natural number $k$. Now take this quadratic in terms of $a$. If $a$ is currently not the larger root make it so. Do the same for b (in otherwords, $b\to ka-b$). We can keep going until $a\ge kb$ or $a\le \frac{kb}2$ and $b\le \frac{ka}2$. In this second case we have $$a^2+b^2\ge kab\ge 2a^2$$So $b\ge a$. Also, $$a^2+b^2\ge kab\ge 2b^2$$so $a\ge b$. This implies that $a=b$, eventually. But with our original $a,b$ we now know that, $$\frac{a^2+b^2}{ab}=2\Longleftrightarrow (a-b)^2=0\implies a=b$$Now in the first case, we have $a\ge kb$ Hence $$kab=a^2+b^2\ge kab+b^2$$Which implies $b=0$, so $a^2+b^2=kab=0$. Therefore, with our original $a,b$, $$a^2+b^2=0\Longleftrightarrow a=b=0$$
18.10.2018 09:47
https://artofproblemsolving.com/community/c728438h1707823_system_of_divisibles $\begin{cases}ab|a^2+b^2\\(ab)^2|a^2 b^2\end{cases} \Rightarrow \begin{cases}ab|a^2\\ab|b^2\end{cases} \Rightarrow \begin{cases}b|a\\a|b\end{cases} \Rightarrow a=b$