The gcd is unchanged by subtraction

Statement

Let $a, b \in \mathbb{Z}$. Prove that $\gcd(a, b) = \gcd(a - b,\, b)$.

Solution

It suffices to show that the pairs $\{a, b\}$ and $\{a-b, b\}$ have the same common divisors; then they have the same greatest common divisor.

• If $d \mid a$ and $d \mid b$, then $d \mid (a - b)$; so $d$ is a common divisor of $a-b$ and $b$.
• If $d \mid (a - b)$ and $d \mid b$, then $d \mid \big((a-b) + b\big) = a$; so $d$ is a common divisor of $a$ and $b$.

The sets of common divisors coincide, hence their maximum is the same: $\gcd(a,b) = \gcd(a-b,\,b). \qquad \blacksquare$