Euclid's Lemma for Prime Divisors/Proof 2

From ProofWiki
Jump to navigation Jump to search

Lemma

Let $p$ be a prime number.

Let $a$ and $b$ be integers such that:

$p \divides a b$

where $\divides$ means is a divisor of.

Then $p \divides a$ or $p \divides b$.


Proof

Let $p \divides a b$.


Suppose $p \nmid a$.

Then from the definition of prime:

$p \perp a$

where $\perp$ indicates that $p$ and $a$ are coprime.

Thus from Euclid's Lemma it follows that:

$p \divides b$


Similarly, if $p \nmid b$ it follows that $p \divides a$.

So:

$p \divides a b \implies p \divides a$ or $p \divides b$

as we needed to show.

$\blacksquare$


Source of Name

This entry was named for Euclid.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Euclid%27s_Lemma_for_Prime_Divisors/Proof_2&oldid=591709"