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)$.
4
$\begingroup$
$\endgroup$
3
$\begingroup$
$\endgroup$
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$.
-
$\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
