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. 
 A: Since $\gcd(a,b)=1$, Bezout's Identity says we have an $x$ and $y$ so that
$$
ax+by=1\tag{1}
$$
Note that
$$
\begin{align}
2a^2&=(a^2+b^2)+(a+b)(a-b)\\
2ab&=(a+b)^2-(a^2+b^2)\\
2b^2&=(a^2+b^2)-(a+b)(a-b)\\
\end{align}\tag{2}
$$
Therefore, incorporating $(1)$ and $(2)$,
$$
\begin{align}
2
&=2(ax+by)^2\\
&=2a^2x^2+4abxy+2b^2y^2\\
&=\Big((a^2+b^2)+(a+b)(a-b)\Big)x^2\\
&+2\Big((a+b)^2-(a^2+b^2)\Big)xy\\
&+\Big((a^2+b^2)-(a+b)(a-b)\Big)y^2\\
&=\color{#00A000}{(x-y)^2}\color{#C00000}{(a^2+b^2)}
+\color{#00A000}{((x^2-y^2)(a-b)+2xy(a+b))}\color{#C00000}{(a+b)}\tag{3}
\end{align}
$$
Equation $(3)$ says that
$$
\gcd(a+b,a^2+b^2)\,|\,2\tag{4}
$$
Note that $\gcd(1+2,1^2+2^2)=1$ and $\gcd(1+3,1^2+3^2)=2$, so both $1$ and $2$ are possible.
A: Put $\,\rm (a,b)=1\,$ below.
Theorem $\rm\,\ \  (a\!+\!b,\ a^2\!+\!b^2)\, =\, (\color{#c00}{2a^2,\ \ 2ab,\ \ 2b^2},\ a\!+\!b)\, \overset{\rm\color{#c00}E}=\, (\color{#c50}{2(a,b)^2}\!,\ a\!+\!b)$
Proof $\rm\ mod\ a\!+\!b\!:\ a^2\!+\!b^2  \equiv \color{#c00}{2a^2\! \equiv -2ab \equiv 2b^2}\  $   by $\rm\,a\!+\!b\,$ divides $\rm\color{#0A0}{green}$ terms below
$$\quad\ \ \ \rm a^2\!+\!b^2 = (\color{#0A0}{b^2\!-\!a^2})+\color{#c00}{2a^2} = (\color{#0A0}{a\!+\!b})^2\!\color{#c00}{-2ab} = (\color{#0A0}{a^2\!-\!b^2})+\color{#c00}{2b^2}  $$
A: $$ \gcd(a+b,a^2+b^2) \mid \gcd((a+b)(a-b), a^2+b^2) = \gcd(a^2-b^2, a^2+b^2) \mid \gcd [ ( a^2+b^2)+ (a^2-b^2) , ( a^2+b^2)+ (a^2-b^2) ]=2 \gcd(a^2,b^2)=2$$
Now it is easy to check that both 1 and 2 are possible...
A: Note that $a^2+b^2=(a+b)^2-2ab$.   Thus $a^2+b^2\equiv -2ab\mod a+b$ and you need to find $(a+b,-2ab)=(a+b,2ab)$.   Can you move on?
ADD Note that $a,b$ cannot be both even. If one is odd and the other is even, then $2\not\mid a+b$, so  $(a+b,2ab)=(a+b,ab)$. But if $p>2$ is a prime with $p\mid a+b,ab$ then $p\mid a$ or $p\mid b$, since $p\mid ab$. But in any case, since $p\mid a+b$, this would give $p \mid b$ (if $p\mid a$) or $p \mid a$ (if $p\mid b)$, contrary to $(a,b)=1$. Thus $(a+b,ab)=1$. 
If $a,b$ are both odd, then $a+b$ is even and $2\mid (a+b,2ab)$. And again, if $p$ is an odd prime factor  $p\mid 2ab\implies p\mid ab$ and the same argument above goes through. Thus whenever $(a,b)=1$, $$(a+b,a^2+b^2)=\begin{cases} 1 &\text{if one of } a,b \text{ is odd}\\2&\text{if both} a,b\text{ are odd}\end{cases}$$
A: 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.
A: $$\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$.
