# Common Divisor Divides Integer Combination

## Corollary to Common Divisor in Integral Domain Divides Linear Combination

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

### Corollary

$c \divides \paren {a + b}$

### General Result

Let $c$ be a common divisor of a set of integers $A := \set {a_1, a_2, \dotsc, a_n}$.

That is:

$\forall x \in A: c \divides x$

Then $c$ divides any integer combination of elements of $A$:

$\forall x_1, x_2, \dotsc, x_n \in \Z: c \divides \paren {a_1 x_2 + a_2 x_2 + \dotsb + a_n x_n}$

## Proof 1

We have that the Integers form Integral Domain.

The result then follows from Common Divisor in Integral Domain Divides Linear Combination.

$\blacksquare$

## Proof 2

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