Pick any number. Any number at all. Now try to smash it into smaller pieces — divide it by 2, by 3, by 7, by whatever feels right — until you can’t divide anymore. What you’re left with, those irreducible atomic fragments, are prime numbers. And here’s the thing: they’ve been sitting quietly at the foundation of mathematics for over two thousand years, and right now, at this very moment, they are part of the mathematics that can help protect your credit card number as it flies across the internet.
That’s not a metaphor. Let’s build up to exactly why.
What Is a Prime, Really?
A prime number is a whole number greater than 1 that has exactly two divisors: 1 and itself. That’s it. No shortcuts, no tricks.
- 2 is prime (divisors: 1 and 2) — and it’s the only even prime
- 3 is prime (divisors: 1 and 3)
- 4 is not prime (divisors: 1, 2, and 4) — it’s called composite
- 5 is prime
- 6 is not (1, 2, 3, 6)
- 7 is prime
The first few primes run: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … and they keep going. Forever. (We’ll prove that in a moment.)
The word “prime” comes from the Latin primus, meaning first or fundamental — and that name is earned. Every whole number greater than 1 is either a prime or can be written as a unique product of primes. This is the Fundamental Theorem of Arithmetic, and it’s one of the most quietly powerful facts in all of mathematics.
For example:
- 12 = 2 × 2 × 3
- 60 = 2 × 2 × 3 × 5
- 100 = 2 × 2 × 5 × 5
- 2,310 = 2 × 3 × 5 × 7 × 11
The factorization is always unique — there’s only one way to break any number down into its prime pieces. Primes are the atoms of arithmetic.
There Are Infinitely Many Primes (A Proof You Can Follow)
Around 300 BCE, the Greek mathematician Euclid proved that primes never run out. His argument is one of the most elegant in mathematics, and you can follow every step.
Suppose — just as a thought experiment — that the list of primes is finite. Say the complete list is: p₁, p₂, p₃, … pₙ. That’s all of them, every last one.
Now build a new number. Multiply all of them together and add 1:
N = (p₁ × p₂ × p₃ × … × pₙ) + 1
Ask yourself: is N divisible by any prime on our list? Try p₁ — when you divide N by p₁, you get a remainder of 1 (because N is exactly one more than a multiple of p₁). Same story for p₂, p₃, every single one. None of them divide N evenly.
But N is a whole number greater than 1, so by the Fundamental Theorem of Arithmetic, it must have a prime factor. That prime factor isn’t on our list. Contradiction! Our assumption that the list was finite must be wrong.
Therefore, there are infinitely many primes. ∎
That little square at the end is the traditional mathematician’s way of saying “I’m done, and I’m satisfied.” You should be too — that argument required no calculus, no fancy notation, just pure logical judo.
The Mysterious Distribution of Primes
Knowing primes go on forever raises a natural follow-up: how often do they appear? Are they evenly spread out, or do they thin out as numbers get bigger?
They thin out — but in a beautifully predictable way. The Prime Number Theorem, proved independently by Hadamard and de la Vallée Poussin in 1896, tells us:
The number of primes up to N is approximately N / ln(N)
where ln(N) is the natural logarithm of N (the power you’d raise e ≈ 2.718 to in order to get N).
Let’s check it with real numbers. How many primes are there up to 1,000?
- Actual count: 168
- Estimate: 1000 / ln(1000) = 1000 / 6.908 ≈ 145
Not bad for a simple formula! The approximation gets proportionally better as N grows. Among the first million numbers, about 1 in every 14 is prime. Among the first billion, about 1 in every 21. Primes become rarer, but they never disappear.
There are also long stretches with no primes at all — called prime deserts or prime gaps. Want a gap of at least 1,000 consecutive composite numbers? Just look at the sequence 1001! + 2, 1001! + 3, 1001! + 4, … 1001! + 1001. Every one of those numbers is composite (1001! + 2 is divisible by 2, 1001! + 3 is divisible by 3, and so on). Primes can hide for as long as you like — they just always come back.
The Real-World Payoff: RSA Encryption
Here’s where the story gets urgent. RSA encryption is a classic and still important example of prime-number mathematics in digital security. It has been widely used on the web and still appears in some certificates and signatures, though modern HTTPS/TLS often uses elliptic-curve key exchange plus symmetric encryption, and tap-to-pay systems use a broader set of cryptographic protocols rather than simply RSA. RSA’s security rests on one beautifully asymmetric fact about primes:
Multiplying two large primes together is easy. Factoring the result back into those two primes is, for all practical purposes, impossible.
This asymmetry — easy one way, brutally hard the other — is one of the padlocks on modern digital communication.
How RSA Works (The Key Ideas, With Numbers)
Let me walk you through a toy version with small numbers so the logic is transparent. Real RSA uses numbers hundreds of digits long, but the math is identical.
Step 1: Choose two primes.
Pick p = 61 and q = 53.
Step 2: Compute their product.
n = p × q = 61 × 53 = 3,233
This number n is your public modulus — you share it with the world.
Step 3: Compute Euler’s totient.
φ(n) = (p − 1)(q − 1) = 60 × 52 = 3,120
This counts how many numbers from 1 to 3,232 share no common factor with 3,233. You keep this secret.
Step 4: Choose a public exponent.
Pick e = 17 (it just needs to share no common factor with 3,120). This is your public key: the pair (n = 3233, e = 17).
Step 5: Find the private exponent.
Find d such that e × d ≡ 1 (mod φ(n)), meaning e × d leaves remainder 1 when divided by 3,120. Working this out (via an algorithm called the Extended Euclidean Algorithm) gives d = 2,753. This is your private key — never shared.
Encrypting a message:
Say your message is the number M = 65 (in practice, text gets converted to numbers). The encrypted message C is:
C = M^e mod n = 65^17 mod 3233 = 2,790
You can share 2,790 openly. Without knowing d, no one can reverse it.
Decrypting:
The recipient uses the private key:
M = C^d mod n = 2790^2753 mod 3233 = 65 ✓
Back to the original message, exactly.
Why Can’t an Attacker Just Factor n?
In our toy example, factoring 3,233 is trivial — you could do it in seconds. But real RSA uses n values that are 2,048 bits long, meaning n is a number with roughly 617 decimal digits. The two prime factors p and q are each about 309 digits long.
The fastest known factoring algorithms on the fastest computers on Earth would take longer than the current age of the universe to factor such a number by brute force. The mathematical hardness of factoring is the lock; the ease of multiplication is the key. Primes make this asymmetry possible.
One More Wonder: Twin Primes
Before we close, let me leave you with an unsolved mystery — because mathematics is full of them, and they’re part of the fun.
Twin primes are pairs of primes that differ by exactly 2: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43) … Do twin primes go on forever?
Nobody knows. The Twin Prime Conjecture says yes — there are infinitely many such pairs — but despite centuries of effort and some spectacular recent progress (in 2013, Yitang Zhang proved that there are infinitely many prime pairs differing by at most 70 million, a gap since narrowed dramatically), a complete proof remains out of reach.
That’s one of the things I love most about prime numbers: they are simple enough to explain to a child, yet deep enough to stump every mathematician who has ever lived.
The One Idea to Take With You
Here it is, the mental model worth carrying:
Large primes can be found efficiently, but products of large primes can be hard to take apart — and that asymmetry is a feature, not a bug.
Factoring is hard. Multiplying is easy. That gap between the two is one of the ideas that makes secure communication on the internet possible. Every time you buy something online, you may be relying, directly or indirectly, on a 2,300-year-old mathematical object to help keep your secrets safe.
Next time you see that little padlock icon in your browser, you’ll know one of the mathematical ideas that helped make it possible.
Leave a Reply