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

|cite|improve this question
$\endgroup$
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$.

|cite|improve this answer
$\endgroup$
  • $\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 '15 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 '15 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 '15 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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