Integer Coprime to Factors is Coprime to Whole/Proof 2

Theorem

Let $a, b, c \in \Z$ be integers.

Let:

$a \perp b$

$a \perp c$

where $\perp$ denotes coprimality.

Then:

$a \perp b c$

In the words of Euclid:

If two numbers be prime to any number, their product also will be prime to the same.

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

Proof

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

We have:

\(\ds a\)

\(\perp\)

\(\ds b\)

\(\text {(1)}: \quad\)

\(\ds \leadsto \ \ \)

\(\ds \exists x, y \in \Z: \, \)

\(\ds 1\)

\(=\)

\(\ds a x + b y\)

Integer Combination of Coprime Integers

\(\ds a\)

\(\perp\)

\(\ds c\)

\(\ds \leadsto \ \ \)

\(\ds \exists u, v \in \Z: \, \)

\(\ds 1\)

\(=\)

\(\ds a u + c v\)

Integer Combination of Coprime Integers

\(\ds \)

\(=\)

\(\ds \paren {a x + b y} \paren {a u + c v}\)

from $(1)$

\(\ds \)

\(=\)

\(\ds a^2 u x + a c v x + a b y u + b c y v\)

multiplying out

\(\ds \)

\(=\)

\(\ds a \paren {a u x + c v x + b y u} + b c \paren {y v}\)

rearranging

\(\ds \leadsto \ \ \)

\(\ds a\)

\(\perp\)

\(\ds b c\)

Integer Combination of Coprime Integers

$\blacksquare$

Sources

• 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $16 \ \text {(a)}$