Primes and Composite Numbers

Trial division and the elementary structure of primes are not merely historical curiosities; they underlie practical and theoretical machinery across mathematics and computing. In cryptography, the RSA public-key system relies on the practical difficulty of factoring large composite numbers (the product of two large primes) even though existence of a factorization is guaranteed by the theorem above — the gap between "a factorization exists" and "a factorization is easy to find" is precisely what protects encrypted data. In computer science, trial division (and its refinements, such as the sieve methods and probabilistic tests like Miller–Rabin) forms the baseline algorithm against which faster primality tests and factoring algorithms are measured. In pure number theory, the existence-of-factorization result proved here is the first half of the Fundamental Theorem of Arithmetic, whose uniqueness half underlies virtually all further arithmetic (computing greatest common divisors via prime exponents, defining arithmetic functions like $\varphi$ and $\sigma$, and studying Diophantine equations). In statistics and random number generation, prime moduli are chosen for linear congruential generators because primality guarantees useful algebraic structure (Modular Arithmetic modulo a prime forms a field). Finally, the question this article opens the door to — how many primes are there, and how are they spaced? — leads directly to Euclid's proof of the Infinitude of Primes and, further out, to the Prime Number Theorem and the Riemann Hypothesis.

Ask the tutor: How does Euclid's Lemma turn this existence proof into a full proof of unique factorization?

Think of the positive integers greater than $1$ as objects sitting on an assembly line, and multiplication as the operation of gluing two smaller objects together. Some objects — the primes $2, 3, 5, 7, 11, 13, \dots$ — cannot be produced by gluing two smaller pieces (other than the trivial gluing with the identity factor $1$). Every other object, the composites, can be pulled apart into at least two nontrivial pieces. If those pieces are themselves composite, pull them apart again; since the pieces strictly shrink and are bounded below by $2$, this process must terminate, and it terminates exactly when every remaining piece is prime. That intuitive "pulling apart until stuck" process is precisely the content of the proof below, made rigorous through strong induction. Trial division formalizes the search for a nontrivial divisor. To test whether $n$ is prime, we do not need to check every integer from $2$ to $n-1$: if $n = ab$ with $a,b > 1$, then $a$ and $b$ cannot both exceed $\sqrt{n}$, since their product would then exceed $n$. So it suffices to search for a divisor no larger than $\sqrt{n}$. This single inequality is what makes primality testing by hand feasible even for numbers in the hundreds.

This theorem is precisely what licenses the trial-division algorithm: to test $n$ for primality, one only checks candidate divisors $2, 3, 4, \dots, \lfloor \sqrt{n} \rfloor$ (or more efficiently just $2$ and the odd numbers up to $\sqrt n$); finding none of them dividing $n$ certifies primality.

Example 1 — testing a moderately large odd composite by hand: $n = 391$. We want to know whether $391$ is prime, and if not, find its factorization, using trial division only up to $\sqrt{391}$. First, $\sqrt{391} \approx 19.77$, so by the Trial Division Bound Theorem it suffices to test primes up to $19$: namely $2, 3, 5, 7, 11, 13, 17, 19$.

• $391$ is odd, so $2 \nmid 391$.
• Digit sum $3+9+1 = 13$, not divisible by $3$, so $3 \nmid 391$.
• Does not end in $0$ or $5$, so $5 \nmid 391$.
• $391 / 7 = 55.857\ldots$, not an integer ($7 \times 55 = 385$, $391 - 385 = 6 \neq 0$), so $7 \nmid 391$.
• $391 / 11 = 35.5\ldots$ ($11 \times 35 = 385$, remainder $6$), so $11 \nmid 391$.
• $391 / 13 = 30.07\ldots$ ($13 \times 30 = 390$, remainder $1$), so $13 \nmid 391$.
• $391 / 17 = 23.0$ exactly: check $17 \times 23 = 391$. Indeed $17 \times 23 = 17\times20 + 17\times3 = 340+51=391$. ✓

So $17$ divides $391$, with $391 = 17 \times 23$. Since $23$ is itself prime (its only divisors below $\sqrt{23}\approx 4.8$ to check are $2,3$; $23$ is odd and $2+3=5$ not divisible by $3$), we conclude

a product of two primes. Note that we found the factor $17$ before reaching $19 = \lfloor\sqrt{391}\rfloor$, consistent with the theorem's guarantee that a composite number's smallest nontrivial factor lies at or below $\sqrt{n}$.

Example 2 — a number requiring the full induction argument to unwind: $n = 2 \times 3 \times 5 \times 7 + 1 = 211$. This example is chosen because $211$ is one more than the product of the first four primes — a classic "does the pattern break" test case, and it illustrates that trial division, not the appearance of the number, is what determines primality. Compute $\sqrt{211} \approx 14.53$, so we must test primes up to $14$: that is $2,3,5,7,11,13$.

• $211$ is odd: $2 \nmid 211$.
• Digit sum $2+1+1=4$: not divisible by $3$.
• Does not end in $0$ or $5$: $5 \nmid 211$.
• $211/7 = 30.14\ldots$ ($7\times 30 = 210$, remainder $1$): $7 \nmid 211$.
• $211/11 = 19.18\ldots$ ($11\times19=209$, remainder $2$): $11 \nmid 211$.
• $211/13 = 16.23\ldots$ ($13\times16=208$, remainder $3$): $13 \nmid 211$.

No prime up to $14$ divides $211$, and by the Trial Division Bound Theorem this certifies that $211$ is prime — there is no need to test $17$ or beyond, since any composite factorization would force a factor $\le \sqrt{211}$. This illustrates the induction proof concretely: $211$ falls into the "Case 1" branch of the inductive step ($m=1$), because its smallest divisor greater than $1$ turns out to be $211$ itself.