Euclid's Lemma on prime numbers

Discussion2

1

Written by Patrick Stevens last updated 7th Aug 2016

Name

Euclid's lemma states that if

p

is a prime number, which divides a product , then divides at least one of or .

Proof

Elementary proof

Suppose

p \mid ab

^[1], but does not divide . We will show that .

Indeed,

p

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 .

Show solution to exercise

We are not allowed to use the fact that we can factorise integers, because we need "

p \mid ab

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

a

and is defined to be the number 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 do have a (unique) highest common factor.

Now, if

c \mid p

, we have that or , because is prime. But is not because we also know that , and we already know does not divide .

Hence

c = 1

.

But multiplying through by

b

, we see . divides and divides , so it divides the left-hand side; hence it must divide the right-hand side too. That is, .

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 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 are greater than ) divides without dividing or , 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.

Summaries

You can edit summaries by clicking on them, reorder them by dragging, or add a new one (up to 3). By default you should avoid creating more than one summary unless the subject matter benefits substantially from multiple kinds of explanation.

Summary

The prime numbers have a special property that they "can't be distributed between terms of a product": if is a prime dividing a product $a b$ 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$ ".

Tab title

Technical

Let be a prime natural number. Then $p ∣ a b$ implies $p ∣ a$ or $p ∣ b$ .

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

Proof

Elementary proof

Suppose $p ∣ a b$ ^[1], but $p$ does not divide $a$ . We will show that $p ∣ 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 $a x + p y = 1$ .

Show solution to exercise

We are not allowed to use the fact that we can factorise integers, because we need " $p ∣ a b$ implies $p ∣ a$ or $p ∣ 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 ∣ a$ ;

$c ∣ p$ ;

for any $d$ which divides $a$ and $p$ , we have $d ∣ c$ .

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

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

Hence $c = 1$ .

But multiplying through by $b$ , we see $a b x + p b y = b$ . $p$ divides $a b$ and divides $p$ , so it divides the left-hand side; hence it must divide the right-hand side too. That is, $p ∣ b$ .

More abstract proof

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

$Z$ , viewed as a ring, is a principal ideal domain. (Proof.) The theorem we are trying to prove is that the irreducibles in $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 $p q$ (where $p, q$ are greater than $1$ ) divides $p q$ 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.

^{^︎}
That is, $p$ divides $a b$ .

Parents:

Mathematics