Euclid's Lemma on prime numbers

Eu­clid’s lemma states that if \(p\) is a prime num­ber, which di­vides a product \(ab\), then \(p\) di­vides at least one of \(a\) or \(b\).


Ele­men­tary proof

Sup­pose \(p \mid ab\) noteThat is, \(p\) di­vides \(ab\)., but \(p\) does not di­vide \(a\). We will show that \(p \mid b\).

In­deed, \(p\) does not di­vide \(a\), so the great­est com­mon di­vi­sor of \(p\) and \(a\) is \(1\) (ex­er­cise: do this with­out us­ing in­te­ger fac­tori­sa­tion); so by Bé­zout’s the­o­rem there are in­te­gers \(x, y\) such that \(ax+py = 1\).

We are not al­lowed to use the fact that we can fac­torise in­te­gers, be­cause we need “$p \mid ab$ im­plies \(p \mid a\) or \(p \mid b\)” as a lemma on the way to­wards the proof of the fun­da­men­tal the­o­rem of ar­ith­metic (which is the the­o­rem that tells us we can fac­torise in­te­gers).

Re­call that the high­est com­mon fac­tor of \(a\) and \(p\) is defined to be the num­ber \(c\) such that:

  • \(c \mid a\);

  • \(c \mid p\);

  • for any \(d\) which di­vides \(a\) and \(p\), we have \(d \mid c\).

Eu­clid’s al­gorithm tells us that \(a\) and \(p\) do have a (unique) high­est com­mon fac­tor.

Now, if \(c \mid p\), we have that \(c = p\) or \(c=1\), be­cause \(p\) is prime. But \(c\) is not \(p\) be­cause we also know that \(c \mid a\), and we already know \(p\) does not di­vide \(a\).

Hence \(c = 1\). <div><div>

But mul­ti­ply­ing through by \(b\), we see \(abx + pby = b\). \(p\) di­vides \(ab\) and di­vides \(p\), so it di­vides the left-hand side; hence it must di­vide the right-hand side too. That is, \(p \mid b\).

More ab­stract proof

This proof uses much more the­ory but is cor­re­spond­ingly much more gen­eral, and it re­veals the im­por­tant fea­ture of \(\mathbb{Z}\) here.

\(\mathbb{Z}\), viewed as a ring, is a prin­ci­pal ideal do­main. (Proof.) The the­o­rem we are try­ing to prove is that the ir­re­ducibles in \(\mathbb{Z}\) are all prime in the sense of ring the­ory.

But it is gen­er­ally true that in a PID, “prime” and “ir­re­ducible” co­in­cide (proof), so the re­sult is im­me­di­ate.

Con­verse is false

Any com­pos­ite num­ber \(pq\) (where \(p, q\) are greater than \(1\)) di­vides \(pq\) with­out di­vid­ing \(p\) or \(q\), so the con­verse is very false.

Why is this im­por­tant?

This lemma is a non­triv­ial step on the way to prov­ing the fun­da­men­tal the­o­rem of ar­ith­metic; and in fact in a cer­tain gen­eral sense, if we can prove this lemma then we can prove the FTA. It tells us about the be­havi­our of the primes with re­spect to prod­ucts: we now know that the primes “can­not be split up be­tween fac­tors” of a product, and so they be­have, in a sense, “ir­re­ducibly”.

The lemma is also of con­sid­er­able use as a tiny step in many differ­ent proofs.


  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.