Skip to main content
Mathematics LibreTexts

1.3: Primes and Factorization

  1. Last updated
  2. Save as PDF
  • Page ID
    82459

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Learning Objectives

    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: Prime

    Let \(p > 1\) be a natural number. We say \(p\) is prime if whenever \(a,b\in \mathbb{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: Prime is often more useful than the usual definition. And, as Lemma 1.3.1 demonstrates, the two notions are equivalent.

    Lemma 1.3.1 : Euclid's Lemma

    Given any \(p\in \mathbb{N}\text{,}\) \(p > 1\text{,}\) \(p\) is prime if and only if whenever \(m\in \mathbb{N}\) divides \(p\text{,}\) either \(m = p\) or \(m = 1\text{.}\)

    Exploration 1.3.1

    Using Lemma 1.3.1 as a guide, give a biconditional characterization for composite numbers. That is, finish the sentence: “A number \(m\in\mathbb{N}\) is composite if and only if ....”

    Remark 1.3.1

    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: Unit and the following; consequently, the opposite of "prime" is not "composite", but "not prime".

    Theorem 1.3.1

    Let \(a\in \mathbb{N}\) such that \(a > 1\text{.}\) Then there is a prime \(p\) such that \(p\mid a\text{.}\)

    Theorem 1.3.2

    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 Arithemetic

    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.

    The proof is broken into two parts: existence (Theorem 1.3.3 ) and uniqueness (Theorem 1.3.4 ).

    Theorem 1.3.3 : 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

    Induction!

    Theorem 1.3.4 : Fundamental Theorem of Arithmetic–Uniqueness Part

    Let \(n\) be a natural number. Let \(\{p_1,p_2,\ldots,p_m\}\) and \(\{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 \(\{r_1,r_2,\ldots,r_m\}\) and \(\{t_1,t_2,\ldots,t_s\}\) be sets of natural numbers such that

    \begin{align*} n &= p_1^{r_1} p_2^{r_2} \cdots p_m^{r_m}\\ &= q_1^{t_1} q_2^{t_2} \cdots q_s^{t_s}\text{.} \end{align*}

    Then \(m = s\) and \(\{p_1,p_2,\ldots,p_m\} = \{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 \(\mathbb{Z}\) and similar objects.

    References

    [1] D. Marshall, E. Odell, M. Starbird, Number Theory Through Inquiry, MAA Textbooks, Mathematical Association of America, 2007

    This page titled 1.3: Primes and Factorization is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Michael Janssen & Melissa Lindsey via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.