Prove $gcd(a,b)=gcd(a,2a+b)$

Question

It's simple to show that $d$ is SOME divisor of $a$ and $2a+b$, since we already know $d|a$ and $d|b$, so it divides the linear combination $2a+b$. However, how can I show that $d$ is the GREATEST common divisor of $a$ and $2a+b$?

Edit: Let $e$ be some other common divisor of $a$ and $2a+b$. Do we know if it's true that $e|b$? If so, we're finished since anything that divides both $a$ and $b$ will also divide $d$, since $d=gcd(a,b)$.

score 3 · Accepted Answer · answered Dec 04 '14 at 19:16

3

If $x$ divides both $a$ and $2a+b$ then $x$ divides both $a$ and $b$. Therefore $x$ divides $d$, so $x \leq d$.

answered Dec 04 '14 at 19:16

Michael Biro

13,757

How do you know $x|b$? – EthanAlvaree Dec 04 '14 at 19:17
$b=(2a+b)-2a$ … – Harald Hanche-Olsen Dec 04 '14 at 19:17
$b = (2a+b) - 2a$. Since $x$ divides both terms on the right, it also divides the left. – Michael Biro Dec 04 '14 at 19:18
Ah - understood, thank you very much Michael! – EthanAlvaree Dec 04 '14 at 19:32

score 3 · Answer 2 · answered Dec 04 '14 at 19:22

3

Another way to put the answer by Michael: What you (Ethan) have done, shows that $\gcd(a,2a+b)\ge \gcd(a,b)$. If you put $c=2a+b$, then the same argument shows that $\gcd(a,b)=\gcd(a,c-2a)\ge\gcd(a,c)=\gcd(a,2a+b)$.

answered Dec 04 '14 at 19:22

Harald Hanche-Olsen

31,960

Prove $gcd(a,b)=gcd(a,2a+b)$

2 Answers2

Linked