Prime Numbers: The Atoms of Arithmetic

Every integer is built from primes.

84 = 2² × 3 × 7. That's its prime factorization — and it's the only one. No other combination of primes multiplies to 84. Every number has a unique prime fingerprint.

Primes are the multiplicative atoms. Everything else is a molecule.

That's the unlock. Just as matter reduces to chemical elements, numbers reduce to primes. The number 2 is an atom. The number 4 is a molecule (2 × 2). The number 6 is a molecule (2 × 3). Primes can't be broken down further; composites can. This atomic structure underlies all of number theory.

The Definition

A prime number is a positive integer greater than 1 that has exactly two positive divisors: 1 and itself.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Why "exactly two divisors"? This excludes 1 (which has only one divisor) and ensures primes are the indivisible building blocks.

A composite number has more than two divisors.

4 = 2 × 2 has divisors 1, 2, 4. 6 = 2 × 3 has divisors 1, 2, 3, 6.

Every integer > 1 is either prime or composite.

The First Few 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, ...

Notice:

• 2 is the only even prime (all other evens are divisible by 2)
• Primes thin out but never stop
• No simple formula generates them

There Are Infinitely Many Primes

Euclid proved this around 300 BCE. His proof is beautiful:

Suppose there are only finitely many primes: p₁, p₂, ..., pₙ.

Consider N = p₁ × p₂ × ... × pₙ + 1.

N is not divisible by any pᵢ (dividing leaves remainder 1).

So either N is prime, or N has a prime factor not in our list.

Either way, our "complete" list missed a prime.

Contradiction. There must be infinitely many primes. ∎

Checking for Primality

To test if n is prime:

Naive method: Check if any number from 2 to n-1 divides n.

Better: Only check up to √n. If n = a × b with a ≤ b, then a ≤ √n.

Practical: Only check prime divisors up to √n.

Is 101 prime? √101 ≈ 10.05. Check primes ≤ 10: 2, 3, 5, 7. 101 ÷ 2 = 50.5 ✗ 101 ÷ 3 = 33.67 ✗ 101 ÷ 5 = 20.2 ✗ 101 ÷ 7 = 14.43 ✗

None divide evenly. 101 is prime.

The Sieve of Eratosthenes

To find all primes up to n:

1. List numbers 2, 3, 4, ..., n
2. Circle 2 (first prime). Cross out all multiples of 2.
3. Circle 3 (next uncrossed). Cross out all multiples of 3.
4. Continue: circle next uncrossed, cross out its multiples.
5. Stop when you've processed up to √n.

All remaining uncrossed numbers are prime.

This 2,200-year-old algorithm is still practical for generating primes.

Prime Distribution

Primes become rarer as numbers grow, but they never stop.

Among the first 100 integers: 25 primes (25%) Among integers up to 1,000: 168 primes (16.8%) Among integers up to 1,000,000: 78,498 primes (7.8%)

The Prime Number Theorem quantifies this:

π(n) ≈ n / ln(n)

where π(n) counts primes up to n. Primes thin out logarithmically.

Twin Primes

Twin primes are pairs differing by 2: (3,5), (5,7), (11,13), (17,19), (29,31), ...

Are there infinitely many twin primes?

We don't know. The Twin Prime Conjecture says yes, but it remains unproven despite massive effort.

In 2013, Yitang Zhang proved there are infinitely many prime pairs differing by at most 70 million. That bound has been reduced to 246. But the gap to 2 remains open.

Goldbach's Conjecture

Every even number greater than 2 is the sum of two primes.

4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 10 = 5 + 5 = 3 + 7 ...

Verified for all even numbers up to 4 × 10¹⁸. Still unproven in general.

One of the oldest unsolved problems in mathematics (1742).

Special Primes

Mersenne primes: Primes of the form 2ᵖ - 1. Examples: 3, 7, 31, 127, 8191, ... The largest known primes are Mersenne primes.

Fermat primes: Primes of the form 2^(2ⁿ) + 1. Only five known: 3, 5, 17, 257, 65537.

Sophie Germain primes: p where 2p + 1 is also prime. Examples: 2, 3, 5, 11, 23, 29, ...

Primes in Cryptography

RSA encryption:

1. Choose two large primes p and q.
2. Compute n = p × q.
3. n is public; p and q are secret.

Security relies on the difficulty of factoring n back into p × q.

For a 2048-bit n (about 617 digits), factoring with current technology would take longer than the age of the universe.

Primes protect your data.

Why Primes Are Mysterious

We know:

• There are infinitely many primes
• They thin out logarithmically
• Their exact distribution follows the Riemann Hypothesis (probably)

We don't know:

• A formula to generate all primes
• Whether twin primes are infinite
• Whether Goldbach's conjecture is true
• Whether the Riemann Hypothesis is true

Simple definitions, infinite depth.

The Core Insight

Primes are the atoms from which all integers are built.

Every number factors uniquely into primes. Understanding primes means understanding the multiplicative structure of integers.

But primes resist easy description. They appear randomly, yet they're completely determined. Their distribution follows patterns we can approximate but not fully explain. The simplest building blocks pose the hardest questions.

Part 2 of the Number Theory series.

Previous: What Is Number Theory? The Queen of Mathematics Next: The Fundamental Theorem of Arithmetic: Unique Factorization