2.3: The Fundamental Theorem of Arithmetic
- Page ID
- 60302
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The last corollary of the previous section enables us to prove the most important result of this chapter. But first, we introduce units and extend the definition of primes to \(\mathbb{Z}\).
Definition 2.13
Units in \(\mathbb{Z}\) are \(-1\) and \(1\). All other numbers are non-units. A number \(n \ne 0\) in \(\mathbb{Z}\) is called composite if it can written as a product of two non-units. If \(n\) is not \(0\), not a unit and not composite, it is a prime.
Theorem 2.14 (The Fundamental Theorem of Arithmetic)
Every nonzero integer \(n \in \mathbb{Z}\)
- is a product of powers of primes (up to a unit) and
- that product is unique (up to the order of multiplication and up to multiplication by the units \(\pm 1\).
Remark: The theorem is also called the unique factorication theorem. Its statement means that up to re-ordering of the \(p_{i}\), every integer \(n\) can be uniquely expressed as
\[ n = \pm 1 \prod_{i=1}^{r} p_{i}^{l_{i}} \nonumber\]
where the \(p_{i}\) are distinct primes.
- Proof
-
Statement (1): Define \(S\) to be the set of integers \(n\) that are not products of primes times a unit, and the set \(ν(S)\) their norms. If the set \(S\) is non-empty, then then by the well-ordering principle (Theorem 1.7), \(ν(S)\) has a smallest element. Let \(a\) be one of the elements in \(S\) that minimize \(ν(S)\). By possibly multiplying by \(-1\), we may assume that \(a\) is positive.
If \(a\) is prime, then it can be factored into primes, namely \(a = a\), and the theorem would hold in this case. Thus \(a\) is a composite number, \(a = bc\) and both \(b\) and \(c\) are non-units. Thus \(N(b)\) and \(N(c)\) are strictly smaller than \(N(a)\). If \(b\) and \(c\) are products of primes, then, of course, so is \(a = bc\). Therefore at least one of \(a\) or \(b\) is not. But this contradicts the assumptions on \(a\).
Statement (2): Let \(S\) be the set of integers that have more than one factorization and \(ν(S)\) the set of their norms. If the set \(S\) is non-empty, then by the well-ordering principle (Theorem 1.7), \(ν(S)\) has a smallest element. Let \(a\) be one of the elements in \(S\) that minimize \(ν(S)\).
Thus we have
\[a = u \prod_{i=1}^{r} p_{i} = u' \prod_{i=1}^{r} p'_{i} \nonumber\]
where at least some of the \(p_{i}\) and \(p'_{i}\) do not match up. Here, \(u\) and \(u'\) are units. Clearly, \(p_{1}\) divides \(a\). By Corollary 2.12, \(p_{1}\) equals one of the \(p'_{i}\), say, \(p'_{1}\). Since primes are not units, \(N(\frac{a}{p_{1}})\) is strictly less than \(N(a)\). Therefore, by hypothesis, \(\frac{a}{p_{1}}\) is uniquely factorizable. But then then, the primes in
\[\frac{a}{p_{1}} = u \prod_{i=2}^{r} p_{i} = u' \prod_{i=2}^{r} p'_{i} \nonumber\]
all match up (up to units).