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)$.
[Math] Greatest common divisor of two positive integers
elementary-number-theorylogic
Best 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$.