GCD with Remainder

From ProofWiki

Jump to: navigation, search

Theorem

Let $a, b \in \Z$.

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

Then $\gcd \left\{{a, b}\right\} = \gcd \left\{{b, r}\right\}$

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

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $		$\displaystyle \gcd \left\{ {a, b}\right\} \backslash a \land \gcd \left\{ {a, b}\right\} \backslash b$	$\displaystyle $	$\displaystyle $	$\displaystyle $	GCD is a common divisor
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \gcd \left\{ {a, b}\right\} \backslash \left({a - q b}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Common Divisor Divides Integer Combination
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \gcd \left\{ {a, b}\right\} \backslash r$	$\displaystyle $	$\displaystyle $	$\displaystyle $	as $r = a - q b$
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \gcd \left\{ {a, b}\right\} \le \gcd \left\{ {b, r}\right\}$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of $\gcd \left\{ {b, r}\right\}$ as the greatest common divisor of $b$ and $r$

The argument works the other way about:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $		$\displaystyle \gcd \left\{ {b, r}\right\} \backslash b \land \gcd \left\{ {b, r}\right\} \backslash r$	$\displaystyle $	$\displaystyle $	$\displaystyle $	GCD is a common divisor
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \gcd \left\{ {b, r}\right\} \backslash \left( {q b + r}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Common Divisor Divides Integer Combination
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \gcd \left\{ {b, r}\right\} \backslash a$	$\displaystyle $	$\displaystyle $	$\displaystyle $	as $a = q b + r$
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \gcd \left\{ {b, r}\right\} \le \gcd \left\{ {a, b}\right\}$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of $\gcd \left\{ {a, b}\right\}$ as the greatest common divisor of $a$ and $b$

Thus $\gcd \left\{{a, b}\right\} = \gcd \left\{{b, r}\right\}$.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \gcd \left\{ {a, b}\right\} \backslash a \land \gcd \left\{ {a, b}\right\} \backslash b\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	GCD is a common divisor
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \gcd \left\{ {a, b}\right\} \backslash \left({a - q b}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Common Divisor Divides Integer Combination
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \gcd \left\{ {a, b}\right\} \backslash r\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	as $r = a - q b$
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \gcd \left\{ {a, b}\right\} \le \gcd \left\{ {b, r}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of $\gcd \left\{ {b, r}\right\}$ as the greatest common divisor of $b$ and $r$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \gcd \left\{ {b, r}\right\} \backslash b \land \gcd \left\{ {b, r}\right\} \backslash r\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	GCD is a common divisor
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \gcd \left\{ {b, r}\right\} \backslash \left( {q b + r}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Common Divisor Divides Integer Combination
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \gcd \left\{ {b, r}\right\} \backslash a\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	as $a = q b + r$
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \gcd \left\{ {b, r}\right\} \le \gcd \left\{ {a, b}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of $\gcd \left\{ {a, b}\right\}$ as the greatest common divisor of $a$ and $b$