A prime number is a positive integer that has exactly 2 positive divisors. The first few prime numbers are
When we go to larger positive integers, we notice that prime numbers get more and more scarce. Is it possible that at some point, we have found all the prime numbers and thus everything larger is composite? The answer turns out to be no:
There are infinitely many primes.
There have been many proofs of this fact. The earliest, which gave rise to the name, was by Euclid of Alexandria in around 300 B.C. This page lists several proofs of this theorem.
For any finite set of primes , Euclid considered the number
has a prime divisor (every integer has at least one prime divisor). But is not equal to any of the If were equal to any of the , then would have to divide , which is impossible. So for any finite set of prime numbers, it is possible to find another prime that is not in that set.
In other words, a finite set of primes cannot be the collection of all prime numbers.
Notice that Euclid's original proof was a direct proof, not a proof by contradiction.
Euler started his proof by assuming that there are only finitely many primes . Then he considered
On the other hand, expanding the product and using the fact that every integer can be uniquely expressed as a product of primes, we get
It is apparent that converges. Here, we have used the formula for the infinite geometric series:
Note that is the infamous harmonic series and it diverges, which is a contradiction!
So, there cannot be finitely many primes.
This is a relatively new proof that was first published in 2005. Unlike the last two proofs, which rely on contradiction, this proof makes use of induction.
First, take any number . For simplicity, we can just say that it's prime. As in Euclid's proof, we can add to to get a new number, . These two integers must be coprime* and thus their product has at least two different prime factors. Now take , which we know has two prime factors, and repeat this process:
and must likewise be coprime and thus have at least three different prime factors. This can be continued indefinitely.
* Take and Assume that there is a factor which divides and let Dividing by gives us which cannot hold for integers unless in which case is just a trivial factor. Thus, the greatest common divisor between these two numbers is , making them coprime.
For this proof, we need to know what Fermat numbers are. Fermat numbers are of the form where is a non-negative integer. The first few Fermat numbers are .
We'll prove that any two Fermat numbers are relatively prime. Since there are an infinite number of Fermat numbers, this will prove that there are an infinite number of primes.
Take a look at the following relation:
This is not hard to prove using induction. For , we have and . So is true for .
Assume that it is true for any . Then
So, is true for all positive integers .
We're actually done proving that any two Fermat numbers are co-prime since if and (with ) have a common factor , then from , . This means equals either or . But cannot be equal to since all Fermat numbers are odd. That means and and are co-prime.
From that we can say there are infinitely many primes.
It is enough to find an infinite sequence of positive integers that are pairwise relatively prime (i.e. without a common prime factor). So, if is a prime dividing , if is a prime dividing , etc., then are all different.
If and are relatively prime integers with , the sequence defined by the recursive relation
consists of pairwise relatively prime positive integers. In the best situation, i.e. when and , the sequence is in fact the sequence of Fermat numbers: .
Similarly, if is odd and
then again the integers are pairwise relatively prime.
Let be integers such that and let be primes satisfying . Suppose that .
Then by the fundamental theorem, every integer such that may be written in a unique way in the form
where . Counting all the possibilities, it follows that
and this is absurd. So .
Choose . From for every , it follows that .
Thus, there exist at least primes such that . Since may be taken arbitrarily large, this shows that there are infinitely many primes.
Suppose there are finitely many prime numbers, . By fundamental theorem of arithmetic, each positive integer can be represented uniquely as where are nonnegative integers. Denote the mapping mapping to . Note that is clearly a bijection.
Note that since , we have for all , and thus for all . Thus . Thus if we fix some large and let , all components of must be at most . Thus among , there are at most distinct values. But since is bijective, we need distinct values. Thus we need . This is clearly false for large enough . So there are infinitely many prime numbers.
On the set of integers , define a topology having subbase of all non-constant arithmetic progressions (unbounded in both directions). It can be shown that all open sets in this topology are either infinite or empty.
For each prime and integer , define to be the set of all integers in the arithmetic progression with difference , containing . We can easily see that is precisely the set of all integers divisible by . Moreover, we have . The left-hand side is the union of open sets and thus open; so is closed.
Now suppose there are finitely many prime numbers. Then the union of all , being a finite union of closed sets, is also closed. But by definition of prime numbers, the only integers not divisible by any prime are the units 1 and -1. Thus the complement of is . Being the complement of a closed set, should be open; but this is a finite non-empty set, contradicting our result that open sets in this topology are either infinite or empty. Thus there must be infinitely many prime numbers.
Despite there being infinitely many prime numbers, it's actually difficult to find a large one. For recreational purposes, people have been trying to find as large prime number as possible. The current largest known prime number is , having 24,862,048 digits. This was found by the Great Internet Mersenne Prime Search project, which uses distributed computing to discover prime numbers in the form , known as Mersenne primes. Mersenne primes are very rare; in fact, it's an open problem whether there are infinitely many Mersenne primes or not. Only 50 are known so far, the largest of which is the above.