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

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

$\blacksquare$


Sources