This post presents a proof of a lemma that is called Euclid’s lemma, which is one of the fundamental properties of prime numbers. Euclid’s lemma is the statement that if a prime number divides a product of two integers, it must divide one of the factors.
This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.
We first state all the tools that we need. The notation refers to the condition that divides . The notation refers to the greatest common divisor (GCD) of and .
Extended Euclidean Algorithm
Let and be integers. Let be the greatest common divisor of and . Then there exist integers and such that .
The extended Euclidean algorithm is discussed in this post.
If and , then .
Proof of Lemma 1
Suppose that and . According to the extended Euclidean algorithm, for some integers and , we have . Multiplying both sides by , we have:
Since divides each term in the left-hand side of this equation, .
If is a prime number and , then or .
If , then we are done. So assume , which implies that . If , , which implies that . Note that the only positive divisors of are and . By Lemma 1, .
We would like to point out that the assumption that is prime is essential in Euclid’s lemma. Note that and .