Prime Numbers

A prime number is a positive integer greater than 1 whose only positive divisors are 1 and itself. The primes — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … — are the building blocks of the integers: every positive integer can be factored into primes in exactly one way (up to order). Primes are central to number theory, cryptography, and surprisingly to the random-looking statistics of complex systems. The study of their distribution is one of the oldest open problems in mathematics.

Definition

A natural number \( p > 1 \) is prime if its only positive divisors are 1 and \( p \) itself. A natural number greater than 1 that is not prime is composite — it has at least one divisor other than 1 and itself. The number 1 is neither prime nor composite (by convention, to make the Fundamental Theorem of Arithmetic clean).

First 25 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

The Fundamental Theorem of Arithmetic

Every integer \( n > 1 \) can be written as a product of primes in essentially one way:

$$ n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k} $$

where the \( p_i \) are distinct primes and the \( a_i \) are positive integers. The factorization is unique up to the order of the factors. Example: \( 360 = 2^3 \cdot 3^2 \cdot 5 \). No other prime factorization of 360 exists.

Euclid’s Theorem: Infinitely Many Primes

There are infinitely many primes. Euclid proved this around 300 BCE.

Proof sketch. Suppose only finitely many primes exist: \( p_1, p_2, \ldots, p_k \). Consider \( N = p_1 p_2 \cdots p_k + 1 \). Either \( N \) is itself prime (a new prime not in the list), or \( N \) has a prime factor — but that factor cannot be any of \( p_1, \ldots, p_k \) (because \( N \) leaves a remainder of 1 when divided by any of them). Either way, we have a prime not in the original list. Contradiction. So no finite list captures all the primes.

Distribution of Primes

Primes thin out as numbers get larger, but they never stop. The Prime Number Theorem (Hadamard and de la Vallée Poussin, 1896) makes the thinning precise:

$$ \pi(x) \sim \frac{x}{\ln x} $$

where \( \pi(x) \) is the number of primes \( \leq x \). So among the first \( 10^9 \) numbers, about \( 10^9 / \ln(10^9) \approx 4.83 \times 10^7 \) are prime — roughly 1 in 21.

The largest known prime as of 2026 is a Mersenne prime with over 41 million digits. Finding huge primes is a popular distributed-computing pursuit (GIMPS — Great Internet Mersenne Prime Search).

Sieve of Eratosthenes

The classic way to find primes up to \( N \):

1. Write down all integers from 2 to \( N \).
2. Cross out all multiples of 2 except 2 itself.
3. Move to the next number not crossed out (3) and cross out all its multiples except itself.
4. Repeat until the next number to check exceeds \( \sqrt{N} \). All remaining numbers are prime.

Eratosthenes (3rd century BCE) gave this method; it’s still the fastest way to find all primes up to a moderate bound.

Primality Tests vs. Factoring

Testing whether a number is prime is computationally easy: the AKS algorithm (2002) runs in polynomial time. The Miller-Rabin probabilistic test is fast and gives near-certainty of primality very quickly. Factoring a composite number into its prime factors, on the other hand, is computationally hard — no polynomial-time classical algorithm is known. This asymmetry is exactly what makes RSA encryption work.

Applications

• RSA cryptography. Pick two large primes p and q, multiply them to get n = pq. The product n is the public key; the primes are the private key. Factoring n to recover p and q is computationally infeasible at typical key sizes (~2048 bits), which makes RSA secure.
• Hashing. Hash table sizes are typically prime to spread keys evenly; prime moduli reduce clustering.
• Random number generation. Many pseudo-random generators use prime moduli to maximize period length.
• Pure number theory. The Riemann Hypothesis — the most famous open problem in mathematics — concerns the distribution of primes. A million-dollar Clay Millennium Prize is offered for a proof.
• Coding theory. Reed-Solomon codes and other error-correcting codes operate over finite fields, which have prime (or prime power) sizes.

Related study notes: Modular Arithmetic, Fundamental Theorem of Algebra, Cryptography, Euclidean Algorithm.

Frequently Asked Questions