when ${\rm gcd} (a,b)=1$, what is ${\rm gcd} (a+b , a^2+b^2)$? I want to prove above statement
"what is ${\rm gcd} (a+b , a^2+b^2)$ when ${\rm gcd}(a,b) = 1$"
I've seen some proofs of it, but i couldn't find useful one.
here is one of the proof of it.
some proofs
I want prove it using method like 2nd answer. (user 9413)
but i can't understand why "if $d | 2ab$ then $d = 1$ or $2$ or $d | a$ or $d|b$"
(isn't Euclid's lemma which only holds when $d$ is prime ?)
please show me proof step by step
 A: Suppose $\gcd(a,b)=1$, that is, there are $x,y$ so that $ax+by=1$. Then
$$
\begin{align}
1
&=(ax+by)^3\\
&=a^2(ax^3+3bx^2y)+b^2(3axy^2+by^3)
\end{align}
$$
Therefore,
$$
\begin{align}
\small2
&\small=\overbrace{(\color{#00A000}{(a^2+b^2)}+\color{#C00000}{(a+b)}(a-b))}^{\large 2a^2}(ax^3+3bx^2y)+\overbrace{(\color{#00A000}{(a^2+b^2)}-\color{#C00000}{(a+b)}(a-b))}^{\large 2b^2}(3axy^2+by^3)\\[4pt]
&\small=\color{#C00000}{(a+b)}(a-b)(ax^3+3bx^2y-3axy^2-by^3)+\color{#00A000}{(a^2+b^2)}(ax^3+3bx^2y+3axy^2+by^3)
\end{align}
$$
This means that $\gcd(a+b,a^2+b^2)\mid2$. Thus,
$$
\gcd(a+b,a^2+b^2)=\gcd(a+b,2)
$$
A: We know that $a^2+b^2=(a+b)^2-2ab$ so we can say that
$$
\gcd(a+b,a^2+b^2)=\gcd(a+b,2ab)
$$
Now a prime number $p$ that divides $a+b$ and $2ab$ must either divide $2$ (that is $p=2$) or divide $a$ or divide $b$. But if $p\mid a$ and $p\mid(a+b)$, then $p\mid b$. Similarly, if $p\mid b$, then $p\mid a$. In both cases we have a contradiction with $\gcd(a,b)=1$.
Therefore either $2$ is the only prime dividing both $a+b$ and $a^2+b^2$ or no prime divides both $a+b$ and $a^2+b^2$. In the second case, $\gcd(a+b,a^2+b^2)=1$. In the first case, the greatest common divisor is $2^k$ for $k\ge1$. But if $k>1$, from $2^k\mid 2ab$ we get $2^{k-1}\mid ab$ and so $2\mid ab$, which can be ruled out as before.
So the greatest common divisor is $1$ or $2$. The second case happens when $a+b$ is even (and so also $a^2+b^2$).
A: You are correct in what you don't understand about the linked-to answer (by user 9413).  It would have been better in that answer to let $d$ be a prime power dividing $\gcd(a+b,a^2+b^2)$ and conclude that $d$ could only be $1$ or $2$.
