4
$\begingroup$

I know that Greatest common divisor of two positive integers $a$ and $b$ is the largest positive integer that divides both $a$ and $b$, but how can I use that to prove that $\gcd(a, b) = \gcd(a, b-a)$.

$\endgroup$

1 Answer 1

3
$\begingroup$

Set $c=\gcd(a,b)$ and $d=\gcd(a,b-a)$ for convenience.

Step 1: Prove that $c$ is a common divisor of $a,b-a$. This proves $c\le d$.

Step 2: Prove that $d$ is a common divisor of $a,b$. This proves $d\le c$.

$\endgroup$
3
  • $\begingroup$ how do you prove that c is a common divisor of a, b-a and also how do you prove that d is a common divisor of a, b $\endgroup$
    – Syed Naqi
    Nov 17, 2015 at 15:44
  • $\begingroup$ We know $c$ divides $a,b$. Hence it divides $a$, and also divides $b-a$. Hence it is a common divisor of $a,b-a$. $\endgroup$
    – vadim123
    Nov 17, 2015 at 15:54
  • $\begingroup$ so how does that allow us to come to the fact or how do we use those to tell that gcd(a,b)=gcd(a,b−a)gcd(a,b)=gcd(a,b−a) . $\endgroup$
    – Syed Naqi
    Nov 18, 2015 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .