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

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$.
• 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$. Nov 17 '15 at 15:54