Integer Combinations Multiples of GCD

From ProofWiki

Jump to: navigation, search

Theorem

The set of all integer combinations of $a$ and $b$ is precisely the set of all integer multiples of the GCD of $a$ and $b$:

$\gcd \left\{{a, b}\right\} \backslash c \iff \exists x, y \in \Z: c = x a + y b$

Let $d = \gcd \left\{{a, b}\right\}$.

Then $d \backslash c \implies \exists m \in \Z: c = m d$.

So:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle \exists p, q \in \Z: d$	$=$	$\displaystyle p a + q b$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Bézout's Lemma
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle c$	$=$	$\displaystyle m d$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle m p a + m q b$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle \left({m p}\right) a + \left({m q}\right) b$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \exists x, y \in \Z: c$	$=$	$\displaystyle x a + y b$	$\displaystyle $	$\displaystyle $	$\displaystyle $

Thus $\gcd \left\{{a, b}\right\} \backslash c \implies \exists x, y \in \Z: c = x a + y b$.

$\Box$

Suppose $\exists x, y \in \Z: c = x a + y b$.

From Common Divisor Divides Integer Combination, we have $\gcd \left\{{a, b}\right\} \backslash \left({x a + y b}\right)$.

It follows directly that $\gcd \left\{{a, b}\right\} \backslash c$ and the proof is finished.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \exists p, q \in \Z: d\)	\(=\)	\(\displaystyle p a + q b\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Bézout's Lemma
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle c\)	\(=\)	\(\displaystyle m d\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle m p a + m q b\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({m p}\right) a + \left({m q}\right) b\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists x, y \in \Z: c\)	\(=\)	\(\displaystyle x a + y b\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)