Full Proof of Fundamental Theorem of Arithmetic

Statement

The Fundamental Theorem of Arithmetic says that any positive integer greater than $1$ can be written as a product of finitely many primes uniquely up to their order. The term "up to thier order" means that we consider $12 = 2^2 \cdot 3$ to be equivalent as $12 = 3 \cdot 2^2$. Note that a product can consist of just one prime. We must exclude $1$ because it has only one divisor ($1$), but we do not consider it a prime, as otherwise it would contradict uniqueness. For example, if $1$ were prime, then $5 = 5$ and $5 = 1 \cdot 5$ would be a contradiction to the uniqueness. For more advanced readers, $1$ is a unit in the ring of integers, and in a ring, the FTA says that the product is unique up to a unit and order of primes.

Proof

For this proof, we will assume that the reader already knows the following two facts:

• Every integer greater than $1$ has at least one prime divisor. This implies that every integer greater than $1$ is either prime or composite. (Used to show existence)

• (Euclid's Lemma) If a prime $p | ab$ for integers $a, b$, then $p | a$ or $p | b$. (Used to show uniqueness)

If either of these seem unfamiliar, take a moment now to think about why they are true. They can also be found in previous lessons.

There are two parts we need to prove:

• The existence of such a product of primes

• The product of primes is unique up to their order

Existence

To prove existence, we will use strong induction. Since $2$ is already a prime itself, that covers the base case. Now assume that all integers $1 < n < k$ can be written as a product of primes. We will show that $k$ can be written as a product of primes. If $k$ itself is prime, then we are done as it is the product of $1$ prime. Otherwise, let $k = ab$ for integers $1 < a, b < k$. By the inductive hypothesis, $a$ and $b$ can be written as the product of primes, so the product $ab = k$ can also be written as a product of primes. Hence, by induction, all integers greater than $1$ can be written as a product of one or more primes.

Uniqueness

To prove uniqueness, suppose, that a number $n$ can be expressed as a product of primes in two ways: $n = p_1p_2\cdots p_k = q_1 q_2 \cdots q_l$. Here, we leave out exponents since we will explicitly write out repeated primes (for example, it is possible to have $p_1 = p_2 = 2$). We wish to show that these two representations are the same up to their order. Since these two products are equal, any factor of one product must divide the other product. That is, for any $1 \le i \le k$, $p_i | q_1 q_2 \cdots q_l$. By Euclid's Lemma, there exists $1 \le j \le l$ such that $p_i | q_j$. Since $p_i$ and $q_j$ are primes, it follows that $p_i = q_j$. We may divide out the common prime factor in the two products, and repeat with the remaining factors, until all common prime factors have been divided out.

If $k \ne l$, then we will be left with either $p_{i_1} p_{i_2} \cdots p_{i_r} = 1$ (if $k > l$), or $q_{l_1} q_{l_2} \cdots q_{l_s} = 1$ (if $k < l$). Since all primes are integers greater than $1$, both scenarios are impossible. Therefore, $k = l$, so the two products have the same number of (not necessarily distinct) primes. But from our above argument, we know that these two representations are the same up to their order. Therefore, any two representations of an integer $n$ as a product of prime factors must be equivalent up to thier order.

The Fundamental Theorem of Arithmetic formalizes the concept of prime factorization. We call the representation of an integer as a product of primes $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ the canonical representation of $n$.

Concrete Example: consider the number $72$. We can find its factorization (which we now know is unique) by trying to factor out the smallest prime numbers possible. The smallest prime number is $2$. Since $72$ is even, there is at least one power of $2$ in the prime factorization, so we promptly pull it out:

$$72 = 2 \cdot 36$$

It turns out we can factor out a $2$ twice more:

$$72 = 2 \cdot 2^2 \cdot 9 = 2^3 \cdot 9$$

Finally, $9$ has the prime factorization $3^2$.

$$72 = 2^3 \cdot 3^2$$

We have broken up $72$ into prime factors and their powers, so we're done. By the commutative property of multiplication, we can rearrange these factors in any order, like so

$$2 \cdot 3 \cdot 3 \cdot 2 \cdot 2$$ $$3 \cdot 3 \cdot 2 \cdot 2 \cdot 2$$ $$2 \cdot 3 \cdot 2 \cdot 3 \cdot 2$$

and so on. But they are all the same! In other words, rearranging the factors doesn't cause a problem with uniqueness.

Proof of uniqueness of prime factorization, without Euclid's lemma

Check out Kevin Buzzard's notes: An inductive proof of fundamental theorem of arithmetic.

As usual the main difficulty is uniqueness; we assume existence throughout.

So, to prove uniqueness, go by induction: suppose $$n = p_1\dots p_r = q_1\dots q_s$$ for some $n>1$, where the statement has been proven for $m=1,\dots,n-1$.

In particular, if $m\in [1,n-1]$ is divisible by a prime $p$, then $p$ appears in the (unique!) prime factorization of $m$. Call this fact (+).

Key idea

Instead of directly using Euclid's lemma to prove that one of the $q_j$'s is divisible by $p_1$ (hence equal to $p_1$), we take an indirect route to the same end. We will assume $p_1$ is the smallest prime among the $p_i,q_j$ and then reduce some $q_j$'s modulo $p_1$ (which doesn't affect divisibility by $p_1$).

Details

If $q_1 = p_1$, we're done by the inductive hypothesis for $n/p_1$.

Else, by the minimality assumption on $p_1$, we have $p_1 < q_1$. Then $$m = (q_1-p_1)q_2\dots q_s$$ is congruent to $$q_1q_2\dots q_s = n \equiv 0\pmod{p_1}.$$

Now, by (+), $p_1$ appears in the (unique!) prime factorization of $m$. Upon choosing a prime factorization of $q_1-p_1$ (by existence), we conclude that either $q_1-p_1$ is divisible by $p_1$ (in which case $p_1\mid q_1$, so $q_1 = p_1$), or one of $q_2,\dots,q_s$ is divisible by (hence equal to) $p_1$. As in the $q_1 = p_1$ case, we're now done by the inductive hypothesis for $n/p_1$.

Reflection

We didn't need to choose $p_1$ to be absolutely minimal among the $p_i,q_j$; assuming $p_1 \leq q_1$ would still have worked. Also, in the second (interesting) case $p_1 < q_1$ above, it is actually impossible for $q_1-p_1$ to be divisible by $p_1$, or else $q_1$ would have to be a multiple of $p_1$, which would be inconsistent with the primality of $q_1$.

Generality

The proof, with a slight modification, generalizes to Euclidean domains. The key technical input was to be able to reduce any integer (in our case, $q_1$) modulo $p_1$ to get a smaller remainder.

Exercise

What goes wrong if you try to prove Euclid's lemma directly by induction (assuming only existence in FTA)? The main desired statement is now that if $$n = p_1\dots p_r = AB,$$ then either $p_1\mid A$ or $p_1\mid B$.