Prime Factorization

If integers are the atoms of arithmetic, primes are the protons. Every positive integer above $1$ breaks down into primes in exactly one way, and that uniqueness is the single most important fact in all of elementary number theory. It is what makes modular arithmetic well-behaved, what makes RSA encryption a one-way street (multiplying two huge primes is fast; factoring their product takes geological time on classical hardware), and what makes “find a hash collision” a meaningful challenge in cryptocurrency proof-of-work. Cantor used uniqueness of factorisation to encode finite sets as integers; Gödel used it to encode logical proofs as integers. The Fundamental Theorem of Arithmetic earns its name.

Primes and composites

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$. Otherwise (and $n > 1$) it is composite. The integer $1$ is neither — treating it as prime would break uniqueness of factorisation (you could insert any number of $1$ factors).

The Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be written as $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ where the $p_i$ are distinct primes and the $a_i \geq 1$, and this representation is unique up to the order of the factors. Existence follows from strong induction: either $n$ is prime (done) or $n = ab$ for some $1 < a, b < n$, both of which factor by the induction hypothesis.

Uniqueness requires a deeper tool, Euclid’s lemma: if a prime $p$ divides $ab$, then $p \mid a$ or $p \mid b$. Proof: if $p \nmid a$, then $\gcd(p, a) = 1$ (the only divisors of $p$ are $1$ and $p$). By Bezout, $sp + ta = 1$; multiplying by $b$ gives $spb + tab = b$, and since $p \mid ab$, $p$ divides both terms on the left, hence $p \mid b$. Iterating Euclid’s lemma forces any two factorisations of $n$ to match prime-by-prime.

The Sieve of Eratosthenes

To list every prime $\leq N$: write $2, 3, \ldots, N$. Cross out the multiples of $2$ (except $2$ itself); move to the next surviving number ($3$) and cross out its multiples; continue with $5, 7, \ldots$ up to $\lfloor \sqrt{N} \rfloor$. Whatever survives is prime. Reason for stopping at $\sqrt{N}$: a composite $n \leq N$ must have a divisor $\leq \sqrt{n} \leq \sqrt{N}$, so it would have already been crossed out.

Euclid’s proof of infinitely many primes

Suppose for contradiction the complete list of primes is $p_1, p_2, \ldots, p_k$. Consider $N = p_1 p_2 \cdots p_k + 1$. Then $N > 1$, so it has a prime factor $p$. But $p$ cannot be any $p_i$, because dividing $N$ by $p_i$ leaves remainder $1$. So $p$ is a prime missing from our supposedly complete list — contradiction. (Note: $N$ itself is not necessarily prime; the argument only needs that some prime factor of $N$ lies outside the list.)

Pause and think: Why does the FTA fail if we allow $1$ as a prime? Try writing the factorisation of $12$ in two ways using $1$ as a permitted factor — you will see immediately why $1$ has to be excluded.

Try it

• Predict first: how many primes lie between $1$ and $30$? Then run the Sieve mentally (cross out multiples of $2, 3, 5$; $\lfloor \sqrt{30} \rfloor = 5$, so stop there) and count.
• Factorise $2520$ into primes. (It is famous for having lots of small factors.) Use your factorisation to compute the number of positive divisors of $2520$.
• Verify Euclid’s construction with ${2, 3}$ as the “complete” list: $N = 2 \cdot 3 + 1 = 7$. Is $7$ prime? Repeat with ${2, 3, 5, 7, 11, 13}$: is $N = 30031$ prime? (It is not — see if you can factor it.)
• Two-step puzzle: explain why $n^2 - 1$ is never prime when $n \geq 3$. (Factor $n^2 - 1$ as a product first.)

A trap to watch for

It is tempting to test whether $n$ is prime by checking divisibility for every integer up to $n - 1$ — but you only need to test up to $\lfloor \sqrt{n} \rfloor$. Reason: if $n = a \cdot b$ with $a \leq b$, then $a \leq \sqrt{n}$. So either you find a factor $\leq \sqrt{n}$, or there is none and $n$ is prime. A related trap: Euclid’s proof shows there are infinitely many primes, but it does not show that $p_1 p_2 \cdots p_k + 1$ is itself prime — only that some prime factor of it is new. Students sometimes mis-remember this as “the Euclid construction always produces a new prime,” which is false (try ${2, 3, 5, 7, 11, 13}$ above).

What you now know

You can decompose any integer into primes, justify the uniqueness of that decomposition via Euclid’s lemma, sieve out primes up to a given bound, and produce Euclid’s elegant contradiction proof that primes go on forever. Next section, modular arithmetic, recasts “same prime factorisation up to” ideas as algebra on equivalence classes.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §7.2.
• Hardy, G. H., Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press, ch. 1–2.
• Niven, I., Zuckerman, H. S., Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley, ch. 1–2.
• Rosen, K. H. (2010). Elementary Number Theory (6th ed.). Pearson, ch. 3.
• Koblitz, N. (1994). A Course in Number Theory and Cryptography (2nd ed.). Springer, ch. 1.