# Why There Are Infinitely Many Prime Numbers & More Curious Facts About Primes

A prime number is a positive integer whose only factors are 1 and itself, while a composite number has more than these two factors. Conventionally, 1 is considered neither prime nor composite. Prime numbers have been a source of fascination to mathematicians since antiquity, and there are still unproven conjectures and new discoveries being made about the nature of prime numbers and where they occur in the sequence of integers.

One of the most basic questions about primes is whether there are only finitely many. This was resolved circa 300 BC by the ancient Greek mathematician Euclid, who ingeniously proved that there are in fact infinitely many prime numbers. The second important discovery about prime numbers came over two thousand years later in 1896, when mathematicians Hadamard and de la Vallée Poussin independently proved how prime numbers are distributed among the natural numbers. In layman's terms, for a large enough integer N, the number of primes between 0 and N is approximately Ln(N), the natural logarithm of N. This is known as the Prime Number Theorem (PNT).

Here are more interesting facts and as-of-yet unproven conjectures about prime numbers.

## Prime Number Facts at a Glance

- The largest prime number known to date is 2^57885161 - 1. That's 2 multplied by itself 57885161 times, minus 1. This number is 17425170 digits long!
- There are 25 primes less than 100, 168 primes less than 1000, and 78498 primes less than 1000000.
- Jenny's number, 8675309, is a prime number
- Prime numbers occur in the life cycles of types of cicadas, such as 13-year and 17-year cicadas.
- To check if a number N is prime, you only need to check if all the primes up to sqrt(N) will divide evenly into N.

## Types of Prime Numbers

Mathematicians categorize prime numbers according to the form they take and how they relate to other types of integers such as squares, powers of 2, and Fibonacci numbers. Here are the most commonly studied varieties of primes.

**Euclid's Proof of the Infinitude of Primes:** This is a clever proof by contradiction. Suppose that the set of primes is finite and consists of n primes {2, 3, 5, ...., p_{n}}. Now consider the product of all these primes and call this number P_{n}#, the *n*th primorial. Let the Q = 1 + P_{n}#. There are two cases to consider.

- Q is prime. If Q is prime then the original assumption is false.
- Q is not prime. If Q is composite, then it can be factored into the product of primes. However, since Q is 1 plus the product of all the assumed known primes, it cannot be divisible by 2, 3, 5, ..., or p
_{n}. Thus, it must be divisible by some other prime(s) not in the original list of n primes.

Iterating this argument shows that for any finite list of primes, at least one other prime not in the list must exist, therefore the list of primes cannot be finite!

- Mersenne primes, named after the 17th century French monk Marin Mersenne, are primes of the form 2^n - 1. That is, they are 1 less than a power of 2. The 10 largest primes known to date are Mersenne primes. The first few are 3, 7, 31, 127,...
- Fermat primes, named after Pierre de Fermat, are of the form 2^(2^n) + 1. Fermat primes are key in the study of constructible polygons. A k-sided polygon is constructible with ruler and compass if and only if the k is the product of a power of 2 (including 2^0 = 1) and distinct Fermat primes. The only five Fermat primes are known to date are 3, 5, 17, 257, and 65537, and it is not known if there are infinitely many.
- Primorial primes are of the form p
_{n}# ± 1, where p_{n}# is the*n*th primorial, i.e., the product of all the first n primes. For example, 2*3*5*7 = 210 is the fourth primorial, and 210 + 1 = 211 is a primorial prime. This concept is key in Euclid's proof that there are infinitely many prime numbers. - A Sophie Germain prime is any prime p such that 2p + 1 is also prime. For instance, 11 is a Sophie Germain prime since 2*11 + 1 = 23, and 23 is prime. But 13 is not since 2*13 + 1 = 27, and 27 is divisible by 3.
- Twin primes are pairs of primes that differ by 2. For example, {3, 5}, {5, 7}, {11, 13}, {17, 19}, {29, 31}, {41, 43}, etc. It is not known if there are infinitely many twin prime pairs.
- An emirp ("prime" spelled backward) is a prime whose digit reversal is a distinct prime. The first several emirps are 13, 17, 31, 37, 71, 73, 79, 97,...
- Fibonacci primes are as the name suggests, numbers both prime and part of the Fibonacci sequence. It is not known if the set is infinite.
- Oddly enough, primes of the form n^2 + 1 don't have a special name, but they are also actively studied by number theorists.

## Uses of Prime Numbers

Public-key cryptography is an application of number theory that makes use of large primes and justifies the search for ever larger and larger prime numbers. One of the first public-key cryptosystems to be implemented was the RSA algorithm, whose encryption/decryption scheme works as follows:

- Pick two large primes P and Q and compute their product PQ = N, as well as the product (P-1)(Q-1) = M.
- Pick a number E between 1 and M such that E has no common factors with M.
- Compute a number D that is the multiplicative inverse of E modulo M.

The numbers E and N are released as the public-key encryption components, while D and M are the private-key decryption components. Anyone who knows E and N can encrypt a message, but only the person who knows D and M can decrypt the message. The security of the system relies on the fact that it is infeasible to factor large numbers such as N. If someone devised a faster factoring algorithm, this encryption scheme would become very easy to crack.

## Prime Generating Functions: Are there any formulas that output only prime numbers?

The search for prime number formulas has occupied mathematicians for centuries. Some of the first attempts to construct equations that output only prime numbers, or all the primes numbers, were linear and quadratic functions. For example, the polynomial x^2 - x + 41 outputs a prime number for x = 0, 1, 2, 3, ...., 40. However, past x = 40 the function starts outputting a mix of prime and composite numbers. It is not known if there are any quadratic polynomials that generate infinitely many primes. In particular, it is not know if the polynomial x^2 + 1 generates infinitely many primes for integer values of x.

Although Dirichlet proved that linear polynomials Ax + B output infinitely many prime numbers when gcd(A, B) = 1, they are not suitable as prime generators because they also output infinitely many composite numbers for integer values of x, regardless of the integer coefficients A and B.

More progress was made in 1947 when H. W. Mills proved that there exists a number Ψ such that

floor{ Ψ^(3^n) }

outputs a prime number for every positive integer n. Unfortunately, the value of Ψ is unknown, and nobody knows how to compute it. All we know is that if the Riemann hypothesis is true, then Ψ ≈ 1.30637788.

A sequence known to contain only 1s and primes makes use of the recursive equation

U_{n} = U_{n-1} + gcd(n, U_{n-1}), with U_{1} = 7

The *differences* between consecutive terms of this sequence, U_{n+1} - U_{n}, is a sequence that consists of 1s and primes -- mostly 1s. The first 50 terms of the difference sequence are 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3.

## Things Known About Prime Numbers

Over the centuries, mathematicians have done a lot to deepen our understanding of the nature of prime numbers. For example, it is easy to show that all prime numbers have the form 4n+1 or 4n+3. What is slightly harder show is that there are infinitely many primes of both types. This result is consequence of Dirichlet's Theorem, which states that for any coprime integers A and B, there are infinitely many primes of the form An + B. For instance, there are also infinitely many primes of the form 30n + 77. Here are some other known results about prime numbers.

- The infinite sum of the reciprocals of the primes, 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... is divergent. In other words, the sum is inifinity. This was proven by the prolific mathematician Leonhard Euler.
- Brun's Theorem: The sum of the reciprocals of twin prime pairs is convergent and approximately equal to 1.902160578. This number is known as Brun's constant. In the computation of Brun's constant, 1/5 is counted twice because it is a twin prime with both 3 and 7. It is not known if this is an infinite sum or not, since we do not know if there are infinitely many twin prime pairs.
- Bertrand's Postulate (or Bertrand's Theorem): For every integer X, there is always at least one prime number between X and 2X - 2. An improvement on this result is that there is always a prime between 3X and 4X.

## Things Unknown About Prime Numbers

Primes are the center of many unproven conjectures in mathematics. Four unsolved conjectures about prime numbers are collectively known as Landau's Problems, not because they were posed by the mathematician Edmund Landau, but because in 1912 he characterized these four as "unattackable at the present state of science." They are

Above is the only known image of French mathematician Adrien-Marie Legendre, sketched by caricaturist Julien-Leopold Boilly in 1820. Up until 2005, historians had mistakenly used the portrait of French politician Louis Legendre, below. (Public Domain, both)

- Goldbach's Conjecture: Is every even integer the sum of two prime numbers? Thus far, all even numbers up to 4×10^18 have been proven to be the sum of two primes.
- The Twin Prime Conjecture: Are there infinitely many pairs of primes that differ by 2?
- Legendre's Conjecture: For every pair of consecutive perfect squares, is there always a prime between them? In other words, for every N, is there always a prime number between N^2 and (N+1)^2?
- Are there infinitely many primes of the form m^2 + 1 for some integer m? In other words, are there infinitely many primes p such that p - 1 is a square number?

Other unproven conjectures about prime numbers include

- Polignac's Conjecture: For any even number k, there are infinitely many pairs of primes whose difference is k. If Polignac's Conjecture is true, it would imply that there are infinitely many twin primes, since this is the case k = 2.
- Are there infinitely many Sophie Germain primes?
- Brocard's Conjecture: There are at least four primes between the squares of consecutive prime numbers, starting with the second prime number 3.

## Visualizations of Prime Numbers

If you draw a square spiral of the integers starting with 1 at the center, and highlight the primes, you will produce the Ulam spiral. Interesting patterns of prime number density emerge along certain lines as you increase the size of the spiral.

## Extending the Concept of "Prime" to Complex Numbers a + bi

The Gaussian integers are complex numbers of the form a + bi, where a and b are real integers. Since a and b can be 0, the set of Gaussian integers includes both pure imaginary integers and real integers. Gaussian primes are Gaussian integers that cannot be factored as the product of smaller Gaussian integers, not including the trivial unit factors 1, -1, i, and -i.

For example, 2 - 5i is a Gaussian prime, but -1 + 3i is not since -1 + 3i = (1 + i)(1 + 2i). A curious thing about the Gaussian integers is that real prime integers of the form 4n + 1 are no longer prime. For example, the real primes 5, 17, and 61 factor as

5 = (2 + i)(2 - i) = (1 + 2i)(1 - 2i)

17 = (4 + i)(4 - i) = (1 + 4i)(1 - 4i)

61 = (5 + 6i)(5 - 6i) = (6 + 5i)(6 - 5i)

Nor is 2 a Gaussian prime since 2 = (1 + i)(1 - i). However, all real primes of the form 4n + 3 are still prime among the Gaussian integers.

## Comments

This is a hub I need to read over and over again to fully grasp the facts about prime numbers, but congratulations for being picked as a hub of the day.

I love math, I thought about majoring in math but was led to elementary education instead. What a fascinating hub!

This seriously has GOT to be in my list of Top 10 hubs ever. For real! I love prime numbers and study them when I'm not concentrating on chemistry.

I wrote some computer code for finding prime numbers, but I haven't completed it yet. It's my Summer project. I don't expect to find the next prime number, really just playing around with code and primes.

Sharing this article all over social media. :)

Wow, that picture of the Ulam spiral at 150 iterations really blew me away. Really great hub, and congrats on HOTD!

6