# 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

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