Section 6.3 The Fundamental Theorem of Arithmetic
Subsection 6.3.1 Preliminaries and statement
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.
Definition 6.3.1.
A factorization of an integer is a way of writing it as a product of integers. This nearly always refers to one of two things, which are mentioned explicitly if there is danger of ambiguity:
Theorem 6.3.2. Fundamental Theorem of Arithmetic.
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_j
\end{equation*}
then \(m=n\) and a reordering of the \(q_j\) will make them the same as the \(p_i\text{.}\)
Proof.
Example 6.3.3.
For instance:
Clearly (from normal experience) the only possible factorizations than these would just put the primes in a different order. Why doesn’t this work for
\(N=1\text{?}\) (See
Exercise 6.6.24.) As it happens, Euclid did not even consider one to be a number in the same sense as the others; see
Joyce’s commentary 16 .
Example 6.3.4.
Usually we will implicitly assume the primes are in nondecreasing order, and write \(3^2\) instead of \(3\cdot 3\) (with the primes now necessarily in increasing order), so the following notation is common to express a prime power factorization:
\begin{equation*}
N=\prod_{i=1}^n p_i^{e_i}\text{.}
\end{equation*}
Sometimes when the context is clear, one can even write \(N = \prod p\) or \(N = \prod p^e\text{.}\)
Using the same numbers as in the previous example:
Example 6.3.5.
Just to get this down, practice writing the following as a product of such prime powers.
Subsection 6.3.2 Proof of the FTA
This theorem is quite old, and of course Euclid has a
nice proof of it 17 , along with various lemmata (the
plural of lemma 18 , though I’ll also use “lemmas” in this text) that 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 by definition divisible by some smaller positive number other than one. (Euclid used the stronger fact that it is divisible by a
prime in his proof of
Infinitude of Primes.)
This process can be continued, but only finitely often.
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.
Lemma 6.3.6.
If a prime \(p\) divides a product \(ab\text{,}\) then \(p\) divides at least one of \(a\) or \(b\text{.}\)
Proof.
Corollary 6.3.7.
If a prime \(p\) divides a finite product of numbers, then \(p\) divides at least one of them, i.e.
\begin{equation*}
p\;\Bigg\vert\; \prod_{k=1}^\ell a_k\text{ implies }p\mid a_k\text{ for at least one }k
\end{equation*}
Proof.
Okay, now we need the details.
Proof of Theorem 6.3.2.
Let’s use induction on the size of \(N\text{.}\) So our base case is \(N=2\text{,}\) which is of course prime so it has (the) unique factorization \(2^1\text{.}\)
For the induction step, first 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.
By induction, this shows that a prime factorization exists for all numbers up to \(N+1\text{.}\) It remains to be shown that such a factorization is unique.
So first rewrite our factorization in a given order (such as nondecreasing):
\begin{equation*}
N+1=\prod p_i,\; p_i\leq p_{i+1}\text{.}
\end{equation*}
Now let’s look at another possible representation, possibly with different primes:
\begin{equation*}
N+1=\prod q_j\text{.}
\end{equation*}
At this point we need
Corollary 6.3.7. By assumption,
\(p_1\) divides
\(N+1\text{.}\) Hence, by the corollary,
\(p_1\) divides at least one of the
\(q_j\text{.}\) But the only positive divisors of a prime are itself and 1, and
\(p_1\) is prime (not one), so
\(p_1=q_j\text{.}\)
Cancel these from both products to get two different representations of (the integer) \(\frac{N+1}{p_1}\) as a product of primes. By the induction hypothesis, since this number is less than \(N+1\text{,}\) these representations are unique up to reordering, so multiplying both by \(p_1\) to get \(N+1\) must also be unique up to reordering.
By induction, we are done.
Two comments about this proof are in order. First, some students may wonder about this induction proof, because in the induction hypothesis we do not simply assume a single
\(N\) has a (unique) factorization (as in
Example 1.2.4), but that all
\(n\leq N\) do. But this is just an artifact
20 of the statement we are proving. The logical induction statement is not that “
\(N\) has a factorization”, but that “all numbers less than
\(N\) have a factorization”.
Second, if you are familiar with other algebraic structures, it is very important to note that other algebraic systems may
not have unique factorization into primes, or even have a notion of prime elements! Even some structures very similar to the integers fail this; many 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.30.
mathcs.clarku.edu/~djoyce/java/elements/bookVII/defVII1.html
aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX14.html
www.duden.de/rechtschreibung/Lemma
aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII30.html
In my view, there is no pedagogical need for a separate notion of ‘strong induction’.