# Number Theory : $\gcd$ of $(a^2 + b^2, a+b)$ , where $\gcd$ of $(a,b)$ $=$ $1$?

I was solving some basic number theory problems when I came across :

What is $\gcd(a^2 + b^2, a+b)$, where $a$ and $b$ are relatively prime integers that are not both $0$?

Can someone help me out ? Even a hint , upon which I can build , would suffice ...

• A start: Any common divisor of $a^2+b^2$ and $a+b$ is a common divisor of $a+b$ and $(a+b)^2-(a^2+b^2)$, which is $2ab$. Feb 20, 2015 at 1:51
• Hi , @AndréNicolas -- I got upto this point that a prime divisor of $(a^{2} + b^{2} , a+b)$ , will also divide $2ab$ $\Rightarrow$ it also divides $2$ $\Rightarrow$ it is $=$ $1$ or $2$ . How can I proceed after that ? Feb 20, 2015 at 1:55
• If $a,b$ are both odd, then it's 2. Otherwise, it's 1. Feb 20, 2015 at 2:00
• You are finished, once you show (using a couple of examples) that $1$ and $2$ are both possible. But you need to show that any common divisor is $1$ or $2$, not, as you put it, that a prime divisor of the gcd is $1$ or $2$. Feb 20, 2015 at 2:02
• @pranav The answer is $\,(a\!+\!b,2).\,$ More generally, when $\,d = (a,b) > 1\,$ it is $\,(a\!+\!b,2d^2),\,$ as I show in my answer. Feb 20, 2015 at 2:25

Hint Modulo $a+b$, $(a+b)^2\equiv 0$ so $a^2+b^2\equiv -2ab$. Hence you want to compute $(2ab,a+b)$.
Hint If $d= \gcd(a+b,a^2+b^2)$, then $d\mid(a-b)(ab)$ hence
$$d \mid (a^2+b^2) \pm (a^2-b^2)$$
Hint $\ \ (a\!+\!b,\ a^2\!+\!b^2)\, =\, (a\!+\!b,\,\color{#c0f}{2a^2}, \ \color{blue}{2ab}, \ \color{#c00}{2b^2})\, =\, (a\!+\!b,\,2(a,b)^2\!)\,$ [$=\, (a\!+\!b,2)\$ if $\ (a,b)=1$]
by $\ a^2\!+\!b^2 = (\color{#0A0}{b^2\!-\!a^2})+\color{#c0f}{2a^2} = (\color{#0A0}{a\!+\!b})^2\!-\color{blue}{2ab} = (\color{#0A0}{a^2\!-\!b^2})+\color{#c00}{2b^2}\,$ and $\,\color{#0a0}{\rm greens}\equiv 0\pmod{a\!+\!b}$