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

# Proof

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

Parents:

• Mathematics

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

• Out of cu­ri­os­ity, is there any rea­son you are avoid­ing call­ing this lemma by its tra­di­tional name, Eu­clid’s lemma?

• Sim­ply that I didn’t know the name :) I’ll edit it in.