<s>[INST] Show that $\gcd(a + b, a^2 + b^2) = 1$ or $2$ if $\gcd(a, b)=1$ Show that $\gcd(a + b, a^2 + b^2) = 1$ or $2$ if $\gcd(a, b)=1$.
I have absolutely no clue where to start and what to do, please provide complete proof and answer.
 [/INST] We use repeatedly the identity $\gcd(x,y)=\gcd(x,y+kx)$ for any integer $k$.
For $k=-(a+b)$, we have $$\gcd(a+b,a^2+b^2)=\gcd(a+b,-2ab)$$
But $\gcd(a,b)=1$ so $\gcd(a,a+b)=1$ and similarly $\gcd(b,a+b)=1$.  Combining, we get $\gcd(ab,a+b)=1$.  Hence $\gcd(a+b,a^2+b^2)=\gcd(a+b,-2)$, which is $1$ or $2$.
</s>