<s>[INST] 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. 
 [/INST] $$\begin{align}
\gcd(a+b, a^2 + b^2)
&= \gcd(a+b, a^2 + b^2 - a(a+b))
\\&= \gcd(a+b, b^2 - ab)
\\&= \gcd(a+b, b^2 - ab + b(a+b))
\\&= \gcd(a+b, 2b^2)
\end{align}
$$
Now, $\gcd(a+b,b) = \gcd(a,b) = 1$, so we can get rid of the factors of $b$ and have
$$ \gcd(a+b, a^2 + b^2) = \gcd(a+b, 2) $$
The strategy I used was still the basic idea of the Euclidean algorithm; since I couldn't compare numeric values, I instead simplified by working to eliminate the variable $a$, starting with the largest power of $a$.
</s>