Set of Integer Combinations equals Set of Multiples of GCD
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: \, \) | \(\ds d\) | \(=\) | \(\ds p a + q b\) | Bézout's Identity | ||||||||||
\(\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: \, \) | \(\ds 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
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Corollary $\text {2-2}$
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $2$: Some Properties of $\Z$: Exercise $2.4$
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Theorem $2 \text{-} 3$: Corollary
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $13 \ \text {(a)}$
- 1982: Martin Davis: Computability and Unsolvability (2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Lemma $2$