Skip to main content \(\newcommand{\longdivision}[2]{#1\big)\!\!\overline{\;#2}}
\newcommand{\mlongdivision}[2]{\longdivision{#1}{#2}}
\renewcommand{\emptyset}{\{\}}
\newcommand{\blanksp}{\underline{\hspace{.25in}}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\cspace}{-}
\newcommand{\Ta}{\mathtt{a}}
\newcommand{\Tb}{\mathtt{b}}
\newcommand{\Tc}{\mathtt{c}}
\newcommand{\Td}{\mathtt{d}}
\newcommand{\Te}{\mathtt{e}}
\newcommand{\Tf}{\mathtt{f}}
\newcommand{\Tg}{\mathtt{g}}
\newcommand{\Th}{\mathtt{h}}
\newcommand{\Ti}{\mathtt{i}}
\newcommand{\Tj}{\mathtt{j}}
\newcommand{\Tk}{\mathtt{k}}
\newcommand{\Tl}{\mathtt{l}}
\newcommand{\Tm}{\mathtt{m}}
\newcommand{\Tn}{\mathtt{n}}
\newcommand{\To}{\mathtt{o}}
\newcommand{\Tp}{\mathtt{p}}
\newcommand{\Tq}{\mathtt{q}}
\newcommand{\Tr}{\mathtt{r}}
\newcommand{\Ts}{\mathtt{s}}
\newcommand{\Tt}{\mathtt{t}}
\newcommand{\Tu}{\mathtt{u}}
\newcommand{\Tv}{\mathtt{v}}
\newcommand{\Tw}{\mathtt{w}}
\newcommand{\Tx}{\mathtt{x}}
\newcommand{\Ty}{\mathtt{y}}
\newcommand{\Tz}{\mathtt{z}}
\newcommand{\So}{\Tf}
\newcommand{\Sno}{\Tg}
\newcommand{\Si}{\Th}
\newcommand{\Sni}{\Tj}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\ZZ}{\Z}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\RR}{\R}
\newcommand{\F}{\mathbb{F}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\abs}[1]{|#1|}
\newcommand{\fmod}{\bmod}
\newcommand{\fdiv}{\,\mathrm{div}\,}
\newcommand{\lcm}{\mathrm{lcm}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\nr}[1]{\##1}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\newcommand{\sol}[1]{{\color{blue}\textit{#1}}}
\newcommand{\gro}[1]{{\color{gray}#1}}
\newcommand{\todo}[1]{{\color{purple}TO DO: #1}}
\newcommand{\fixme}[1]{{\color{red}FIX ME: #1}}
\newcommand{\checkme}[1]{{\color{green}CHECK ME: #1}}
\newcommand{\degre}{^\circ}
\newcommand{\vect}[1]{\overrightarrow{#1}}
\newcommand{\nix}{}
\newcommand{\cox}[1]{\fcolorbox[HTML]{000000}{#1}{\phantom{M}}}
\newcommand{\tox}[1]{\texttt{\##1} \amp \cox{#1}}
\newcommand{\ttx}[1]{\texttt{\##1}}
\newcommand{\mox}[1]{\mathtt{\##1}}
\newcommand{\xx}{\mathtt{\#}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 10.4 Infinitude of Primes
It is natural to ask the question
How many primes are there ?
In
Figure 10.6 we give a list of primes that comes in handy for many considerations of primes. Use it to count how many primes there are between certain numbers. You will see that as the numbers become larger there are fewer primes.
In
Theorem 9.17 we saw that there are infinitely many natural numbers. Certainly, not every natural number is prime because there are composites, too. However, an ancient number theory result
[5] asserts that there are still infinitely many primes.
Theorem 10.17 . Euclid’s Theorem.
There are infinitely many primes.
Proof. Let
\(\PP\) denote the set of all prime numbers. We show that for any finite subset
\(Q\) of
\(\PP\) there is an element in
\(\PP\) that is not an element of the finite subset
\(Q\text{.}\)
Let
\(Q\) be a finite subset of the set
\(\PP\text{.}\) Denote the elements of
\(Q\) by
\(p_1, p_2, \dots,p_n\) and let
\(q = p_1 \cdot p_2\cdot \ldots \cdot p_n\text{.}\)
By
Theorem 4.18 \(q\) and
\(q+1\) are coprime. So there is at least one prime number that divides
\(q+1\) but does not divide
\(q\text{.}\) Call that prime number
\(t\text{.}\) Then
\(t \not\in Q\text{.}\)
As we can find such a prime number
\(t\) for every finite subset of
\(\PP\text{,}\) the set
\(\PP\) is infinite by
Theorem 9.16 .
In the video in
Figure 10.18 we go through our proof of the infinitude of primes which is also called Euclid’s theorem.
Figure 10.18. Infinitude of Primes by Matt Farmer and Stephen Steward. There are many proofs for
Theorem 10.17 . For example a new prove was given by UNCG Professor Filip Saidak
[4] in 2006.
