Prime numbers: the building blocks of arithmetic

A prime number is an integer > 1 divisible only by 1 and itself. First 20 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.

Non-prime integers > 1 are called composite. They are products of smaller primes.

The number 1 is neither prime nor composite by mathematical convention.

Fundamental theorem of arithmetic

Every integer > 1 expresses uniquely (up to ordering) as product of primes. Proved by Euclid (~300 BCE) in Elements.

n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k

Examples:

• 12 = 2² × 3
• 60 = 2² × 3 × 5
• 360 = 2³ × 3² × 5
• 1000 = 2³ × 5³

Sieve of Eratosthenes

Ancient algorithm (Eratosthenes of Cyrene, ~240 BCE) to find all primes up to n:

1. Write all numbers 2 to n
2. Smallest uncrossed is prime: cross out all its multiples
3. Repeat with next prime
4. Stop when prime exceeds √n

Complexity: O(n log log n), very efficient for n < 10⁸.

Primality tests

1. Trial division

Check divisibility by primes p ≤ √n. O(√n). Works up to ~10⁹.

2. Miller-Rabin test

Probabilistic: error probability < 1/4^k for k iterations. Deterministic for specific bases up to 3.3 × 10¹⁴ (Miller 1976, Rabin 1980).

3. AKS primality test

Agrawal, Kayal, Saxena (2002): first deterministic polynomial algorithm. Historically important, slower than Miller-Rabin in practice.

4. ECPP

Used to certify giant primes. Largest prime proved by ECPP has ~40,000 digits.

Prime number theorem

Independently proved by Jacques Hadamard and Charles de la Vallée Poussin in 1896:

π(n) ~ n / ln(n)

where π(n) is number of primes ≤ n.

Prime density:

• Up to 100: 25 primes (25%)
• Up to 1,000: 168 (16.8%)
• Up to 1,000,000: 78,498 (7.85%)
• Up to 10⁹: 50,847,534 (5.08%)

Primes "thin out" but never end (Euclid's theorem: infinitely many primes).

Euclid's proof of infinitely many primes

Suppose finite primes: p₁, p₂, ..., p_n.

Consider N = p₁ · p₂ · ... · p_n + 1.

N not divisible by any p_i (remainder 1).

So N is prime or has prime factor not in list.

Contradiction → infinitely many primes. QED Euclid ~300 BCE.

Famous primes

Mersenne primes

M_p = 2^p − 1 with p prime. Largest known prime (late 2024) is 2^136,279,841 − 1 (51st Mersenne prime), with ~41 million digits. Project GIMPS: volunteer distributed computing.

Fermat primes

F_n = 2²ⁿ + 1. Fermat conjectured (1640) all F_n prime. Euler (1732) showed F₅ = 4,294,967,297 = 641 × 6,700,417. Only F₀..F₄ (3, 5, 17, 257, 65537) known prime.

Twin primes

Pairs (p, p+2) both prime. Examples: (3,5), (5,7), (11,13), (17,19), (29,31).

Twin prime conjecture (open): infinitely many pairs. Yitang Zhang (2013) proved infinitely many primes at distance < 70 million. Later reduced to < 246.

Sophie Germain primes

p prime such that 2p + 1 is also prime. Used in cryptography. Studied by Sophie Germain (1831).

Cryptography and primes

Security of major cryptographic algorithms relies on difficulty of factoring large semiprimes (product of two primes):

RSA (Rivest-Shamir-Adleman, 1977)

Public and private keys based on two ~300-600 digit primes. Decrypting without knowing p and q requires factoring n = p·q, computationally infeasible.

RSA-2048 current security. RSA-1024 broken in 2019.

Quantum threat

Shor's algorithm (1994) on quantum computers factors n in polynomial time. RSA will fall when large-scale quantum computers exist. NIST standardizing post-quantum cryptography.

Important arithmetic functions

Euler's totient φ(n)

Number of integers 1 to n coprime to n.

Formula: φ(n) = n · Π(1 − 1/p) for primes p dividing n.

• φ(10) = 4 (integers 1, 3, 7, 9 coprime with 10)
• φ(p) = p − 1 for p prime

Euler's theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). Fundamental in cryptography.

Divisor function σ(n)

Sum of all positive divisors.

σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28.

Perfect numbers

Integers equal to sum of proper divisors:

• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14
• 496, 8128, 33,550,336, ...

Euler's formula: even n is perfect iff n = 2^p-1(2^p − 1) with 2^p − 1 Mersenne prime. Unknown if odd perfect numbers exist (open problem).

Amicable numbers

Pair (a, b) such that σ(a) − a = b and σ(b) − b = a. First: (220, 284), (1184, 1210), (2620, 2924).

Famous open conjectures

Goldbach's conjecture (1742)

Every even > 2 is sum of two primes. Verified up to ~4 × 10¹⁸, not proved.

Riemann hypothesis (1859)

All non-trivial zeros of Riemann zeta function have real part = 1/2. Implies very precise prime distribution. Millennium Prize: $1 million.

Twin prime conjecture

Infinitely many pairs (p, p+2) both prime.

Legendre conjecture

There's always at least one prime between n² and (n+1)².

Largest known prime

As of October 2024: 2^136,279,841 − 1

• 41,024,320 digits
• 51st Mersenne prime
• Found by Luke Durant via GIMPS (volunteer GPU computing)
• Verification time: ~1 month on modern CPU

Advanced factorization algorithms

Pollard's rho

Probabilistic O(n^1/4). Efficient for semiprimes with small-to-medium factors.

Quadratic Sieve (QS)

Sub-exponential, practical up to ~10¹⁰⁰.

Number Field Sieve (NFS)

Best known classical algorithm: L(1/3) complexity. Broke RSA-768 in 2009.

Shor's algorithm (quantum)

Polynomial O((log n)²·log log n). Will break RSA when practical quantum computers exist.

Modern applications

Cryptography

• RSA: e-commerce, SSL/TLS, digital signatures
• Diffie-Hellman: key exchange
• Elliptic curves (ECC): more efficient alternative

Pseudorandom generators

Blum Blum Shub: generator based on factoring difficulty, cryptographically secure.

Hash functions

Some algorithms use prime moduli for better distribution (universal hashing).

Coding theory

Reed-Solomon over GF(pⁿ) for error correction in CDs, QR codes, DVB.

Distributed computing

GIMPS Mersenne search: volunteer global primality testing.

Examples

1. Factorizing 360

360 = 2³ × 3² × 5
Divisors: (3+1)(2+1)(1+1) = 24
List: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360

2. Carmichael number

561 = 3 × 11 × 17. Composite but passes Fermat test for every coprime base — "strong pseudo-prime". Discovered by Korselt 1899, cataloged by Carmichael 1910.

3. Primality of 1,000,003

√1,000,003 ≈ 1000. Test divisibility by primes ≤ 1000. None found → 1,000,003 is prime.

Excel / Sheets / Python functions

Python

from sympy import isprime, primerange, factorint, primepi

isprime(1000003)     # True
list(primerange(1, 50))  # [2, 3, 5, 7, ...]
factorint(360)       # {2: 3, 3: 2, 5: 1}
primepi(10**6)       # 78498

Excel / Sheets

No native prime function. Use Python/VBA or custom LAMBDA formula (Excel 365).

Common mistakes

• Is 1 prime? No, it's a unit. Neither prime nor composite by convention
• 2 is even and prime: the only one
• Crypto with "small primes": RSA with keys < 2048 bits is obsolete

FAQ

Why isn't 1 prime?

Convention preserves fundamental theorem of arithmetic: if 1 were prime, 6 = 1 × 2 × 3 = 1 × 1 × 2 × 3 would have multiple factorizations.

How to find large primes?

For curiosity: GIMPS volunteer project. For cryptography: pseudorandom generation + Miller-Rabin test.

How many primes up to a million?

π(10⁶) = 78,498. About 1 in 12-13 is prime in that range.

Twin primes infinite?

Open conjecture. Zhang 2013 proof: infinitely many pairs at distance < 70 million. Reduced to < 246 via Polymath.

Is RSA safe?

Yes for keys ≥ 2048 bits (for now). Future threat: quantum computers. NIST standardizing post-quantum.

Updated July 2026