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.

We first show that there is no odd prime $p$ that divides both $a+b$ and $a^2+b^2$.
For if $p$ divides both, then $p$ divides $(a+b)^2-(a^2+b^2)$, so $p$ divides $2ab$. Since $p$ is odd, it divides one of $a$ or $b$, say $a$. But then since $p$ divides $a+b$, it must divide $b$. This contradicts the fact that $a$ and $b$ are relatively prime.
So the only possible common divisors of $a+b$ and $a^2+b^2$ are powers of $2$. If $a$ is even and $b$ is odd (or the other way) then the greatest common divisor of $a+b$ and $a^2+b^2$ is therefore $1$.
If $a$ and $b$ are both odd, then $a^2+b^2\equiv 2\pmod{8}$, and therefore the highest power of $2$ that divides $a^2+b^2$ is $2^1$. So in that case $\gcd(a+b,a^2+b^2)=2$. 
