You Gotta Know These Statements ÎÞÓǶÌÊÓƵ Prime Numbers
A positive integer p greater than 1 is called prime if it has exactly two positive divisors, 1 and p itself. All other positive integers greater than 1 are called composite. The categories of prime and composite do not apply to 0, 1, or negative integers.
- The fundamental theorem of arithmetic states that every positive integer greater than 1 can be expressed as a product of primes (its prime factorization), and that factorization is unique if the order of the factors is ignored. For example, 80 = 24·5, and there is no other way to express 80 as a product of primes other than changing the order (80 = 5·24 = 23·5·2, etc., but these are all really the same product). This includes prime numbers as a “product of just one prime,” e.g., 7’s prime factorization is just 7. This ubiquitous result in number theory is a principal reason that primes are so important.
- There are infinitely many prime numbers. This is sometimes called Euclid’s theorem since Euclid’s Elements contained a proof of it similar to the following: Consider finitely many prime numbers p1, p2, … pn. Now consider 1 more than the product of those prime numbers, that is, p1p2×⋯×pn + 1. That number cannot be divisible by any of the original prime numbers pi. Therefore, it must itself be prime, or else be divisible by prime numbers that are not on the original list. Either way, that means there is at least one prime number not on the original list. That argument can be applied to any finite list of prime numbers, so there cannot be any finite list that contains every prime number. There are many other proofs of this statement.
- Fermat’s little theorem (not to be confused with Fermat’s last theorem) states that if p is prime and a is any integer, then ap ≡ a mod p, that is, ap − a is divisible by p. This theorem is used in probabilistic primality testing, which is problematic because the converse is not always true: Carmichael numbers (of which 561 is the smallest example) are composite numbers n such that if a is any integer, an ≡ a mod n. Fermatଁs little theorem can be generalized to composite numbers as Euler’s theorem, which uses Euler’s totient function.
- Wilson’s theorem states that p is prime if and only if (p − 1)! ≡ −1 mod p. Though named after the 18th-century English mathematician John Wilson, its first known use is by the 11th-century polymath Ibn Al-Haytham. A common proof of the theorem requires the useful fact that each number from 1 to p − 1 has a unique multiplicative inverse modulo p.
- The Euclid–Euler theorem states that every even perfect number can be written in the form 2p − 1(2p − 1), where p is prime. The latter factor is a Mersenne prime (a prime number that is 1 less than a power of 2; the term Mersenne number refers to any number 1 less than a power of 2, regardless of whether it is prime), and the theorem also states that every Mersenne prime gives rise to a perfect number via that formula, meaning that this formula gives a bijection between even perfect numbers and Mersenne primes. (The theorem says nothing about odd perfect numbers, but it is not known whether any odd perfect numbers even exist.)
- The prime number theorem describes the approximate behavior of the prime counting function, π(n), which gives the number of primes less than or equal to n. There is no exact straightforward formula for this function, but there are several approximations, including this theorem. Specifically, the prime number theorem says that π(n) ～ n / logen, that is, as n becomes arbitrarily large, π(n) gets arbitrarily close to n / logen. There are many alternate formulations of this theorem, including in terms of the logarithmic integral.
- It is very difficult to find prime factorizations of large numbers. This fact underlies public key cryptography algorithms like RSA (which, in turn, underlie much of the security in computing, such as safely transmitting credit card numbers for online payments) and many other algorithms in cryptography. Some cryptosystems use safe primes, which are primes that can be written in the form 2p + 1 for a smaller prime number p; these numbesr were first studied by Sophie Germain long before the advent of public key cryptography.
- Goldbach’s conjecture, sometimes called the strong Goldbach conjecture, is the unproven claim that every even integer greater than 2 can be written as the sum of two prime numbers. (For example, 16 = 5 + 11.) This has been verified from 4 to 4,000,000,000,000,000,000, but it has not been proven to be true for every even integer greater than 2. There are some interesting variations of this statement, such as that every odd integer greater than 5 can be written as the sum of three prime numbers, which is called the weak Goldbach conjecture and was proved by Harald Helfgott in 2013.
- The Riemann hypothesis is an unproven statement about the Riemann zeta function, ζ(s) = 1/1s + 1/2s + 1/3s +⋯, where s is a complex number. The hypothesis states that that function’s zeroes (roots) are all either negative even numbers or complex numbers whose real part is ½ (the latter called the critical strip or critical line). The Euler product is a technique that can be used to rewrite the zeta function as a product using prime numbers as indexes, which means the Riemann hypothesis has significant implications for how prime numbers are distributed, including for understanding how the approximation in the prime number theorem changes its accuracy (called the error term). The zeta function and hypothesis were introduced by Bernhard Riemann in 1859 in the paper “On the Number of Primes Less Than a Given Magnitude.” Proving the hypothesis is a Millennium Prize Problem. It is generally believed to be true, and many results in advanced mathematics rest on an assumption that it is true, but it has not been proven.
- The twin prime conjecture is the unproven statement that there are infinitely many pairs of primes that differ by 2, such as 3 and 5, or 101 and 103. These pairs are called twin primes. There has been rapid progress recently on the related concept of prime gaps, which are the differences between consecutive primes (e.g., 31 and 37 have a prime gap of 6, while twin primes have a prime gap of 2); the twin prime conjecture is equivalent to stating that a prime gap of 2 occurs infinitely often. In 2013 Yitang Zhang showed that there are infinitely many prime gaps less than 70 million; over the next two years, James Maynard and the collaborative Polymath project reduced this bound to 4860, 600, and 246.
This article was contributed by ÎÞÓǶÌÊÓƵ editor Joseph Krol.