# GCD with Remainder

## Theorem

Let $a, b \in \Z$.

Let $q, r \in \Z$ such that $a = q b + r$.

Then:

$\gcd \set {a, b} = \gcd \set {b, r}$

where $\gcd \set {a, b}$ is the greatest common divisor of $a$ and $b$.

## Proof

 $\ds$  $\ds \gcd \set {a, b} \divides a \land \gcd \set {a, b} \divides b$ Definition of Greatest Common Divisor of Integers $\ds \leadsto \ \$ $\ds$  $\ds \gcd \set {a, b} \divides \paren {a - q b}$ Common Divisor Divides Integer Combination $\ds \leadsto \ \$ $\ds$  $\ds \gcd \set {a, b} \divides r$ as $r = a - q b$ $\ds \leadsto \ \$ $\ds$  $\ds \gcd \set {a, b} \le \gcd \set {b, r}$ Definition of Greatest Common Divisor of Integers

The argument works the other way about:

 $\ds$  $\ds \gcd \set {b, r} \divides b \land \gcd \set {b, r} \divides r$ Definition of Greatest Common Divisor of Integers $\ds \leadsto \ \$ $\ds$  $\ds \gcd \set {b, r} \divides \paren {q b + r}$ Common Divisor Divides Integer Combination $\ds \leadsto \ \$ $\ds$  $\ds \gcd \set {b, r} \divides a$ as $a = q b + r$ $\ds \leadsto \ \$ $\ds$  $\ds \gcd \set {b, r} \le \gcd \set {a, b}$ Definition of Greatest Common Divisor of Integers

Thus:

$\gcd \set {a, b} = \gcd \set {b, r}$

$\blacksquare$