Common Divisor Divides Integer Combination/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $c$ be a common divisor of two integers $a$ and $b$.

That is:

$a, b, c \in \Z: c \divides a \land c \divides b$


Then $c$ divides any integer combination of $a$ and $b$:

$\forall p, q \in \Z: c \divides \paren {p a + q b}$


Proof

\(\ds c\) \(\divides\) \(\ds a\)
\(\ds \leadsto \ \ \) \(\, \ds \exists x \in \Z: \, \) \(\ds a\) \(=\) \(\ds x c\) Definition of Divisor of Integer
\(\ds c\) \(\divides\) \(\ds b\)
\(\ds \leadsto \ \ \) \(\, \ds \exists y \in \Z: \, \) \(\ds b\) \(=\) \(\ds y c\) Definition of Divisor of Integer
\(\ds \leadsto \ \ \) \(\, \ds \forall p, q \in \Z: \, \) \(\ds p a + q b\) \(=\) \(\ds p x c + q y c\) Substitution for $a$ and $b$
\(\ds \) \(=\) \(\ds \paren {p x + q y} c\) Integer Multiplication Distributes over Addition
\(\ds \leadsto \ \ \) \(\, \ds \exists z \in \Z: \, \) \(\ds p a + q b\) \(=\) \(\ds z c\) where $z = p x + q y$
\(\ds \leadsto \ \ \) \(\ds c\) \(\divides\) \(\ds \paren {p a + q b}\) Definition of Divisor of Integer

$\blacksquare$


Sources