# Integer Coprime to all Factors is Coprime to Whole

## Theorem

Let $a, b \in \Z$.

Let $\displaystyle b = \prod_{j \mathop = 1}^r b_j$

Let $a$ be coprime to each of $b_1, \ldots, b_r$.

Then $a$ is coprime to $b$.

In the words of Euclid:

(*The Elements*: Book $\text{VII}$: Proposition $24$)

## Proof 1

From Integer Combination of Coprime Integers:

- $\forall j \in \set {1, 2, \ldots, r}: a x_j + b_j y_j = 1$

for some $x_j, y_j \in \Z$.

Thus:

- $\displaystyle \prod_{j \mathop = 1}^r b_j y_j = \prod_{j \mathop = 1}^r \paren {1 - a x_j}$

But $\displaystyle \prod_{j \mathop = 1}^r \paren {1 - a x_j}$ is of the form $1 - a z$.

Thus:

\(\displaystyle \prod_{j \mathop = 1}^r b_j \prod_{j \mathop = 1}^r y_j\) | \(=\) | \(\displaystyle 1 - a z\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle a z + b y\) | \(=\) | \(\displaystyle 1\) | where $\displaystyle y = \prod_{j \mathop = 1}^r y_j$ |

and so, by Integer Combination of Coprime Integers, $a$ and $b$ are coprime.

$\blacksquare$

## Proof 2

*This proof follows the structure of Euclid's proof, if not its detail.*

Let $a, b, c \in \Z$ such that $c$ is coprime to each of $a$ and $b$.

Let $d = a b$.

Aiming for a contradiction, suppose $c$ and $d$ are not coprime.

Then:

- $\exists e \in \Z_{>1}: e \mathrel \backslash c, e \mathrel \backslash d$

We have that $c \perp a$ and $e \mathrel \backslash c$

From Proposition $23$ of Book $\text{VII} $: Divisor of One of Coprime Numbers is Coprime to Other:

- $e \perp a$

As $e \mathrel \backslash d$ it follows by definition of divisibility that:

- $\exists f \in \Z: e f = d$

We also have that:

- $a b = d$

So:

- $a b = e f$

But from Proposition $19$ of Book $\text{VII} $: Relation of Ratios to Products:

- $e : a = b : f$

or in more contemporary language:

- $\dfrac a e = \dfrac b f$

But $a \perp e$.

From Proposition $21$ of Book $\text{VII} $: Coprime Numbers form Fraction in Lowest Terms, $\dfrac a e$ is in canonical form.

From Proposition $20$ of Book $\text{VII} $: Ratios of Fractions in Lowest Terms:

- $e \mathrel \backslash b$

But we already have that:

- $e \mathrel \backslash c$

So $e$ is a divisor of both $b$ and $c$.

But this is a contradiction of the assertion that $c$ and $b$ are coprime.

Hence the result.

$\blacksquare$