This theorem is quite old, and of course Euclid has a nice proof of it, along with various lemmas he needs to get there. The key ingredients are:

• If a number is prime, that is the prime factorization.
• If a number is composite, then it is divisible by some prime. (Euclid used this in his proof of the infinitude of primes, above.)
• This process can be continued and is finite.
• Any other way in which you can write the same number as a product of primes is just a reordering of the one obtained in the previous step. (This step requires that if a prime \(p\) divides a product \(ab\), then \(p\) divides at least one of \(a\) or \(b\); Euclid proves it here, and it is very closely related to our earlier fact about coprimes dividing a product.)

Okay, now we need the details.

• Let's use induction. So our base case is \(N=2\), which is of course prime and has a unique factorization \(2^1\).
• Suppose we have proved that all numbers up to \(N\) can be written as a product of primes (unique or not). Then look at \(N+1\).
• If \(N+1\) is prime, that is its prime factorization, as with \(2\).
• If not, then by induction we know it is composite, so \(N+1=ab\), where \(1< a,b< N+1\). Note why this is! Recall the proof of the Sieve.
• So \(a\) and \(b\) have prime decompositions \(\prod p_i\) and \(\prod q_j\), since they are less than \(N+1\) but not 1, and so \(N+1=\prod p_i \prod q_j\).
• It remains to be shown that this is unique. So first rewrite it as \[N+1=\prod p_i^{e_i}\] and now suppose that (once again by induction) we have written all numbers up to \(N\) uniquely as a product of primes.
• Let's look at another such representation, \[N+1=\prod q_j^{f_j}\]
• At this point we need that if \(p|\prod_{k=1}^\ell a_k\), then \(p|a_k\) for at least one \(k\). If you are uncomfortable with induction, then you should try proving this for yourself.
• By definition, \(p_1\) divides \(N+1\). Hence (by the preceding step) \(p_1\) divides at least one of the \(q_j^{f_j}\), and hence (by the same step applied to \(q_j\cdot q_j\cdot q_j\cdots q_j\)) it divides \(q_j\).
• But the only positive divisors of a prime are itself and 1, so \(p_1=q_j\).
• Cancel these from the product to get two different representations of (the integer) \(\frac{N+1}{p_1}\) as a product of primes. By the induction hypothesis, these are unique up to reordering.
• Hence multiplying both by \(p_1\) to get \(N+1\) should also be unique up to reordering.
• By induction, we are done.

If you are familiar with other algebraic structures, I should note -- this theorem is not true for every algebraic system! Not even for every such system that is like the integers in other ways. Most interesting examples of this are just beyond the level of this course; for those who must know now, try finding prime factorizations of \(N=6\) in the ring \(\mathbb{Q}[\sqrt{-5}]\).

The FTA is so great, I cannot overstate its significance. For instance:

• Lots of theorems now have reasons, not just proofs. This is an important point about math! You will reprove a few things to see this. This boils down to the fact that \(\gcd(a,b)=1\) now means that \(a\) and \(b\) do not share any common prime factors.
• Slightly quick and dirty example to give the feel:

  If \(a|c\), \(b|c\), and \(\gcd(a,b)=1\), then \(a=\prod p_i\) and \(b=\prod q_j\) but none of the \(p_i\) can be any of the \(q_j\). Since \(c=\prod r_k^{e_k}\) where the \(r_k\) are distinct, the \(p_i\) must be some of the \(r_k\) and the \(q_j\) must be different ones, so that \(\prod p_i q_j\) still divides \(c\).

• Computing all kinds of things becomes easier. If we let \(a=\prod_{i=1}^n p_i^{e_i}\) and \(b=\prod_{i=1}^n p_i^{f_i}\), where it's possible that \(e_i\) or \(f_i\) is zero at times, then
  • \[ab=\prod_{i=1}^n p_i^{e_i+f_i}\]
  • \[\gcd(a,b)=\prod_{i=1}^n p_i^{\min(e_i,f_i)}\]
  • \[\text{lcm}(a,b)=\prod_{i=1}^n p_i^{???}\] (Recall the least common multiple from last time.)
  • \[a/b=\prod_{i=1}^n p_i^{???}\]
• It can help us do in a systematic way results that were probably first obtained by extremely ad-hoc methods. As an example, you probably first saw the proof that \(\sqrt{2}\) is irrational using only "evenness". But we can prove that \(\sqrt{m}\notin \mathbb{Q}\) (for \(m\) not a perfect square) in a very similar fashion.
• It gives us a canonical way to describe every integer in terms of simpler integers, and gives a measure of simplicity.

As an example, let's prove with it the facts I used for the proofs about Pythagorean triples last time:

• If \(a^2|z^2\), then \(a|z\).
• If \(gcd(m,n)=1\) and \(mn\) is a perfect square, then so are \(m\) and \(n\).

There are oodles more things this helps with. For instance, take this set of ideas from another good text.

• Suppose \(\gcd(a,p^2)=p\) and \(\gcd(b,p^2)=p^e\) for some positive integers \(a,b\) and \(e\geq 0\).
• What can we say about \(\gcd(a^2,p^2)\)?
• What can we say about \(\gcd(ab,p^{2+e})\)?
• What can we say about \(\gcd(a+b,p)\) or \(\gcd(a+b,p^2)\) or \(\cdots\) ?

Here are some ways to calculate these things in Sage.

Note that one of these functions gives just a list of the prime divisors, while the other gives the full factorization.

It's fun to redo some of these theorems with the FTA. For instance, it becomes apparent why \(\text{lcm}(a,b)\gcd(a,b)=ab\); for each prime \(p\) in the factorization of \(a\) and/or \(b\), the bigger power of \(p\) must be the power in the least common multiple (since you need a multiple), and the smaller power of \(p\) must be the power in the greatest common divisor (since you need it to divide both \(a\) and \(b\)). So for each \(p\), the statement turns into \[p^{e}p^{f}=p^{max(e,f)}p^{min(e,f)}\; ,\] which is obvious, and then we multiply for all \(p\).

One last thing that is useful is some additional notation.

As an example, \(5^2\parallel 75\). The prime factorization of a number clearly gives you information about this.

Since \(2^{18} \parallel 20!\) and \(5^4\parallel 20!\), we can conclude that \(20!\) ends with exactly 4 zeros merely from the prime factorization, which we could certainly get without multiplying it out (though in this case Sage does that first). We can check this: