Divisors of Product of Coprime Integers

Theorem

Let $a \backslash b c$, where $b \perp c$.

Then $a = r s$, where $r \backslash b$ and $s \backslash c$.

Corollary

Let $p$ be a prime.

Let $p \backslash b c$, where $b \perp c$.

Then $p \backslash b$ or $p \backslash c$, but not both.

Proof

Let $r = \gcd \left\{{a, b}\right\}$.

By Divide by GCD for Coprime Integers, $\exists s, t \in \Z: a = r s \land b = r t \land \gcd \left\{{s, t}\right\} = 1$.

So we have written $a = r s$ where $r$ divides $b$.

We now show that $s$ divides $c$.

Since $a$ divides $b c$ there exists $k$ such that $b c = k a$.

Substituting for $a$ and $b$:

$r t c = k r s$

which gives:

$t c = k s$

So $s$ divides $t c$.

But $s \perp t$ so by Euclid's Lemma $s \backslash c$ as required.

$\blacksquare$

Proof of Corollary

From the main result, $p = r s$, where $r \backslash b$ and $s \backslash c$.

But as $p$ is prime, either:

$r = 1$ and $s = p$, or:

$r = p$ and $s = 1$.

So $p \backslash b$ or $p \backslash c$.

But $p$ can not divide both as $b \perp c$.

$\blacksquare$