Our biggest goal for this chapter, and the motive for introducing primes at this point, is the Fundamental Theorem of Arithmetic, or FTA. It should probably be called the Fundamental Theorem of Number Theory, but in older usage one said “arithmetic”, and the name has stuck.
A factorization of an integer is a way of writing it as a product of other integers. This nearly always refers to one of two things, which are mentioned explicitly if there is danger of ambiguity:
A product into prime numbers, which can be called a prime factorization;
A product into positive powers of primes, which can be called a prime power factorization.
The following are true:
Every \(n\gt 1\) has a prime factorization.
Every such factorization of a given \(n\) is the same if you put the prime factors in increasing order (uniqueness).
More formally, we can say the following. Any positive integer \(N\gt 1\) may be written as a product \begin{equation*}N=\prod_{i=1}^n p_i\end{equation*} of primes, and further, if we can write a different such product \begin{equation*}N=\prod_{j=1}^m q_m\end{equation*} then \(m=n\) and a reordering of the \(q_j\) will make them the same as the \(p_i\).
For instance:
\(30=2\cdot 3\cdot 5\)
\(24=2\cdot 3\cdot 2\cdot 2=2\cdot 2\cdot 2\cdot 3\)
Clearly (from normal experience, I mean) the only other possibilities are putting the primes in a different order. Why doesn't this work for \(N=1\)?
Usually we will implicitly assume the primes are in nondecreasing order, and write \(3^2\) instead of \(3\cdot 3\), so be ready for the notation \begin{equation*}N=\prod_{i=1}^n p_i^{e_i}\end{equation*} for this same result; we only use the first notation for convenience for the first statement. (Sometimes when the context is clear, one can even write \(N = \prod p\) or \(N = \prod p^e\).)
For instance:
\(30=2^1\cdot 3^1\cdot 5^1\)
\(24=2^3\cdot 3^1\)
Just to get this down, practice writing the following as a product of such prime powers.
\(N=12100\)
\(N=1250\)
\(N=3072\)
This theorem is quite old, and of course Euclid has a nice proof of it, along with various lemmata (the plural of lemma, though I'll also use “lemmas” in this text) 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.
The last step requires this lemma, which is Euclid's Book 7, Proposition 30.
If a prime \(p\) divides a product \(ab\), then \(p\) divides at least one of \(a\) or \(b\).
If a prime \(p\) divides any finite product of primes, then \(p\) divides at least one of them, i.e. \begin{equation*}p\mid \prod_{k=1}^\ell a_k\text{ implies }p\mid a_k\text{ for at least one }k\end{equation*}
Okay, now we need the details.
Let's use induction on the size of \(N\). So our base case is \(N=2\), which is of course prime and has a unique factorization \(2^1\).
First, let's suppose we have proved that all numbers up to \(N\) can be written as a product of primes (uniquely or not). Then we look at \(N+1\) to continue the induction.
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\lt a,b\lt N+1\). (Note why \(a,b\) are smaller! Recall the proof of the Sieve 6.2.2.) In this case, \(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\).
By induction, this shows that a prime factorization exists.
It remains to be shown that such a factorization is unique. So first rewrite it as \begin{equation*}N+1=\prod p_i\end{equation*} and now suppose that (once again by induction) we have written all numbers up to \(N\) uniquely as a product of primes. So let's look at another such representation, \begin{equation*}N+1=\prod q_j\end{equation*}
At this point we need Corollary 6.3.6. By definition, \(p_1\) divides \(N+1\). Hence \(p_1\) divides at least one of the \(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, so multiplying both by \(p_1\) to get \(N+1\) should also be unique up to reordering.
By induction, we are done.
Two comments about this proof are in order. First (this is especially to the instructor), this may seem like a different kind of induction proof, because we do not simply assume \(N\) has a (unique) factorization, but that all \(n\leq N\) do. It is not; the statement we are proving is just different. Rather than proving “\(N\) has a factorization” we are proving “all numbers less than \(N\) have a factorization”. In particular, there is no pedagogical need for a separate notion of ‘strong induction’, in my view.
Second, if you are familiar with other algebraic structures, it is very important to 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 what this means now, try Exercise 6.6.25.
