50 Awesome facts about prime numbers

A prime is a natural number greater than one whose only factors are one and itself. I find primes pretty cool, so I made a list of 50 facts about primes:

  1. The first twenty primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.
  2. For any positive natural number $n$, there is always a prime between $n$ and $2n$. This is known as Bertrand’s postulate.
  3. A Mersenne prime is a prime of the form $2^n – 1$. Such a number is prime if and only if $2^{n-1}(2^n-1)$ is a perfect number (a number equal to the sum of all its proper divisors). All even perfect numbers arise this way, and no one knows if an odd perfect number exists.
  4. Mersenne would be pretty thrilled that people keep looking for his primes

  5. There are 51 known Mersenne primes, and it is unknown whether there are infinitely many.
  6. The largest prime that humans have ever found is $2^{82,589,933}-1$ and is a Mersenne prime. It was discovered in 2018.
  7. It is pretty easy to come up with a new kind of prime, such as a “palindromic prime”, but most of the time it is very difficult to prove that there are infinitely many such primes. In case you’re curious, 142840628019121910826048241 is a palindromic prime.
  8. If $a$ and $b$ are relatively prime nonzero integers, then there are infinitely many primes in the sequence $a + b, 2a + b, 3a+b,\dots$.
  9. The primes 17 and 37 are of the form $x^2+1$ for $x = 4$ and $x=6$ respectively. No one knows whether there are infinitely many primes of this form.
  10. If $F$ is a field with finitely many elements, then it must have $p^n$ elements for some prime and positive natural number $n$.
  11. Every positive natural number can be written uniquely (up to order of factors) as a product of prime numbers.
  12. Wilson’s theorem: If $n > 1$ is a natural number, then $(n-1)!\equiv -1\pmod{n}$ if and only if $n$ is prime. This theorem is totally impractical for primality testing in practice.
  13. There exists a real number $\theta$ such that $f(n) = \lfloor \theta^{3n}\rfloor$ is prime for every $n\geq 1$.
  14. Goldbach’s conjecture is that every even number $n\geq 4$ can be written as the sum of two primes. Indeed, experiments suggest that as $n$ increases, so does the number of ways it can be so written.

    Here are the number of ways to write n as a sum of two primes, plotted on a logarithmic plot. It only increases. The blue denotes numbers of the form 4k and the red denotes numbers of the form 4k+2.

  15. …on the other hand, Ivan Matveevich Vinogradov proved that every sufficiently large odd number can be written as the sum of three primes.
  16. Vinogradov came the closest to proving Goldbach’s conjecture

  17. The infinite sum $1/2 + 1/3 + 1/5 + 1/7 + 1/11 + \cdots$ of the reciprocal of all primes diverges.
  18. Did I mention there are infinitely many primes? That is because if you only have finitely many primes $p_1,\dots,p_n$ then the number $p_1\cdots p_n + 1$ either is prime or has a prime factor not in the original list of primes. This proof is due to Euclid.
  19. It’s 2019. Unfortunately, that’s not a prime. The next prime year is 2027, and the one after that is 2029.
  20. You probably noticed that 2027 and 2029 are twin primes. That is, they are prime numbers only two apart. There are probably infinitely many of them, but no one has proved this.
  21. Even though no one has proved the twin prime conjecture, Yitang Zhang in 2013 proved that there are infinitely many prime pairs whose distance is 70,000,000 or less.
  22. Like most other well-studied types of primes, mathematicians have inevitably searched for huge examples of twin primes. For example, in 1994, Karl-Heinz Indlekofer and Antal Járai wrote a computer program that determined $697053813\times 2^{16352}\pm 1$ to be twin primes.
  23. The first prime after a trillion (10^12) is 1000000000039.
  24. Fermat’s little theorem states that if $p$ is a prime and $p$ does not divide an integer $a$ then $a^{p-1}\equiv 1\pmod{p}$. This can be used as a quick primality test. For example, $3^{1000} – 1$ is congruent to 990 modulo 1001, so 1001 is not prime (it is in fact divisible by 11).
  25. Fermat’s little theorem cannot always recognize composite numbers. In fact, there are numbers $n$ that are not prime, and yet $a^{n-1}\equiv -1\pmod{n}$ for every $a$. Such $n$ are called Carmichael numbers. Sneaky buggers.
  26. The smallest Carmichael number is 561, and Alford, Granville, and Pomerance proved in 1994 that there are infinitely many Carmichael numbers.
  27. Never fear, Fermat’s little theorem can be enhanced to better work against Carmichael numbers in what is known as the Miller-Rabin primality test.
  28. If $n\geq 5$ is prime then
    \[ \binom{2n-1}{n-1}\equiv 1\pmod{n^3}. \] The converse is still a conjecture!
  29. Remember Euclid’s proof that there are infinitely many primes? If $p$ is a prime and $N_p$ is the product of all primes less than or equal to $p$, then $N_p+1$ is either prime or has a prime factor larger than $p$. But when is $N_p$ actually prime? $p=24029$ is the largest prime known such that $N_p + 1$ is prime.
  30. Another type of prime is a Fermat prime. It is a prime of the form $F_n = 2^{2^n} + 1$. The largest known prime of this form is $F_4 = 65537$. So for example, $F_5 = 641\times 6700417$ and $F_6 = 274177\times 67280421310721$. It is unknown whether $F_{24}$ is prime or composite. The number $F_{24}$ is around $10^{5050445}$.
  31. Théophile Pépin gave a criterion for a Fermat number $F_n$ to be prime: it is prime if and only if $3^{(F_k-1)/2}\equiv -1\pmod{F_k}$.
  32. Lucas proved that if $a$ and $n \gt 1$ are integers and $a^{n-1}\equiv 1\pmod{n}$ but $a^{(n-1)/q}\not\equiv 1\pmod{n}$ for each prime $q\mid n-1$ then $n$ is prime.
  33. Every prime number of the form $4k + 1$ can be written as the sum of two squares. For example, $13 = 2^2 + 3^2$. No prime of the form $4k + 3$ can be so written.
  34. For every prime $p$ there exists integers $x$ and $y$ such that $x^2 + y^2 + 1$ is divisible by $p$.
  35. There is no nonconstant polynomial which takes on only prime values.
  36. However, the polynomial $f(x) = x^2 + x + 41$ is prime for $x=0,1,\dots, 39.$
  37. Stranger still, there exists a multivariable polynomial with integer coefficients whose values is exactly the set of primes when its variables take on all the nonnegative integers.
  38. Let $\pi(x)$ denote the number of primes less than or equal to $x$. The prime number theorem states that $\pi(x)$ is asymptotically $x/\log(x)$. That is, $\lim_{x\to\infty} \pi(x)/(x/\log(x))=1$.
  39. The current record for calculating $\pi(x)$ is
    \[\pi(10^{25}) = 176846309399143769411680, \] found by Jan Büthe in 2014.
  40. Gauss gave a more accurate estimate of ${\rm Li}(x):= \int_2^x {\rm d}t/\log(t)$ for $\pi(x)$. The function ${\rm Li}(x)$ is called the logarithmic integral.
  41. C.F. Gauss was one serious dude!

  42. There are arbitrarily large sequences of consecutive integers, none of which are prime. One way to produce such a sequence is $n! + 2, n! +3,\dots, n! + n$, which is a sequence of $n-1$ composite numbers.
  43. The number 9012345678901 whose digits are consecutive integers, is a prime number! Here is another:


    Can you find a bigger one?!

  44. Legendre’s conjecture states that for every natural number $n$, there exists a prime number between $n^2$ and $(n+1)^2$.
  45. Although no one has proved Legendre’s conjecture, Chen Jingrun did prove that there exists a number $x$ between $n^2$ and $(n+1)^2$ that is either prime or a product of two primes.
  46. Chen also proved an approximation to Goldbach’s conjecture: every sufficiently large even number is the sum of a prime and a number that has at most two prime factors.
  47. Levy’s conjecture states that all odd numbers greater than or equal to 7 are the sum of a prime and twice a prime. For example: 11 = 5 + 2(3).
  48. A Sophie Germain prime is a prime $p$ such that $2p+1$ is also a prime. These primes are primes for which the “first case” of Fermat’s Last Theorem holds. No one knows if there are infinitely many.
  49. The largest Sophie Germain prime known to us is
    \[ p = 2618163402417\times 2^{1290000} -1. \]
  50. Pretty much the only image of Sophie Germain is on this medallion

  51. A Smarandache-Wellin is a prime of the form $Q_n = p_1|p_2|\cdots |p_n$ where $p_1,\dots,p_n$ are the first $n$ primes and $a|b$ denotes $a$ concatenated with $b$. For example, $Q_1 = 2, Q_2 = 23, Q_3 =235$, etc. The first few running primes are $2, 23, 2357,\dots$ and the next one is quite large. I just made this definition up, but after searching the OEIS I found it it had the name Smarandache-Wellin. Pretty cool, right? Can you find the next one?
  52. You can also stick a decimal point in front of the concatenation of primes to form $0.235711\dots$. This number is called the Copeland–Erdős constant and it’s irrational.
  53. There exists a polynomial-time algorithm to determine whether a number is prime. It was discovered in 2002 by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.
  54. If this guy knew his hypothesis was worth a million dollars, he would have solved it himself

  55. The Riemann zeta function is the analytic continuation of the function $\zeta(s) = 1^{-s} + 2^{-s} + 3^{-s} + \cdots$. It has trivial zeroes at the negative even integers. The Riemann hypothesis is that all its nontrivial zeroes are on the line Re=1/2, and is a Millenium prize problem worth a million USD. The Riemann hypothesis implies many facts about the distribution of primes, including the prime number theorem.

Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.