Prime Number

A prime number is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, \dots Everything else — 4 = 2\times2, 6 = 2\times3, 12 = 2\times2\times3 — is composite, built by multiplying smaller pieces. The primes are the pieces that cannot be broken further. They are, quite literally, the atoms of multiplication, and the Fundamental Theorem of Arithmetic makes that metaphor a theorem.

The sieve made visible

The fastest way to see primality is to eliminate everything that isn't prime. Lay the integers out in a grid and cross out every multiple of 2, then every multiple of 3, then 5, and so on. Whatever survives is prime. This is the Sieve of Eratosthenes, running live below.

Infinitely many — Euclid's proof

There is no largest prime. Euclid proved it around 300 BC with one of the most elegant arguments in all mathematics, a proof by contradiction.

Suppose the primes were a finite list p_1, p_2, \dots, p_k. Form the number

Now Q leaves remainder 1 when divided by every prime on the list, so none of them divides it. But every integer above 1 has at least one prime factor (by the Fundamental Theorem of Arithmetic). That factor is a prime not on our list — contradiction. The list can never be complete, so the primes go on forever.

Thinning out, but never stopping

Primes become rarer as you climb, but only slowly. The prime counting function \pi(x) — how many primes are \le x — grows like x / \ln x, the celebrated Prime Number Theorem. The density near x is roughly 1/\ln x, so primes thin out logarithmically: never absent, never regular.

This unpredictable-yet-structured distribution is exactly what makes primes useful in RSA: it is easy to find large primes (they are common enough), but hard to factor their products.

See also

• Sieve of Eratosthenes
• Fundamental Theorem of Arithmetic
• RSA