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

Community
  • 1
Won Seok Lee
  • 49
  • 1
  • It is not the case that if $d;\vert;2ab$ then $d=1$ or $2$ or $d\vert a$ or $d\vert b$. For example, take $d=15,a=3,b=5$. – John Gowers Aug 27 '15 at 08:58

3 Answers3

3

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

robjohn
  • 345,667
  • i think it is the most clear one ( other answers are also brilliant ). but i want to ask you one more thing. in last sentence, "gcd(a+b,a^b+b^2)|2 thus gcd(a+b,a^2+b^2) = gcd(a+b,2)" why does it hold? – Won Seok Lee Oct 08 '14 at 06:50
  • i think it is equivalent state with " if gcd(a,b) | c then gcd(a,b) = gcd (a,c)" but it does not hold when a=8,b=4,c=8 – Won Seok Lee Oct 08 '14 at 06:57
  • @WonSeokLee: If $2\mid a+b$, then $2\mid a^2+b^2$; thus $\gcd(a+b,a^2+b^2)=2=\gcd(a+b,2)$. If $2\not\mid a+b$, then $2\not\mid a^2+b^2$; thus $\gcd(a+b,a^2+b^2)=1=\gcd(a+b,2)$. Therefore, in either case, $\gcd(a+b,a^2+b^2)=\gcd(a+b,2)$. – robjohn Oct 08 '14 at 12:06
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$).

egreg
  • 238,574
  • To rule out $4\mid\gcd(a+b,a^2+b^2)$, we can also use the fact that if $\gcd(a,b)=1$, then $a^2+b^2$ is either $1$ or $2$ mod $4$. – robjohn Oct 07 '14 at 21:01
  • @robjohn Yes, of course. Everything but your computation. ;-) – egreg Oct 07 '14 at 21:05
2

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

Barry Cipra
  • 79,832