Divisors of Product of Coprime Integers

From ProofWiki

Jump to: navigation, search

Contents

[edit] Theorem

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

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


[edit] 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.


[edit] 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


[edit] 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

Personal tools