If $(a,b)=1$, prove that $(a^2+b^2,a+b)=1$ or $2$. If $(a,b)=1$, prove that $(a^2+b^2,a+b)=1$ or $2$.
So far, I let
$d=(a^2+b^2,a+b)$
$\implies d|(a^2+b^2-(a+b)^2)$
$\implies d|(a^2+b^2-(a^2+2ab+b^2))$
$\implies d|(-2ab)$
I have heard from other people that this somehow leads to a conclusion, but I am not seeing it. Alternatively, is there some other way of showing it?
EDIT(10:41PM):
Just noticed that
$(a^2+b^2\pm (a+b)(a-b),a+b)$
results in
$d|2a^2$ and $d|2b^2$.
$\implies d|(2a^2,2b^2)$.
$\implies d|2(a^2,b^2)$.
Now I just have to fully understand why
$(a,b)=1\implies (a^2,b^2)=1$.
I sort of intuitively understand this.
 A: Hint: What contradiction can you get if $d|a$ or $d|b$ but $d \neq1$?
A: Lemma 1: If $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$.
Proof: We will prove the contrapositive. Suppose $\gcd(a^2,b^2)>1$. Then $a^2$ and $b^2$ must have a prime common divisor, say $p$. Since $p|a^2$, Euclid's lemma implies that $p|a$. Similarly, $p|b$. Thus $p$ is a common divisor of $a,b$ and so $\gcd(a,b)>1$.
Lemma 2: If $\gcd(u,v)=1$, then $\gcd(u+v,u-v) \leq 2$.
Proof: Let $d$ be a common divisor of $u+v$ and $u-v$. Then $d|(u+v+u-v)$ and so $d|2u$. Moreover, $d|(u+v-(u-v))$ and so $d|2v$. Thus $d|\gcd(2u,2v)$. But $\gcd(2u,2v)=2\gcd(u,v)=2$. It follows that $\gcd(u+v,u-v) \leq 2$.
Given these two lemmas, we'll prove the problem statement. Since $\gcd(a,b)=1$, $\gcd(a^2,b^2)=1$ by Lemma 1. Now, by setting $u=a^2$, $v=b^2$ in Lemma 2, we can see that $\gcd(a^2+b^2,a^2-b^2) \leq 2$. 
Finally, suppose $d$ is a common divisor of $a^2+b^2$ and $a+b$. Because $d|(a+b)$, $d|(a+b)(a-b)=a^2-b^2$. So $d$ is a common divisor of $a^2+b^2$ and $a^2-b^2$. It follows that $d \leq 2$, completing the proof.
A: Consider the case where a and b are both odd. In this case, since d divides (-2ab), and a and b are coprime, the condition becomes 
d divides a or d divides b or d divides 2.
If d divides a, then d | ( (a+b)-a ), and thus d divides b, a contradiction since a and b are coprime. Hence, d divides 2; d is 1 or 2.
Next consider the case where a even, b odd. (The case where b even, a odd is similar.) We express a as (2^n)(c), where c is an odd positive integer and n is positive integer. Then d divides (-2ab) is equivalent to d divides (2a) or d divides b (since 2a and b are coprime). If d divides b, then by similar reasoning as above d would divide a, leading to a contradiction. The remaining case is where d contains 2^(n+1) as a factor; however that cannot be true as d divides (a+b) which is odd. Therefore, as per the first case d divides 2; d is 1 or 2.
A: Many gcd questions can be answered by finding a way to use the Euclidean algorithm. By the Euclidean algorithm, I mean $(a, aq+r) = (a,r)$.
Here, $a$ is played by $a+b$, $q$ is played by $a-b$, and $r$ is played by $2b^2$. The Euclidean algorithm then implies that
 $$(a+b, (a+b)(a-b) + 2b^2) = (a+b, 2b^2).$$
This reads as $(a^2+b^2, a+b) = (a+b, 2b^2)$. The conclusion should now be clear.
