Prime Numbers and Primality Testing

⚡ Key Takeaways

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. Every integer factors uniquely into primes (the Fundamental Theorem of Arithmetic), making primes the multiplicative atoms of number theory. Primality testing answers "is $n$ prime?" — solved efficiently by probabilistic tests (Miller–Rabin) and, since 2002, by a deterministic polynomial-time algorithm (AKS). Primes underpin modern cryptography (RSA, Diffie–Hellman). Studied since Euclid (~300 BCE); deep questions (twin primes, Riemann Hypothesis) remain open today.

💡 The Core Insight

Primes are defined by indivisibility but behave like atoms: their power comes from the unique factorization of integers. Two distinct circles of ideas grow from this — (1) the multiplicative theory: how primes combine, distribute, and density (Prime Number Theorem); and (2) the algorithmic question: given $n$ , can we decide primality and find factors quickly? Remarkably, deciding whether $n$ is prime is computationally easy, while factoring $n$ into primes is believed to be hard — an asymmetry that secures the digital world.

DefinitionPrime and Composite

An integer $p$ is prime if $p > 1$ and its only positive divisors are $1$ and $p$ . An integer $n > 1$ that is not prime is composite: there exist integers $a, b$ with $1 < a, b < n$ and $n = ab$ . The integer $1$ is a unit — neither prime nor composite. Divisibility $d \mid n$ means $n = dk$ for some integer $k$ .

TheoremFundamental Theorem of Arithmetic

Every integer $n > 1$ can be written as a product of primes, and this representation is unique up to the order of the factors.

TheoremEuclid's Lemma

If a prime $p$ divides a product $ab$ , then $p \mid a$ or $p \mid b$ .

TheoremInfinitude of Primes — Euclid

There are infinitely many prime numbers.

TheoremPrime Number Theorem

Let $\pi(x)$ count primes $\le x$ . Then $\pi(x)$ is asymptotic to $x/\ln x$ .

ProofUniqueness of Factorization

We prove the uniqueness part of Fundamental Theorem of Arithmetic using Euclid's Lemma. 1. Setup. Suppose some integer $> 1$ has two prime factorizations. By well-ordering, let $n$ be the smallest such integer:

n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s.

2. Apply Euclid's Lemma. Since $p_1 \mid n = q_1 \cdots q_s$ , repeated application of equation $[3]$ shows $p_1 \mid q_j$ for some $j$ . 3. Match the factors. Because $q_j$ is prime, its only divisors are $1$ and $q_j$ ; since $p_1 > 1$ , we get $p_1 = q_j$ . 4. Cancel and descend. Dividing both sides by $p_1 = q_j$ gives a smaller integer $n/p_1 > 1$ with two factorizations (the $p$ 's minus $p_1$ , the $q$ 's minus $q_j$ ). By minimality of $n$ , these must agree, forcing the original factorizations to agree. 5. Conclusion. No smallest counterexample exists, so factorization is unique up to order. $\blacksquare$

∎

ProofFermat's Little Theorem — Basis of Fast Testing

If $p$ is prime and $\gcd(a,p)=1$ , then $a^{p-1} \equiv 1 \pmod p$ . 1. Consider the residues $\{a, 2a, 3a, \dots, (p-1)a\} \pmod p$ . 2. These are a permutation of $\{1, 2, \dots, p-1\}$ : if $ia \equiv ja$ then $p \mid (i-j)a$ , and since $p \nmid a$ , we get $i \equiv j$ , so all are distinct and nonzero. 3. Multiply them all together:

a^{p-1}(p-1)! \equiv (p-1)! \pmod p.

4. Since $\gcd((p-1)!, p) = 1$ , cancel to obtain $a^{p-1} \equiv 1 \pmod p$ . $\blacksquare$ This gives a primality test: if $a^{n-1} \not\equiv 1 \pmod n$ for some $a$ coprime to $n$ , then $n$ is definitely composite.

∎

mathematician · Euclid of Alexandria | fl. ~300 BCE

Euclid's Elements, Book IX, contains the earliest surviving proof of the infinitude of primes (Proposition 20) and the foundational results on divisibility that became Euclid's Lemma. His method — assume finiteness, construct a new prime — is a paradigm of proof by contradiction still taught unchanged 2,300 years later. The Elements also gives the Euclidean algorithm for the greatest common divisor, the computational engine behind Bézout's identity and thus behind Euclid's Lemma itself.

🧠 Intuition

Think of integers as Lego structures and primes as the indivisible bricks. Multiplication snaps bricks together; the Fundamental Theorem says each structure has a unique parts list. Now, why are primes hard to predict? Because primality is a global property — to know $p$ is prime you must rule out every potential divisor. Yet there is order in the chaos: primes near $x$ appear roughly once every $\ln x$ integers (PNT), so around a billion you expect a prime about every 21 numbers. The asymmetry powering cryptography: checking primality only needs a few modular exponentiations (fast), but factoring a 600-digit semiprime would take longer than the age of the universe on classical hardware.

Figure

The prime counting function π(x) tracking x/ln x

ExampleFactoring and Verifying Primality of 97

Given: Determine whether $n = 97$ is prime.

Steps: 1. Trial division only needs primes $\le \sqrt{97} \approx 9.85$ , i.e. test $2, 3, 5, 7$ . 2. $97$ is odd → not divisible by $2$ . 3. Digit sum $9+7 = 16$ , not divisible by $3$ . 4. Does not end in $0$ or $5$ → not divisible by $5$ . 5. $97 = 7 \times 13 + 6$ → not divisible by $7$ . 6. All primes up to $\sqrt{97}$ fail, so no nontrivial factor exists.

Answer: $\boxed{97 \text{ is prime}}$ (the 25th prime).

ExampleMiller–Rabin Test on n = 561 (a Carmichael number)

Given: Apply the Miller–Rabin test to $n = 561$ with witness $a = 2$ .

Steps: 1. Write $n - 1 = 560 = 2^4 \cdot 35$ , so $d = 35$ , $s = 4$ . 2. Compute $x_0 = 2^{35} \bmod 561$ . By repeated squaring: $2^{35} \equiv 263 \pmod{561}$ . 3. Since $x_0 = 263 \neq 1$ and $\neq 560$ , square: $x_1 = 263^2 \bmod 561 = 166$ . 4. $x_2 = 166^2 \bmod 561 = 67$ ; $x_3 = 67^2 \bmod 561 = 1$ . 5. We reached $1$ from $67 \neq 560$ : this is a nontrivial square root of 1, proving $561$ composite. 6. Indeed $561 = 3 \times 11 \times 17$ . Note: the weaker Fermat test gives $2^{560} \equiv 1 \pmod{561}$ — it is fooled! Miller–Rabin catches it.

Answer: $\boxed{561 \text{ is composite}}$ ; witness $a=2$ exposes it where the Fermat test fails.

⚠️ Common mistake

"Passing the Fermat test means $n$ is prime." False. There exist composite $n$ (the Carmichael numbers: $561, 1105, 1729, \dots$ ) for which $a^{n-1}\equiv 1 \pmod n$ for every $a$ coprime to $n$ . The Fermat test cannot detect these. Miller–Rabin fixes this by additionally checking nontrivial square roots of $1$ . Never rely on a single Fermat test for security-grade primality.

⚠️ Common mistake

"1 is prime." No — $1$ is a unit. If $1$ were prime, unique factorization in equation $[2]$ would fail, since $6 = 2\cdot3 = 1\cdot2\cdot3 = 1^2\cdot2\cdot3 = \cdots$ . Excluding $1$ is a definitional choice that preserves the Fundamental Theorem.

Counterexample

Mersenne numbers are not all prime. A common belief is that $2^p - 1$ is prime whenever $p$ is prime. Counterexample: $p = 11$ is prime, but

2^{11} - 1 = 2047 = 23 \times 89.

So primality of the exponent is necessary but not sufficient. The largest known primes are Mersenne primes precisely because the Lucas–Lehmer test makes them cheap to verify — not because all such numbers are prime.

connection

Prime numbers sit at the crossroads of many fields. Modular Arithmetic turns $\mathbb{Z}/p\mathbb{Z}$ into a field exactly when $p$ is prime, the algebraic source of Fermat's Little Theorem. Group Theory explains primality tests: the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$ has order $n-1$ iff $n$ is prime, and Lagrange's theorem forces $a^{n-1}\equiv 1$ . The Riemann Zeta Function encodes the distribution of primes through its Euler product $\prod_p (1-p^{-s})^{-1}$ , linking primality to complex analysis. Computational Complexity frames the deep contrast: primality is in P (AKS), while integer factorization's hardness is the open foundation of Public-Key Cryptography.

🔬 Where this appears

⏳ History

- ~300 BCE — Euclid proves the infinitude of primes and Euclid's Lemma in the Elements; describes the Sieve of Eratosthenes's logical basis.

- ~240 BCE — Eratosthenes of Cyrene devises his sieve, an efficient method to list all primes up to

N

.

- 1640 — Pierre de Fermat states Fermat's Little Theorem and studies Fermat numbers

2^{2^k}+1

.

- 1736 — Leonhard Euler proves Fermat's Little Theorem and the Euler product formula, connecting

\zeta(s)

to primes; proves

\sum 1/p

diverges.

- 1796 — Carl Friedrich Gauss (age 15) conjectures the Prime Number Theorem from prime tables; later formalizes congruences in Disquisitiones Arithmeticae (1801).

- 1859 — Bernhard Riemann's memoir links

\pi(x)

to the zeros of

\zeta(s)

, posing the Riemann Hypothesis.

- 1896 — Hadamard and de la Vallée Poussin independently prove the Prime Number Theorem.

- 1976–78 — Diffie, Hellman, then Rivest–Shamir–Adleman build public-key cryptography on prime-based hardness.

- 1980 / 2002 — Miller–Rabin probabilistic test (Rabin, 1980); Agrawal–Kayal–Saxena (AKS) give the first deterministic polynomial-time primality test, proving PRIMES ∈ P.

open-problem

Several central questions about primes remain unsolved:

Riemann Hypothesis: all nontrivial zeros of $\zeta(s)$ have real part $\tfrac12$ . This would give the sharpest possible error term in the Prime Number Theorem, $\pi(x) = \mathrm{Li}(x) + O(\sqrt{x}\,\ln x)$ .
Twin Prime Conjecture: infinitely many primes $p$ with $p+2$ also prime. Zhang (2013) proved infinitely many prime gaps $< 70{,}000{,}000$ ; the bound is now $246$ (Polymath/Maynard).
Goldbach's Conjecture: every even integer $> 2$ is a sum of two primes — verified to $4\times10^{18}$ but unproven.
Practical factoring vs. quantum computers: Shor's algorithm factors in polynomial time on a quantum computer, threatening RSA — motivating post-quantum cryptography. The exact classical complexity of factoring is unknown (not proven to be NP-hard, not known to be in P).

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also