3.1 Prime numbers

Definition of prime numbers

A prime number is a positive integer greater than 1 whose only divisors are 1 and itself. Numbers like 2, 3, 5, 7, and 11 are prime. Any positive integer greater than 1 that isn't prime is called composite, meaning it can be broken into smaller factors (for example, 12 = 2 × 2 × 3).

Primes matter because they're the atoms of arithmetic. Every whole number is either prime or can be built by multiplying primes together. This makes them the starting point for nearly everything in number theory.

Fundamental theorem of arithmetic

This theorem says that every integer greater than 1 can be written as a product of primes in exactly one way (ignoring the order you write them). For example, 60 = 2 × 2 × 3 × 5, and there's no other combination of primes that gives you 60.

The word "uniquely" is doing heavy lifting here. It means the prime factorization of any number is like a fingerprint: no two different numbers share the same one, and no number has two different factorizations.

This theorem is the foundation for working with divisibility, greatest common divisors (GCDs), and least common multiples (LCMs).

Prime factorization

Prime factorization is the process of breaking a composite number down into its prime factors. Here's how to do it using repeated division:

1. Start with your number (say, 84)
2. Divide by the smallest prime that goes in evenly: 84 ÷ 2 = 42
3. Keep dividing by that prime until it no longer works: 42 ÷ 2 = 21
4. Move to the next prime: 21 ÷ 3 = 7
5. 7 is prime, so you're done: $84 = 2^2 \times 3 \times 7$

Prime factorization is the tool you'll use to find GCDs and LCMs. To find the GCD of two numbers, take the lowest power of each shared prime factor. To find the LCM, take the highest power of every prime factor that appears in either number.

Properties of prime numbers

Infinitude of primes

There are infinitely many primes. Euclid proved this around 300 BCE using proof by contradiction, which is worth understanding as a technique:

1. Assume there are only finitely many primes: $p_1, p_2, \ldots, p_n$
2. Multiply them all together and add 1: $N = p_1 \times p_2 \times \cdots \times p_n + 1$
3. $N$ is not divisible by any prime on your list (dividing by any of them leaves a remainder of 1)
4. So either $N$ is itself prime, or it has a prime factor not on your list
5. Either way, your list was incomplete. Contradiction.

This is one of the most famous proofs in all of mathematics, and it's a great example of how proof by contradiction works.

Distribution of primes

Primes become less frequent as numbers get larger, but they never stop appearing entirely. Among the first 100 positive integers, there are 25 primes. Among the first 1,000, there are 168. The density keeps dropping.

Gaps between consecutive primes generally grow, but not in a perfectly predictable way. You can find stretches of 100+ consecutive composite numbers, yet surprisingly close prime pairs still pop up (more on twin primes below).

Prime number theorem

The prime number theorem gives a precise estimate of how primes thin out. It says the number of primes less than or equal to $n$, written $\pi(n)$, is approximately:

$\pi(n) \approx \frac{n}{\ln(n)}$

For example, the number of primes up to 1,000,000 is 78,498, while $\frac{1{,}000{,}000}{\ln(1{,}000{,}000)} \approx 72{,}382$. Not exact, but it captures the right order of magnitude and gets proportionally better as $n$ grows.

This also gives you a rough sense of the "probability" that a random number near $n$ is prime: about $\frac{1}{\ln(n)}$.

Testing for primality

How do you determine whether a given number is prime? There are several approaches, ranging from simple to sophisticated.

Trial division

The most straightforward method: try dividing your number $n$ by every integer from 2 up to $\sqrt{n}$. If none divide evenly, $n$ is prime.

Why only up to $\sqrt{n}$? Because if $n = a \times b$ and both $a$ and $b$ are greater than $\sqrt{n}$, then $a \times b > n$. So at least one factor must be $\leq \sqrt{n}$.

For example, to test whether 97 is prime, you only need to check primes up to $\sqrt{97} \approx 9.8$, meaning you check 2, 3, 5, and 7. None divide 97, so it's prime.

Trial division works fine for small numbers but becomes impractical for very large ones.

Sieve of Eratosthenes

This ancient algorithm finds all primes up to a given limit. Here's how it works:

1. Write out all integers from 2 to your limit $n$
2. Start with the first unmarked number (2). Circle it as prime
3. Cross out all multiples of 2 (4, 6, 8, 10, ...)
4. Move to the next unmarked number (3). Circle it as prime
5. Cross out all multiples of 3 (9, 15, 21, ...)
6. Repeat until you've passed $\sqrt{n}$. Every remaining unmarked number is prime

The sieve is efficient for generating lists of primes and is still used as a building block in modern algorithms.

Probabilistic primality tests

For very large numbers (hundreds of digits), trial division and sieves are too slow. Probabilistic tests like the Miller-Rabin test can determine with very high confidence whether a number is prime, without guaranteeing it with 100% certainty.

These tests work by checking certain mathematical conditions that all primes satisfy. If a number fails the test, it's definitely composite. If it passes, it's probably prime. Running the test multiple times with different parameters drives the error probability extremely low (for practical purposes, negligible).

This trade-off between speed and absolute certainty is a recurring theme in computational mathematics.

Applications of prime numbers

Cryptography and RSA

RSA encryption, one of the most widely used cryptographic systems, depends directly on prime numbers. The core idea:

• Multiplying two large primes together is easy (a computer can do it instantly)
• Factoring the resulting product back into those two primes is extraordinarily hard when the primes are large enough (hundreds of digits)

This asymmetry between multiplication and factoring is what makes RSA secure. Your public key is based on the product; your private key depends on knowing the original primes.

Hash functions

Hash functions map data to fixed-size values, and prime numbers help make them work well. Using a prime number as the size of a hash table reduces the chance of collisions (different inputs mapping to the same slot), because primes don't share factors with common data patterns.

Random number generation

Some pseudo-random number generators use primes as parameters. Linear congruential generators, for instance, often choose prime moduli to ensure the sequence cycles through as many values as possible before repeating.

Notable prime numbers

Mersenne primes

A Mersenne prime has the form $2^p - 1$, where $p$ is itself prime. Not every such expression yields a prime ($2^{11} - 1 = 2047 = 23 \times 89$), but when it does, the result is a Mersenne prime.

As of 2024, 52 Mersenne primes are known. The largest known prime numbers are almost always Mersenne primes, because there's an especially efficient test for them (the Lucas-Lehmer test). The Great Internet Mersenne Prime Search (GIMPS) is a distributed computing project dedicated to finding more.

Fermat primes

A Fermat prime has the form $2^{2^n} + 1$. Only five are known:

• $n = 0$: 3
• $n = 1$: 5
• $n = 2$: 17
• $n = 3$: 257
• $n = 4$: 65,537

For $n = 5$, the result (4,294,967,297) is composite, as Euler showed. No additional Fermat primes have been found despite extensive searching.

Fermat primes have a surprising geometric connection: a regular polygon can be constructed with compass and straightedge if and only if its number of sides is a power of 2 times a product of distinct Fermat primes.

Twin primes

Twin primes are pairs of primes that differ by exactly 2: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), and so on. They seem to keep appearing no matter how far out you look, but whether there are infinitely many remains unproven (see the twin prime conjecture below).

Prime number conjectures

These are statements about primes that mathematicians believe to be true but haven't been able to prove. They represent some of the deepest open questions in mathematics.

Goldbach's conjecture

Every even integer greater than 2 can be written as the sum of two primes. For example: $4 = 2 + 2$, $10 = 5 + 5$, $28 = 11 + 17$. This has been verified computationally for numbers up to $4 \times 10^{18}$, but no one has found a general proof.

What makes this conjecture fascinating is the contrast between how simple it is to state and how resistant it is to proof.

Riemann hypothesis

The Riemann hypothesis concerns the Riemann zeta function and where its "non-trivial zeros" lie. It conjectures that all such zeros have a real part equal to $\frac{1}{2}$.

Why does this matter for primes? The zeta function encodes deep information about how primes are distributed. If the Riemann hypothesis is true, it would give us the tightest possible error bounds on the prime number theorem's approximation. It's widely considered the most important unsolved problem in mathematics.

Twin prime conjecture

This conjecture states that there are infinitely many pairs of primes differing by 2. In 2013, Yitang Zhang made a breakthrough by proving there are infinitely many prime pairs differing by at most 70,000,000. Subsequent work (notably by James Maynard and the Polymath project) reduced that bound to 246. Closing the gap from 246 to 2 remains open.

Computational aspects

Generating prime numbers

Beyond the Sieve of Eratosthenes, the segmented sieve breaks the range into smaller chunks to reduce memory usage, making it practical to find primes in very large ranges. These generation methods are essential tools in both mathematical research and applications like cryptography.

Primality proving

While probabilistic tests give high confidence, sometimes you need a proof that a number is prime. Deterministic algorithms like the AKS primality test (2002) can prove primality in polynomial time, which was a major theoretical breakthrough. In practice, elliptic curve primality proving (ECPP) is often faster for specific large numbers.

Factorization algorithms

Factoring large composites into primes is computationally hard, and this difficulty is what makes RSA encryption work. The best known general-purpose algorithm is the general number field sieve, which can factor numbers with hundreds of digits but still takes enormous computational resources. If someone discovered a fast factoring algorithm, much of modern cryptography would break.

Historical significance

Ancient Greek contributions

Euclid's Elements (circa 300 BCE) contains the proof that primes are infinite and the algorithm now called the Euclidean algorithm for finding GCDs. Eratosthenes, working around the same period, devised his sieve. These contributions are remarkable because they remain directly useful over 2,000 years later.

Fermat and Euler's work

Fermat's Little Theorem states that if $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$. This result is foundational for primality testing and cryptography.

Euler extended this with the totient function $\phi(n)$, which counts the integers from 1 to $n$ that are coprime to $n$. Euler's generalization of Fermat's theorem is central to how RSA encryption works.

Modern developments

The search for large primes continues through projects like GIMPS. The largest known prime (as of 2024) is a Mersenne prime with over 41 million digits. Meanwhile, the application of primes in cryptography, coding theory, and computer science has made number theory one of the most practically relevant branches of pure mathematics.

Prime numbers in other fields

Number theory connections

Primes are deeply connected to modular arithmetic (the math of remainders), Diophantine equations (equations where you seek integer solutions), and algebraic number theory (which generalizes primes to more abstract number systems). Nearly every major result in number theory either involves primes directly or depends on their properties.

Computer science applications

Beyond cryptography, primes appear in error-correcting codes (used in data transmission), hash table design, and pseudo-random number generation. The theoretical difficulty of problems like integer factorization also plays a central role in computational complexity theory.

Physics and quantum mechanics

There are intriguing connections between the distribution of prime numbers and the energy levels of certain quantum systems. The spacing of zeros of the Riemann zeta function statistically resembles the spacing of energy levels in quantum chaotic systems. These connections are still being explored and hint at deep, not-yet-understood links between number theory and physics.