Euclid's Proof of Infinite Primes

1. Euclid's Proof: An Undisputed Classic

The theorem that there are infinitely many primes is a cornerstone of number theory. The most famous proof is a masterpiece of logical deduction. It is often presented as a proof by contradiction, a method you'll find indispensable in your mathematical journey.

The NPTEL video from IIT Bombay provides an excellent walkthrough of this argument. The lecturer, Prof. Shripad Garge, begins by explaining the logic of proof by contradiction before applying it to our theorem.

Let's summarize the core steps of the proof by contradiction you just saw:

1. Assumption: Assume the opposite of what we want to prove. Let's assume there is a finite number of primes. We can list them all: $p_1,p_2,p_3,\dots ,p_k$.
2. Construction: Create a new number, $N$, by multiplying all these primes together and adding 1.
   $N=(p_1\cdot p_2\cdot p_3\cdots p_k)+1$
3. Analysis: This number $N$ is greater than 1, so it must have a prime factor (as established in the lemma). Let's call this prime factor $p$.
4. The Contradiction: According to our initial assumption, $p$ must be one of the primes in our complete list $\{p_1,p_2,\dots ,p_k\}$. However, by the way we constructed $N$, if you divide $N$ by any of the primes $p_i$ in our list, you will always get a remainder of 1. Therefore, none of the primes $p_1,p_2,\dots ,p_k$ can be a factor of $N$. This means the prime factor $p$ is not on our supposedly complete list. This is a contradiction.
5. Conclusion: Our initial assumption that the set of primes is finite must be false. Therefore, there are infinitely many primes.

2. A Common Misconception

A frequent point of confusion in this proof is the nature of the number $N=p_1{p}_2\cdots p_k+1$. It is tempting to think that this number must itself be prime. This is not what the proof claims, and it is not always true.

For example:

• $2\cdot 3+1=7$ (prime)
• $2\cdot 3\cdot 5+1=31$ (prime)
• $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509$ (composite)

The proof's logic is more subtle: $N$ is not divisible by any of the primes used to construct it. Therefore, its prime factors (whether it's prime itself or composite) must be new primes, not in the original list.

This popular Numberphile video gives a very quick, intuitive summary of the proof that emphasizes this point correctly.

The following resource provides further excellent clarification on this common mistake and also introduces a slightly different, and perhaps more direct, way to frame the argument.

As Michael Hardy points out in that resource, Euclid's original argument wasn't strictly a proof by contradiction. It can be seen as a constructive method: For any finite set of primes $S$, the number $1+{\prod }_{p\in S}p$ must have prime factors not in $S$. Therefore, no finite set of primes can be complete. This aligns well with your preference for first-principles thinking, as it's a direct demonstration rather than a refutation of a false premise.

3. Variations on Euclid's Argument

The true power of a mathematical idea often lies in its generalizability. The logic of Euclid's proof can be adapted to show that there are infinite primes within certain families of numbers, specifically in arithmetic progressions. This is a common theme in Olympiad-level problems.

Let's explore two examples using a construction similar to Euclid's. The following text from Keith Conrad's lecture notes at UConn is an excellent resource for these kinds of proofs.

These proofs show that the core idea—constructing a number that must have a certain type of prime factor not on an initial list—is a flexible and powerful tool.

There are other constructions as well. A particularly elegant one uses factorials. The NPTEL video you watched earlier contains a short segment on this alternative proof.

The logic here is beautifully simple: for any integer $n$, the number $n!+1$ is not divisible by any integer from 2 to $n$. Therefore, any prime factor of $n!+1$ must be greater than $n$. Since we can do this for any $n$, there cannot be a largest prime.

4. A Glimpse of Other Methods

Euclid's proof is combinatorial and algebraic in nature. However, other proofs exist that draw from different branches of mathematics, revealing deep and unexpected connections. You don't need to master these now, but seeing them will broaden your intellectual landscape.

1. Euler's Proof (Analysis): Leonhard Euler connected the primes to the world of infinite series. He showed that the sum of the reciprocals of all integers (the harmonic series) can be expressed as a product over all primes:
   ${\sum }_{n=1}^{\infty }\frac{1}{n}={\prod }_{p\text{ prime}}\frac{1}{1-1/p}$
   The left side is famously divergent (it goes to infinity). If there were only finitely many primes, the product on the right would be a finite value. This contradiction proves there must be infinitely many primes. This proof is the foundation of a whole field called analytic number theory.

2. Erdős's Proof (Combinatorics): Paul Erdős provided a wonderfully clever proof using a simple counting argument. He showed that if you assume there are finitely many primes, you can't actually generate all the integers up to some large number $N$, leading to a contradiction.

These alternative proofs are discussed in the same notes by Keith Conrad.

Conclusion

Today we have explored one of the most fundamental truths about numbers: the set of primes is infinite.

Key Takeaways:

• Euclid's classic proof shows that for any finite list of primes, one can always construct a number whose prime factors are not on that list.
• The proof does not claim that the number $p_1\cdots p_k+1$ is itself prime, only that it is not divisible by any of $p_1,\dots ,p_k$.
• The core idea of Euclid's proof is a flexible technique that can be adapted to prove the infinitude of primes in specific arithmetic progressions, like $4k+3$ and $4k+1$.
• Alternative proofs, like those by Euler and Erdős, demonstrate the deep interconnectedness of different mathematical fields.

We have now concluded our second module, which focused on the consequences of the Fundamental Theorem of Arithmetic. We've defined primes, established their uniqueness as factors, analyzed their exponents to characterize powers, and now, proven their infinitude. With this solid foundation, we are ready to apply these tools to solve equations.

In our next lesson, we will begin Module 3 by investigating Linear Diophantine Equations. We will learn how to use the GCD and Bézout's Identity—concepts from our very first module—to determine when an equation of the form $ax+by=c$ has integer solutions, and how to find all of them. This will be our first major application of the theoretical machinery we have been building.