Euclid's Lemma: Proof and Application

1. The Power of Primes

Euclid's Lemma makes a very specific and powerful claim. It states:

If $p$ is a prime number and $p$ divides the product of two integers $a$ and $b$, then $p$ must divide $a$ or $p$ must divide $b$. (Symbolically: If $p|ab$, then $p|a$ or $p|b$).

The condition that $p$ must be prime is not a minor detail—it is the entire foundation upon which the lemma rests. Without it, the statement falls apart. To see why this is so critical, let's consider a quick counterexample.

This simple check confirms that the property of "indivisibility" that defines primes is essential. A prime cannot be "split" across a product without fully dividing one of the factors.

2. The Proof via Bézout's Identity

Now, let's construct the formal proof. The argument is a beautiful piece of logic that directly leverages what we learned in the last lesson about Bézout's Identity. The strategy is to assume that the prime $p$ doesn't divide one of the factors (say, $a$) and then use this assumption to force the conclusion that it must divide the other factor ($b$).

You saw a preview of this proof in our last lesson. To solidify your understanding, let's walk through it again with a couple of excellent resources that present the argument with exceptional clarity.

First, here is the concise, text-based proof from the "Olympiad Number Theory" resource.

To see this argument unfolded step-by-step, the following video by Michael Penn is an ideal guide. He meticulously constructs the proof from first principles.

This proof is a masterclass in using the structural properties of integers. We didn't compute anything; instead, we used the existence of a linear combination guaranteed by Bézout's Identity to prove a fundamental property of divisibility.

3. A Note on Circular Reasoning

When exploring proofs of Euclid's Lemma, you might encounter an alternative argument that uses the Fundamental Theorem of Arithmetic (FTA), which states that every integer has a unique prime factorization.

This argument is very intuitive:

1. Assume $p|ab$.
2. Write out the unique prime factorizations of $a$ and $b$.
3. The prime factorization of $ab$ is simply the combination of these two factorizations.
4. Since $p$ divides $ab$, $p$ must appear in the prime factorization of $ab$.
5. Therefore, $p$ must have been a factor in the original factorization of either $a$ or $b$.

This line of reasoning is compelling. However, it contains a subtle but critical logical flaw. Let's watch a video that presents this proof and see if you can spot the issue.

The issue is one of circular reasoning. The uniqueness part of the Fundamental Theorem of Arithmetic—the very idea that a number has only one set of prime factors—is itself proven using Euclid's Lemma! Therefore, using the FTA to prove Euclid's Lemma is assuming the truth of a more complex statement to prove one of its own foundational components.

This is a fantastic example of the care required in mathematical proofs. While the FTA-based argument provides a strong intuition, the Bézout's Identity proof is the logically sound one, as it builds directly from more basic axioms (the Division Algorithm and its consequences).

4. Applications and Generalizations

With a solid proof in hand, let's turn to applying the lemma. Its most direct use is in problems involving divisibility by primes.

A simple, but important, extension is to generalize the lemma from a product of two integers to a product of many.

If a prime $p$ divides the product $a_1{a}_2\cdots a_n$, then $p$ must divide at least one of the factors $a_i$.

This is typically proven by induction, applying the base case ($p|a_1{a}_2$) repeatedly. You can see the formal statement of this in the following resource.

This generalization is exactly what we need for the lemma's crowning application: proving the uniqueness of prime factorizations. As a preview of our next module, let's see how this works.

This application demonstrates why Euclid's Lemma is not just another result, but a cornerstone of number theory. It provides the logical key to lock in the structure of unique factorization.

Conclusion

In this lesson, we took a deep, principled dive into one of number theory's most fundamental results.

Key Takeaways:

• Euclid's Lemma states that if a prime $p$ divides a product $ab$, it must divide at least one of the factors, $a$ or $b$. The primality of $p$ is essential.
• The most rigorous proof relies on Bézout's Identity. By assuming $p\nmid a$, we establish $\text{gcd}(a,p)=1$, which allows us to construct a linear combination that forces the conclusion $p|b$.
• Attempting to prove Euclid's Lemma using the Fundamental Theorem of Arithmetic leads to circular reasoning, as the lemma itself is required to prove the uniqueness part of the FTA.
• The primary application of Euclid's Lemma is to prove the uniqueness of prime factorizations, which forms the bedrock of much of number theory.

We have now established the major pillars of basic divisibility: the Division Algorithm, the Euclidean Algorithm, Bézout's Identity, and Euclid's Lemma. In our next and final lesson of this module, we will round out our toolkit by formally defining the Least Common Multiple (LCM) and exploring its deep and useful relationship with the Greatest Common Divisor.