Euclid's theorem

Euclid's theorem is a very important idea in number theory. It tells us that there are infinitely many prime numbers. Prime numbers are special numbers greater than 1 that can only be divided by 1 and themselves, like 2, 3, 5, and 7.

This theorem was first proven by the ancient Greek mathematician Euclid in his famous book called Elements. Since then, mathematicians have found at least 200 different ways to prove that there are endless prime numbers. This idea helps us understand how numbers work and why they are so interesting and useful in many areas of math.

Euclid's proof

Euclid showed in his book Elements that there are infinitely many prime numbers. He used a clever argument: take any list of prime numbers and multiply them all together to get a big number, called P. Then add 1 to get a new number, called q. If q is prime, it's a new prime not on the list. If q isn't prime, it has a prime factor that can't be on the list either, because no prime on the list can divide q without also dividing 1, which is impossible. This means there are always more primes than we can list.

There are many ways to change Euclid's proof. One uses factorials — the product of all numbers up to n. Adding 1 to this product creates a number that can’t be divided by any numbers from 2 to n, so it must have a prime factor bigger than n. This also shows there are infinitely many primes.

Main article: proved this result by contradiction
Main articles: finite set, proof by cases, direct proof
Further information: Torkel Franzén, factorial

Euler's proof

Another proof was created by the Swiss mathematician Leonhard Euler. Euler used a key idea in number theory called the fundamental theorem of arithmetic. This theorem says that every whole number greater than 1 can be written uniquely as a product of prime numbers.

Euler showed that if you take the first few prime numbers and do a special kind of multiplication with them, you end up with a sum that includes every whole number whose prime factors are among those first few primes. This helps prove that there are infinitely many prime numbers, which supports Euclid’s theorem. Euler also discovered that the sum of the reciprocals of all prime numbers never stops growing, which is another way to see that there must be infinitely many primes.

Erdős's proof

Paul Erdős provided a proof using the fundamental theorem of arithmetic. This theorem says that every positive integer can be broken down into a unique combination of prime numbers and a square number. For example, the number 75,600 can be written as 21 times 60 squared.

Erdős showed that by looking at numbers up to a certain size, the number of primes cannot be limited. He proved that the number of primes less than or equal to any number N is always larger than a value related to the logarithm of N. This means that primes never run out — no matter how big a number you pick, there are always more primes to be found.

Furstenberg's proof

Main article: Furstenberg's proof of the infinitude of primes

In the 1950s, mathematician Hillel Furstenberg created a special way to prove that there are infinitely many prime numbers. He used an idea from a branch of math called point-set topology.

Furstenberg looked at the whole set of integers—all positive and negative whole numbers—and gave them a new kind of structure. He defined certain groups of numbers as "open sets" based on patterns that repeat at regular intervals. By studying these patterns, he showed that assuming there are only a certain number of primes leads to a logical contradiction. This clever proof shows, once again, that there are infinitely many prime numbers.

Recent proofs

Many mathematicians have found new ways to prove Euclid's theorem. One method uses a principle called inclusion–exclusion to count numbers divisible by known primes and shows there must be more primes. Another proof uses a fact about factorials, which are products of all numbers up to a certain point, to argue that having only a few primes leads to a contradiction.

There are also proofs that use ideas from data compression and even simple arguments about even and odd numbers. These different proofs show how deep and important Euclid's theorem is in understanding prime numbers.