Section 1.3 Primes and Factorization
Guiding Questions.
In this section, we’ll seek to answer the questions:
What are primes? What properties do they have?
What does the Fundamental Theorem of Arithmetic say?
Why is the Fundamental Theorem of Arithmetic true?
As described in the
Introduction, our main goal is to build a deep structural understanding of the notion of
factorization. That is, splitting objects (e.g., numbers, polynomials, matrices) into products of other objects. One of the most familiar examples of this process involves factoring integers into products of primes.
Definition 1.3.1.
Let \(p > 1\) be a natural number. We say \(p\) is prime if whenever \(a,b\in \Z\) such that \(p\mid ab\text{,}\) either \(p\mid a\) or \(p\mid b\text{.}\)
A natural number \(m > 1\) is said to be composite if it is not prime.
This is almost certainly not the definition of prime that you are familiar with from your school days, which likely said something to the effect that a prime
\(p > 1\) is a natural number only divisible by 1 and itself. However,
Definition 1.3.1 is often more useful than the usual definition. And, as
Lemma 1.3.2 demonstrates, the two notions are equivalent.
Lemma 1.3.2. Euclid’s Lemma.
Given any \(p\in \N\text{,}\) \(p > 1\text{,}\) \(p\) is prime if and only if whenever \(m\in \N\) divides \(p\text{,}\) either \(m = p\) or \(m = 1\text{.}\)
Exploration 1.3.1.
Using
Lemma 1.3.2 as a guide, give a biconditional characterization for composite numbers. That is, finish the sentence: “A number
\(m\in\N\) is composite if and only if ....”
Remark 1.3.3.
How does your definition treat the number 1? The primality of 1 has been the subject of much debate stretching back to the Greeks (most of whom did not consider 1 to be a number). Throughout history, mathematicians have at times viewed 1 as prime, and at other times, not prime. The main argument for the non-primality of 1 is that if 1 were taken to be prime, we would need to word theorems like the Fundamental Theorem of Arithmetic (below) in such a way that only prime factorizations not including 1 can be considered. For, if 1 is prime, we would have to consider, e.g., \(6 = 2\cdot 3 = 1\cdot 2 \cdot 3 = 1\cdot 1\cdot 2\cdot 3\) as three different factorizations of 6 into primes.
However, neither is 1 composite (your definition should rule this out in some way). Instead, we call 1 a
unit, which we’ll explore more fully in
Definition 2.2.7 and the following; consequently, the opposite of "prime" is not "composite", but "not prime".
Theorem 1.3.4.
Let \(a\in \N\) such that \(a > 1\text{.}\) Then there is a prime \(p\) such that \(p\mid a\text{.}\)
Theorem 1.3.5.
Suppose \(p\) and \(q\) are primes with \(p|q\text{.}\) Then \(p = q\text{.}\)
Our first major theorem makes two claims: that positive integers greater than 1 can be factored into products of primes, and that this factorization can happen in only one way. As the semester progresses, we will see other theorems like this one, and catch glimpses of other ways to think about the unique factorization property.
Fundamental Theorem of Arithmetic.
Every natural number greater than 1 is either a prime number or it can be expressed as a finite product of prime numbers where the expression is unique up to the order of the factors.
Theorem 1.3.6. Fundamental Theorem of Arithmetic–Existence Part.
Every natural number \(n > 1\) is either a prime number or it can be expressed as a finite product of prime numbers. That is, for every natural number \(n > 1\text{,}\) there exist primes \(p_1, p_2, \ldots,
p_m\) and natural numbers \(r_1, r_2, \ldots, r_m\) such that
\begin{equation*}
n = p_1^{r_1} p_2^{r_2} \cdots p_m^{r_m}\text{.}
\end{equation*}
Hint.
Lemma 1.3.7.
Let \(p\) and \(q_1, q_2,\ldots,
q_n\) all be primes and let \(k\) be a natural number such that \(pk = q_1 q_2 \ldots q_n\text{.}\) Then \(p = q_i\) for some \(i\text{.}\)
Theorem 1.3.8. Fundamental Theorem of Arithmetic–Uniqueness Part.
Let \(n\) be a natural number. Let \(\set{p_1,p_2,\ldots,p_m}\) and \(\set{q_1,q_2,\ldots,q_s}\) be sets of primes with \(p_i\ne p_j\) if \(i\ne j\) and \(q_i\ne q_j\) if \(i\ne j\text{.}\) Let \(\set{r_1,r_2,\ldots,r_m}\) and \(\set{t_1,t_2,\ldots,t_s}\) be sets of natural numbers such that
\begin{align*}
n \amp = p_1^{r_1} p_2^{r_2} \cdots p_m^{r_m}\\
\amp = q_1^{t_1} q_2^{t_2} \cdots q_s^{t_s}\text{.}
\end{align*}
Then \(m = s\) and \(\set{p_1,p_2,\ldots,p_m} = \set{q_1,q_2,\ldots,q_s}\text{.}\) That is, the sets of primes are equal but their elements are not necessarily listed in the same order (i.e., \(p_i\) may or may not equal \(q_i\)). Moreover, if \(p_i = q_j\text{,}\) then \(r_i = t_j\text{.}\) In other words, if we express the same natural number as a product of distinct primes, then the expressions are identical except for the ordering of the factors.
Hint.
Argue that the two sets are equal (how do we do that?). Then argue that the exponents must also be equal.
Our first major result is in hand: we can factor natural numbers \(n > 2\) uniquely as a product of primes. Much of the rest of this book seeks to deduce a generalization of this result that relies on structural arithmetic properties enjoyed by \(\Z\) and similar objects.
References References
[1]
D. Marshall, E. Odell, M. Starbird, Number Theory Through Inquiry, MAA Textbooks, Mathematical Association of America, 2007
