Euclid's theorem

Euclid's theorem is an 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 many different ways to prove that there are endless prime numbers. This idea helps us understand how numbers work and why they are 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.

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 in one way 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.

Erdős's proof

Paul Erdős gave a way to show that there are infinitely many prime numbers. He used a big idea called the fundamental theorem of arithmetic. This theorem tells us that every whole number bigger than 1 can be written as a special mix 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 if you look at numbers up to a certain size, you will always find more primes than you might expect. He proved that the number of primes up to any number N is always bigger than a value linked to the logarithm of N. This means that primes never stop — no matter how big a number you choose, there are always more primes out there.

Furstenberg's proof

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

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

Furstenberg looked at all whole numbers, both positive and negative. He gave them a special structure. He studied groups of numbers that repeat in patterns. By looking at these patterns, he showed that if there were only a few prime numbers, it would not make sense. His proof helps us see 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 that can be divided by known primes. It 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 problem.

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