Sum of Integer Combinations is Integer Combination
Jump to navigation
Jump to search
Lemma
Let $a, b \in \Z$ be integers.
Let $S = \set {a x + b y: x, y \in \Z}$ be the set of integer combinations of $a$ and $b$.
Let $u \in S$ and $v \in S$.
Then $u + v \in S$.
Proof
As both $u, v \in S$, $u$ and $v$ can be expressed as:
\(\ds u\) | \(=\) | \(\ds a x_1 + b y_1\) | ||||||||||||
\(\ds v\) | \(=\) | \(\ds a x_2 + b y_2\) |
where $x_1, x_2, y_1, y_2$ are integers.
Then:
\(\ds u + v\) | \(=\) | \(\ds a x_1 + b y_1 + a x_2 + b y_2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds a \paren {x_1 + x_2} + b \paren {y_1 + y_2}\) |
As Integer Addition is Closed, both $x_1 + x_2$ and $y_1 + y_2$ are integers.
Hence the result.
$\blacksquare$
Sources
- 1982: Martin Davis: Computability and Unsolvability (2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Lemma $1$