AI Tutor
As you travel up the number line, prime numbers become rarer and rarer — between 1 and 100 there are 25 primes, but between 10,000,000 and 10,000,100 there are only 2.
This thinning out makes you wonder: does the supply of primes eventually dry up completely, or do they keep appearing forever?

The Divisibility Principle

Before tackling infinity, we need one foundational rule about division. A prime number is an integer greater than 1 whose only positive divisors are 1 and itself.
If an integer dd divides both integer aa and integer bb, it must also divide their difference, b−ab - a.
This means no integer d>1d > 1 can divide both a number PP and its immediate successor P+1P + 1, because their difference is (P+1)−P=1(P + 1) - P = 1.
How can this simple gap of 1 destroy the idea of a finite list of primes?

Euclid's Setup

Around 300 BCE, the Greek mathematician Euclid resolved this question in Book IX of his Elements using a proof by contradiction.
We begin by assuming the opposite of what we want to prove: suppose there are only finitely many primes, and write them all in a complete list S={p1,p2,p3,…,pn}S = \{p_1, p_2, p_3, \dots, p_n\}.
Now we construct a new integer NN by multiplying every single prime in our list together and adding 1: N=(p1⋅p2⋅p3⋯pn)+1N = (p_1 \cdot p_2 \cdot p_3 \cdots p_n) + 1