Euclid's lemma states that if is a prime number, which divides a product , then divides at least one of or .
Suppose [1], but does not divide . We will show that .
Indeed, does not divide , so the greatest common divisor of and is (exercise: do this without using integer factorisation); so by Bézout's theorem there are integers such that .
We are not allowed to use the fact that we can factorise integers, because we need " implies or " 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 and is defined to be the number such that:
Euclid's algorithm tells us that and do have a (unique) highest common factor.
Now, if , we have that or , because is prime. But is not because we also know that , and we already know does not divide .
Hence .
But multiplying through by , we see . divides and divides , so it divides the left-hand side; hence it must divide the right-hand side too. That is, .
This proof uses much more theory but is correspondingly much more general, and it reveals the important feature of here.
, viewed as a ring, is a principal ideal domain. (Proof.) The theorem we are trying to prove is that the irreducibles in 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.
Any composite number (where are greater than ) divides without dividing or , so the converse is very false.
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.
That is, divides .