The Fundamental Theorem of Arithmetic

Why is $12 = 2 \times 2 \times 3$ the only way to write $12$ as a product of primes? Why not, say, $12 = 4 \times 3 = 2 \times 6$? The answer is that $4$ and $6$ themselves break apart into primes; once you push everything down to primes, the list is unique. This is the Fundamental Theorem of Arithmetic (FTA), and it is the bedrock of number theory.

Definitions

A natural number $p > 1$ is prime if its only positive divisors are $1$ and $p$. The first few primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$. A number $> 1$ that is not prime is called composite.

A prime factorisation of an integer $n \ge 2$ is an expression $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},$ where $p_1 < p_2 < \cdots < p_k$ are primes and the exponents $a_i$ are positive integers.

Theorem and idea of proof

Fundamental Theorem of Arithmetic. Every integer $n \ge 2$ can be written as a product of primes, and this factorisation is unique except for the order of the factors.

The statement has two parts: existence (there is some way to write $n$ as a product of primes) and uniqueness (there is only one such way once we sort the primes in increasing order).

Existence follows by repeated splitting. If $n$ is prime, we are done. Otherwise $n = a \cdot b$ with $1 < a, b < n$. Apply the same step to $a$ and $b$. The process must stop because at each stage the factors strictly decrease but remain $\ge 2$. The leaves of this "factor tree" are primes.

Uniqueness is the deeper half. Suppose $p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s,$ where all $p_i$ and $q_j$ are primes. The key lemma , sometimes called Euclid's lemma , says: if a prime $p$ divides a product $ab$, then $p \mid a$ or $p \mid b$. Applying this to $p_1 \mid q_1 q_2 \cdots q_s$, we conclude that $p_1$ equals one of the $q_j$. Cancel and continue. Both lists shrink at the same rate and turn out to be identical (after re-ordering).

The theorem has immediate consequences. Two integers can be compared by comparing their prime exponent vectors. The divisors of $n = p_1^{a_1} \cdots p_k^{a_k}$ are exactly the numbers $p_1^{b_1} \cdots p_k^{b_k}$ with $0 \le b_i \le a_i$, so the number of divisors is $(a_1+1)(a_2+1)\cdots(a_k+1)$. The square divisors of $n^2$, the structure of $n!$, and the irrationality of $\sqrt{p}$ all sit on this foundation.

Finally, FTA tells us that primes are the atoms of the multiplicative world. Just as in chemistry every molecule is built from atoms in one way, every positive integer is built from primes in one way. That is why so much of modern cryptography (RSA, for example) hides a secret inside a hard-to-factor product of two enormous primes.

Worked examples

Example 1. Find the prime factorisation of $156$.

Divide by the smallest primes in turn. $156 = 2 \times 78 = 2 \times 2 \times 39 = 2 \times 2 \times 3 \times 13 = 2^2 \times 3 \times 13.$

Example 2. Factorise $13125$ into primes.

$13125$ ends in $5$, so divide by $5$: $13125 = 5 \times 2625 = 5 \times 5 \times 525 = 5^3 \times 105 = 5^3 \times 3 \times 35 = 5^4 \times 3 \times 7$. Check: $5^4 = 625$, and $625 \times 21 = 13125$. So $13125 = 3 \times 5^4 \times 7$.

Example 3. Show that $7 \times 11 \times 13 + 13$ is a composite number.

Factor $13$ out: $7 \times 11 \times 13 + 13 = 13(7 \times 11 + 1) = 13 \times 78 = 13 \times 2 \times 3 \times 13 = 2 \times 3 \times 13^2$. Because the expression has more than one prime factor, it is composite.

Example 4. How many positive divisors does $360$ have?

First factorise: $360 = 2^3 \times 3^2 \times 5$. Number of divisors $= (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$.

Example 5. Can the number $6^n$ end in the digit $0$ for any natural number $n$?

If $6^n$ ended in $0$, then $10 \mid 6^n$, so $5 \mid 6^n$. By FTA the only prime factors of $6^n = 2^n \cdot 3^n$ are $2$ and $3$. Hence $5 \nmid 6^n$. So $6^n$ can never end in $0$.

Try it yourself

1. Express each as a product of primes: $96$, $234$, $429$, $3825$.
2. Without computing, decide whether $4^n$ can end in $0$ for some $n$.
3. How many divisors does $2^4 \times 3^3 \times 7$ have?
4. Find the prime factorisation of $7429$.
5. Is $1 + 2 + 3 + \ldots + 10$ prime or composite? Justify using FTA.
6. Show that $3 \times 5 \times 7 + 7$ is composite.
7. If $p$ is prime and $p^2 \mid n$, must $p \mid n$? Why?
8. List all positive divisors of $84$ using its prime factorisation.
9. Find the smallest natural number that has exactly $10$ positive divisors.
10. If $n = p^2 q$ (distinct primes), how many divisors does $n^2$ have?

Pitfalls / Insight

• $1$ is not a prime , it has only one divisor, not two. Many students wrongly include $1$ in factor lists.
• Order matters only as bookkeeping. $12 = 2^2 \times 3 = 3 \times 2 \times 2$; FTA cares only about which primes and how many of each.
• "Factorise" means push down to primes, not just split into any two factors. $30 = 5 \times 6$ is not a prime factorisation; $30 = 2 \times 3 \times 5$ is.

Insight. Think of an integer as a vector of exponents. $360 = (3,2,1,0,\ldots)$ in primes $(2,3,5,7,\ldots)$. Multiplication adds vectors, division subtracts them, and the gcd/lcm become coordinate-wise min/max. The whole chapter is just linear algebra on these exponent vectors.