Main Index
Number Theory
Sequences
Primes
Subject Index
comment on the page
Euclid's lemma (also known as Euclid's first theorem) is the name of Proposition 30 in Book VII of Euclid's Elements .
If two numbers, multiplied by one another make some number, and any prime number measures the product, then it also measures one of the original numbers.
In modern notation:
If a prime number divides a product
of two integers
and
, then it divides at least one of the factors
.
In symbols if is prime and
, then either
or
.
The Euclid's lemma demonstrates the important role of prime numbers in the divisibility of integers. For instance, its consequence is the fundamental theorem of arithmetic
.
If we resign to use some sophisticated arguments1, the proof of the lemma is surprisingly not so easy as straightforward is its statement
Assume the lemma is false. Take for the smallest prime number
for which there are
and
such that
but
and simultaneously
. We can suppose that
and
are positive. For this choice of
, take form the set of such pairs
that with the smallest possible
.
It is easy to see that . Not only this,
is even a prime. Otherwise,
with
. Then
. Since
, and
was chosen the smallest, the Lemma is true for the triple
. Therefore
or
. The first case is impossible, for if
, then also
, what contradicts the choice of
. Therefore
. Since d < a, we may again apply the Lemma and get that either
or
. The case
contradicts the hypothesis. But if
then also
. Since
, this contradicting the choice of
. Consequently
is a prime.
Clearly, . If
, take
. Then
. We also have
, but
was chosen the smallest possible. Therefore the Lemma is applicable to the product
. Consequently either
or
. The second possibility is excluded by our assumption, therefore
. But the
, a contradiction. Therefore
.
Now we have, , i.e.
, for some
. But here
is prime,
, and
is the smallest prime for which the Lemma is false. Therefore the Lemma is true for
. Since
, either
or
. The first divisibility relation is impossible due to the fact that
. Consequently
.
Then we write for some
, and
, or
. In other words,
, but this is impossible due to our choice of
, and Lemma is proved.
1 | In most textbooks Euclid’s lemma is proved as a consequence of Bezout’s theorem ![]() |
Cite this web-page as:
Štefan Porubský: Euclid’s Lemma.