Set of Integer Combinations equals Set of Multiples of GCD

From ProofWiki
Jump to navigation Jump to 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 \set {a, b} \divides c \iff \exists x, y \in \Z: c = x a + y b$


Proof

Necessary Condition

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

Then:

$d \divides c \implies \exists m \in \Z: c = m d$


So:

\(\ds \exists p, q \in \Z: d\) \(=\) \(\ds p a + q b\) Bézout's Lemma
\(\ds \leadsto \ \ \) \(\ds c\) \(=\) \(\ds m d\)
\(\ds \) \(=\) \(\ds m p a + m q b\)
\(\ds \) \(=\) \(\ds \paren {m p} a + \paren {m q} b\)
\(\ds \leadsto \ \ \) \(\ds \exists x, y \in \Z: c\) \(=\) \(\ds x a + y b\)


Thus:

$\gcd \set {a, b} \divides c \implies \exists x, y \in \Z: c = x a + y b$

$\Box$


Sufficient Condition

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

From Common Divisor Divides Integer Combination, we have:

$\gcd \set {a, b} \divides \paren {x a + y b}$

It follows directly that $\gcd \set {a, b} \divides c$ and the proof is finished.

$\blacksquare$


Sources