Main Index Number Theory Sequences Primes
 Subject Index
comment on the page

Euclid’s lemma

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 typeset structure divides a product typeset structure of two integers typeset structure and typeset structure, then it divides at least one of the factors typeset structure.

In symbols if typeset structure is prime and typeset structure, then either typeset structure ortypeset structure.

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 typeset structure the smallest prime number typeset structure for which there are typeset structure and typeset structure such that  typeset structure but typeset structure and simultaneously typeset structure. We can suppose that typeset structure and typeset structure are positive. For this choice of typeset structure, take form the set of such pairs typeset structure that with the smallest possible typeset structure.

It is easy to see that typeset structure. Not only this, typeset structure is even a prime. Otherwise, typeset structure with typeset structure. Then typeset structure. Since typeset structure, and typeset structure was chosen the smallest, the Lemma is true for the triple typeset structure. Therefore typeset structure or typeset structure. The first case is impossible, for if typeset structure, then also typeset structure, what contradicts the choice of typeset structure.  Therefore typeset structure. Since d < a, we may again apply the Lemma and get that either typeset structure or typeset structure. The case typeset structure contradicts the hypothesis. But if typeset structure then also typeset structure. Since typeset structure, this contradicting the choice of typeset structure. Consequently typeset structure is a prime.

Clearly, typeset structure. If typeset structure, take typeset structure. Then typeset structure. We also have typeset structure, but typeset structure was chosen the smallest possible. Therefore the Lemma is applicable to the product typeset structure. Consequently  either typeset structure or typeset structure. The second possibility is excluded by our assumption, therefore typeset structure. But the typeset structure, a contradiction. Therefore typeset structure.

Now we have, typeset structure, i.e. typeset structure, for some typeset structure. But here typeset structure is prime, typeset structure, and typeset structure is the smallest prime for which the Lemma is false. Therefore the Lemma is true for typeset structure. Since typeset structure, either typeset structure or typeset structure. The first divisibility relation is impossible due to the fact that typeset structure. Consequently typeset structure.

Then we write typeset structure for some typeset structure, and typeset structure, or typeset structure. In other words, typeset structure, but this is impossible due to our choice of typeset structure, and Lemma is proved.

Notes

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.

Page created  .