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$ noteThat 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 Bézout’s theorem there are integers $x, y$ such that $ax+py = 1$.

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$.

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$. <div><div>

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. (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.

Euclid's Lemma on prime numbers

Proof

Elementary proof

More abstract proof

Converse is false

Why is this important?