🪴 GoDeep
Search
← University Challenge
Portrait of Prime numbers

Science · Mathematics

Prime numbers

c. 300 BC – present

Mathematics — number theory

The whole numbers greater than 1 divisible only by themselves and 1 — 2, 3, 5, 7, 11, 13 and so on — the multiplicative atoms from which every other whole number is built. Euclid proved around 300 BC that there are infinitely many of them, and the fundamental theorem of arithmetic says that every integer above 1 factorises into them in exactly one way. Their distribution thins out logarithmically, as the prime number theorem describes, and their apparent randomness underpins RSA and much of modern cryptography.

How to spot them

  • ▸Divisible only by 1 and itself; 1 is excluded by convention so that factorisation is unique
  • ▸2 is the only even one, and so is often called the oddest prime
  • ▸Euclid's proof by contradiction that the list never ends
  • ▸The sieve of Eratosthenes, which strikes out multiples to leave them behind
  • ▸Record-breaking examples are almost always Mersenne numbers, one less than a power of 2

Key facts

Book IX, Proposition 20 of the Elements: the list never ends (c. 300 BC)

Euclid's proof: multiply any finite list together and add 1

A sieve attributed to the librarian of Alexandria who also measured the Earth (c. 240 BC)

The sieve of Eratosthenes, which crosses out multiples in turn

The theorem, proved independently in 1896 by Hadamard and de la Vallée Poussin, that the count up to n is roughly n divided by its natural logarithm (1896)

The prime number theorem, conjectured by Gauss as a teenager

The 1977 public-key cipher whose security rests on the difficulty of factorising a large product of two of them (1977)

RSA, named for Rivest, Shamir and Adleman

The still-unproved conjecture that every even number above 2 is the sum of two of them (1742)

Goldbach's conjecture, posed in a letter to Euler

A distributed computing project that since 1996 has found every new record-holder (1996)

GIMPS, the Great Internet Mersenne Prime Search

A 2002 Indian algorithm giving the first deterministic polynomial-time test for the property (2002)

The AKS algorithm of Agrawal, Kayal and Saxena at IIT Kanpur

Yitang Zhang's 2013 proof that infinitely many pairs differ by less than 70 million (2013)

The first finite bound on prime gaps; collaborative work later cut it to 246

Key ideas

  • The fundamental theorem of arithmetic: every integer greater than 1 is a product of these numbers in exactly one way, up to order. This is why 1 is not counted as one of them.
  • Multiplying a pair of large ones is easy; recovering them from the product is believed to be hard. That asymmetry is the basis of RSA encryption.

Quick-fire facts

  • •Euclid proved there are infinitely many in Book IX of the Elements, around 300 BC
  • •The largest known is 2^136,279,841 − 1, found in October 2024 by Luke Durant for GIMPS; it has 41,024,320 digits
  • •It is the 52nd known Mersenne prime; Mersenne primes are one less than a power of 2
  • •The twin prime conjecture — that there are infinitely many pairs differing by 2 — remains open
  • •Goldbach's conjecture of 1742, that every even number above 2 is the sum of two of them, is also still open
  • •The prime number theorem was conjectured by Gauss around 1792 and proved in 1896 by Jacques Hadamard and Charles-Jean de la Vallée Poussin
  • •The Electronic Frontier Foundation has paid awards for the first primes of 1 million and 10 million digits, and still offers prizes for 100 million and 1 billion
  • •A Sophie Germain prime is one for which twice it plus one is also prime; a Mersenne prime is 2^p − 1 with p prime
  • •Fermat's little theorem underlies most fast primality tests; the AKS algorithm of 2002 was the first deterministic polynomial-time test
  • •The Riemann hypothesis, if true, would pin down the error term in the prime counting function
  • •2 is the only even example, so any question about 'the only even' one has that answer

Drill it — 9 cards

1 / 9new card

Sources