[summary: The prime numbers have a special property that they "can't be distributed between terms of a product": if $~$p$~$ is a prime dividing a product $~$ab$~$ of integers, then $~$p$~$ wholly divides one or both of $~$a$~$ or $~$b$~$. It cannot be the case that "some but not all of $~$p$~$ divides into $~$a$~$, and the rest of $~$p$~$ divides into $~$b$~$".]

[summary(Technical): Let $~$p$~$ be a prime natural number. Then $~$p \mid ab$~$ implies $~$p \mid a$~$ or $~$p \mid b$~$.]

Euclid's lemma states that if $~$p$~$ is a prime number, which divides a product $~$ab$~$, then $~$p$~$ divides at least one of $~$a$~$ or $~$b$~$.

Proof

Elementary proof

Suppose $~$p \mid ab$~$ %%note:That is, $~$p$~$ divides $~$ab$~$.%%, but $~$p$~$ does not divide $~$a$~$. We will show that $~$p \mid b$~$.

Indeed, $~$p$~$ does not divide $~$a$~$, so the Greatest common divisor of $~$p$~$ and $~$a$~$ is $~$1$~$ (exercise: do this without using integer factorisation); so by [bezouts_theorem Bézout's theorem] there are integers $~$x, y$~$ such that $~$ax+py = 1$~$.

%%hidden(Show solution to exercise): We are not allowed to use the fact that we can factorise integers, because we need "$~$p \mid ab$~$ implies $~$p \mid a$~$ or $~$p \mid b$~$" as a lemma on the way towards the proof of the Fundamental Theorem of Arithmetic (which is the theorem that tells us we can factorise integers).

Recall that the highest common factor of $~$a$~$ and $~$p$~$ is defined to be the number $~$c$~$ such that:

• $~$c \mid a$~$;
• $~$c \mid p$~$;
• for any $~$d$~$ which divides $~$a$~$ and $~$p$~$, we have $~$d \mid c$~$.

[euclidean_algorithm Euclid's algorithm] tells us that $~$a$~$ and $~$p$~$ do have a (unique) highest common factor.

Now, if $~$c \mid p$~$, we have that $~$c = p$~$ or $~$c=1$~$, because $~$p$~$ is prime. But $~$c$~$ is not $~$p$~$ because we also know that $~$c \mid a$~$, and we already know $~$p$~$ does not divide $~$a$~$.

Hence $~$c = 1$~$. %%

But multiplying through by $~$b$~$, we see $~$abx + pby = b$~$. $~$p$~$ divides $~$ab$~$ and divides $~$p$~$, so it divides the left-hand side; hence it must divide the right-hand side too. That is, $~$p \mid b$~$.

More abstract proof

This proof uses much more theory but is correspondingly much more general, and it reveals the important feature of $~$\mathbb{Z}$~$ here.

$~$\mathbb{Z}$~$, viewed as a ring, is a Principal ideal domain. ([integers_is_pid Proof.]) The theorem we are trying to prove is that the irreducibles in $~$\mathbb{Z}$~$ are all prime in the sense of ring theory.

But it is generally true that in a PID, "prime" and "irreducible" coincide (proof), so the result is immediate.

Converse is false

Any composite number $~$pq$~$ (where $~$p, q$~$ are greater than $~$1$~$) divides $~$pq$~$ without dividing $~$p$~$ or $~$q$~$, so the converse is very false.

Why is this important?

This lemma is a nontrivial step on the way to proving the Fundamental Theorem of Arithmetic; and in fact in a certain general sense, if we can prove this lemma then we can prove the FTA. It tells us about the behaviour of the primes with respect to products: we now know that the primes "cannot be split up between factors" of a product, and so they behave, in a sense, "irreducibly".

The lemma is also of considerable use as a tiny step in many different proofs.