How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$ If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can't find a way to use any of the elemental divisibility and gcd theorems to find them. 

We have $a^2 + b^2 - a(a+b) = b^2 - ab = -b (a-b)$ and $a^2 + b^2 - b(a+b) = a^2 - ba = a (a-b)$. 
So if $d$ divides both $a+b$ and $a^2+b^2$, then $d$ divides $$\gcd(a (a-b), b (a-b)) = \gcd(a, b) (a-b) = a - b.$$
So $d$ divides $a+b + a - b = 2a$ and $a+b - (a - b) = 2b$.
So $d$ divides $2\gcd(a,b)=2$. 
So the possibilities for the $\gcd$ appear to be $1$ and $2$, and both clearly occur.
