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.