A prime number is a natural number greater than 1 whose only divisors are 1 and itself. Primes are the atoms of arithmetic β the Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written as a product of primes in exactly one way. There are infinitely many primes (Euclid, c. 300 BCE) but their distribution among the integers is one of the deepest unsolved problems in mathematics.
Some numbers can be broken down by multiplication: 12 = 3 Γ 4, or 6 Γ 2, or 2 Γ 2 Γ 3. But some numbers can't be broken down β they're only divisible by 1 and themselves. These are primes.
The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47β¦
Every other counting number (bigger than 1) is a product of primes:
This is why primes are called the "atoms" of arithmetic. Just like every molecule is built from atoms, every number is built from primes β in exactly one way.
Yes β and we've known this for 2,300 years. Euclid proved it around 300 BCE with one of the cleverest short proofs in all of mathematics. His argument: suppose you had a complete list of all primes. Multiply them all together and add 1. The number you get isn't divisible by any prime on your list β so either it's a new prime, or it has a prime factor you missed. Either way, your list wasn't complete. So no finite list is ever complete.
Primes are the foundation of internet security. Every time you shop online, your card details are protected by encryption that relies on the fact that multiplying two large primes together is easy, but working out which two primes were used is extremely hard. The primes keep your passwords safe.
A prime number p is a natural number p > 1 such that the only divisors of p are 1 and p. Equivalently, p is prime if whenever p = ab with a, b β β€βΊ, then a = 1 or b = 1.
Note: 1 is not prime by definition. This is because of the Fundamental Theorem of Arithmetic β if 1 were prime, factorizations would not be unique (e.g. 6 = 2 Γ 3 = 1 Γ 2 Γ 3 = 1 Γ 1 Γ 2 Γ 3 etc.).
Every integer n > 1 can be written as a product of primes, and this factorization is unique up to the order of factors. This is the central theorem of elementary number theory. It was stated implicitly by Euclid (Elements IX.14) and proved explicitly by Gauss (Disquisitiones Arithmeticae, 1801).
Assume finitely many primes pβ, pβ, β¦, pβ. Let N = pβpββ¦pβ + 1. Then N is not divisible by any pα΅’ (remainder 1 each time). Either N is prime (contradicting completeness) or N has a prime factor not in the list (also contradicting completeness). β΄ There are infinitely many primes. β
Primes thin out as numbers get larger, but never disappear. The Prime Number Theorem (proved independently by Hadamard and de la VallΓ©e-Poussin, 1896) states: the number of primes up to n, written Ο(n), satisfies
This means roughly 1 in every ln(n) numbers near n is prime. Near 1,000,000 (ln β 13.8), about 1 in 14 numbers is prime. Near 10ΒΉβ°β°, about 1 in 230.
To find all primes up to n: write out 2, 3, 4, β¦, n. Cross out all multiples of 2 (keeping 2). Cross out all multiples of 3 (keeping 3). Continue through each uncrossed number. What remains is the list of primes. You only need to check up to βn β any composite number β€ n has a factor β€ βn.
The Riemann zeta function is defined for complex s with Re(s) > 1 as ΞΆ(s) = Ξ£ nβ»Λ’, then extended analytically to all complex s except s = 1. Riemann (1859) showed the distribution of primes is controlled by the zeros of ΞΆ(s). The "trivial" zeros occur at s = β2, β4, β6, β¦. The "non-trivial" zeros all have 0 < Re(s) < 1. The Riemann Hypothesis states all non-trivial zeros have Re(s) = 1/2. If true, the error term in the Prime Number Theorem is O(βn Β· ln n), the best possible. The hypothesis has been numerically verified for the first 10ΒΉΒ³ non-trivial zeros.
The RSA public-key cryptosystem (Rivest, Shamir, Adleman, 1977) is based on: given two large primes p and q, computing n = pq is trivial; factoring n back into p and q is computationally infeasible for sufficiently large p, q (no known polynomial-time algorithm for classical computers). RSA is used in HTTPS, TLS, SSH, and most public-key infrastructure worldwide. The security relies on no efficient factoring algorithm existing β a relationship to the P vs NP problem that is unproved.
Testing whether a number n is prime is computationally easy: the AKS primality test (Agrawal, Kayal, Saxena, 2002) runs in polynomial time O((log n)^6), proving primality testing is in P. This was the first deterministic polynomial-time primality test. In practice, faster probabilistic tests (Miller-Rabin, Solovay-Strassen) are used.
Ben Green and Terence Tao proved that the primes contain arbitrarily long arithmetic progressions β sequences of primes equally spaced (like 5, 11, 17, 23, 29 β five primes spaced 6 apart). This was a landmark result combining analytic number theory with ergodic theory and additive combinatorics.