# Greatest common divisor of two positive integers

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

## 1 Answer

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

• 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 – Syed Naqi Nov 17 '15 at 15:44
• 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$. – vadim123 Nov 17 '15 at 15:54
• 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) . – Syed Naqi Nov 18 '15 at 16:11