# Common Divisor Divides Integer Combination/Proof 2

## 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$