3
$\begingroup$

How to show that $\gcd(a + b, a^2 + b^2) = 1\mbox{ or } 2$ for coprime $a$ and $b$?

I know the fact that $\gcd(a,b)=1$ implies $\gcd(a,b^2)=1$ and $\gcd(a^2,b)=1$, but how do I apply this to that?

$\endgroup$
1
  • $\begingroup$ You can use Euclid's algorithm to simplify the $\gcd$. See the previous question. $\endgroup$
    – user14972
    Aug 9, 2013 at 4:07

3 Answers 3

5
$\begingroup$

Hint: Write $a^2+b^2=(a + b)(a − b)+2b^2$.

Now you can show that $\gcd(a+b, b^2)=1$ so that $\gcd(a + b, 2b^2) = 1\text{ or }2$.

$\endgroup$
1
  • $\begingroup$ Very nice! ---- $\endgroup$
    – Eric Auld
    Aug 8, 2013 at 23:22
0
$\begingroup$

Hint: Suppose gcd(a,b)=1 and let $d=gcd(a+b,a^2+b^2) \implies d|(a+b) $ and $ d|(a^2+b^2)$. Let $dr=a+b$ and $ds=a^2+b^2$ where $r,s \in\mathbb{Z}$. We see that by squaring $dr=a+b$ we get $d^2r^2=a^2+2ab+b^2$. Then $d^2r^2-d=a^2+2ab+b^2-a^2-b^2=2ab$. Thus $d(dr^2-1)=2ab\implies d|2ab$ From this we break the proof into two cases where $d$ is odd and $d$ is even.

Case:1.(We want to somehow show d=1). Suppose d is odd then $gcd(d,2)=1$. It follows $d|ab \implies d|a$ or $d|b$. If $d|a$ and since $d|(a+b)$. We see that since $d|(a+b)-d|a=d|b$ and since we assumed $gcd(a,b)=1$ it follows d=1. If $d|b$ then we see that $d|(a+b)-d|b=d|a$. Similarly $d=1$.

Case 2: Suppose d is even and in this case somehow show $d=2$.

$\endgroup$
0
$\begingroup$

Let positive integer $d$ divides both $a+b,a^2+b^2$

$\implies d$ divides $(a^2+b^2)+(a+b)(a-b)=2a^2$

Similarly, i.e., $d$ divides $(a^2+b^2)-(a+b)(a-b)=2b^2$

$\implies d$ divides $2a^2,2b^2\implies d$ divides $(2a^2,2b^2)=2(a^2,b^2)=2(a,b)^2$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.