when ${\rm gcd} (a,b)=1$, what is ${\rm gcd} (a+b , a^2+b^2)$?

Question

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

Answer 1

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$.

Answer 2

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) $$

Answer 3

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$).