# If $d=\gcd(a+b,a^2+b^2)$, with $\gcd(a,b)=1$, then $d=1$ or $2$

Suppose $\gcd(a,b)=1$. Let $d=\gcd(a+b,a^2+b^2)$. I want to prove that $d$ equals $1$ or $2$.

I get that $d\mid2ab$ but I can't find a linear combination that will give me some help to use the fact that $\gcd(a,b)=1$.

• Keep going. Try to find another linear combination with $2ab$ to eliminate $a$ or $b$. Apr 16 '14 at 19:27
• Well i found the solution (ohh and i was searching a solution without using prime numbers) ..well d|a^2+b^2-(a-b)(a+b) ---> d|2b^2 same with d|2a^2 so d is a common divisor of 2b^2 nad 2a^2 so it divines the gcd(2a^2,2b^2) d|2(a^2,b^2) and because the gcd(a^2,b^2)=1 because gcd(a,b)=1 ---> d is a divisor of 2 so it is 1 or 2.I didnt find a way to continue with the d|2ab....
– Jam
Apr 16 '14 at 23:02
• Apr 17 '14 at 20:59
• @Manolis See my answer for one natural way to use $\,d\mid 2ab.\ \$ Apr 17 '14 at 21:00

Well I found the solution. (Ohh and I was searching a solution without using prime numbers.)

Well $d\mid a^2+b^2-(a-b)(a+b)\;\Rightarrow\;d\mid 2b^2$. Same with $d\mid 2a^2$ so $d$ is a common divisor of $2b^2$ and $2a^2$ so it divides the $\gcd(2a^2,2b^2)=2\gcd(a^2,b^2)$. Since the $\gcd(a^2,b^2)=1$ because $\gcd(a,b)=1$ it follows that $d$ is a divisor of $2$, so it is $1$ or $2$.

I didnt find a way to continue with the $d\mid 2ab$....

• Well done! To use $2ab$ you could have done $d\mid 2b(a+b)-2ab=2a^2$, and the rest follows. Apr 17 '14 at 8:35
• I improved the formatting using $\LaTeX$. You can click the edit button to see what I exactly did, and perhaps try to do this yourself next time. Questions and answers without $\LaTeX$ tend to get downvoted. Apr 17 '14 at 8:44
• thanks!Ill try to use Latex.
– Jam
Apr 17 '14 at 10:41

Suppose $p$ is a prime that divides $a+b$ and $a^2+b^2$, then $p$ also divides $2ab$ and therefore it divides $2$ or $a$ or $b$, but if $p$ divides $a$ and $a+b$...

Hint $\,\ d=(a\!+\!b,a^2\!+b^2)\mid 2a^2,2ab,2b^2\Rightarrow\,d\mid(2a^2,2ab,2b^2)= 2(a,b)^2 = 2\$ by $\ (a,b)=1$

Remark $\$ More generally one easily proves $\ (a^2\!+b^2,a\!+\!b) = (2(a,b)^2,a\!+\!b)$

Bezout based approach

Since $(a,b)=1$, there are $x,y$ so that $ax+by=1$. Then \begin{align} 1 &=(ax+by)^3\\ &=a^2\color{#C00000}{(ax^3+3bx^2y)}+b^2\color{#00A000}{(3axy^2+by^3)} \end{align} Then, since $$(a^2+b^2)+(a+b)(a-b)=2a^2$$ and $$(a^2+b^2)-(a+b)(a-b)=2b^2$$ we have \begin{align} &(a^2+b^2)\left[\color{#C00000}{(ax^3+3bx^2y)}+\color{#00A000}{(3axy^2+by^3)}\right]\\ +&(a+b)(a-b)\left[\color{#C00000}{(ax^3+3bx^2y)}-\color{#00A000}{(3axy^2+by^3)}\right]\\ =&2a^2\color{#C00000}{(ax^3+3bx^2y)}+2b^2\color{#00A000}{(3axy^2+by^3)}\\[6pt] =&2 \end{align} Therefore, $(a+b,a^2+b^2)\mid2$.