\documentclass[hyperref={colorlinks=true}]{beamer}
\usepackage{amsmath,amsfonts,amsthm}
% Not in French
%\usepackage[latin1]{inputenc}
%\usepackage[OT2,T1]{fontenc}
%\usepackage[frenchb]{babel}

\usepackage{xypic}\xyoption{tips}
\usepackage{pgfplots}
\usepackage{url}
\usepackage{calrsfs}
%\usepackage{fourier}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Choose a theme:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usetheme{Berlin}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Marburg}
\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Choose a color theme:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usecolortheme{crane}
%\usecolortheme{dove}
%\usecolortheme{dolphin}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Choose a font theme:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usefonttheme{structurebold}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setbeamercovered{dynamic}

% Blackboard bold characters:
\renewcommand{\AA}{\mathbb{A}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

% Caligraphic characters:
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\renewcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\renewcommand{\cH}{\mathcal{H}}
\renewcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\renewcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cX}{\mathcal{X}}

\begin{document}

\title{Five proofs of the infinitude of primes}
\author{David Kohel\newline
Institut de Math{\'e}matiques de Marseille}
\date{Marseille \newline January 2020}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TITLEPAGE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}\titlepage\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TABLE OF CONTENTS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}\tableofcontents\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof 1: Euclid}
% Short title:
\section{\#1: Euclid}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{The infinitude of primes}

In this talk we give a selection of the most elegant proofs of the
infinitude of primes.  Precisely, we proof the following theorem.
\vspace{4mm}

\begin{theorem}
The set of primes in $\NN$ is infinite.
\end{theorem}
\vspace{4mm}

The earliest known proof is due to Euclid ({\it Elements}, ca.~300~B.C.).
\vspace{4mm}

We permit ourselves to use more modern notions in mathematics: arithmetic
of $\ZZ/n\ZZ$ and basic results from analysis and topology.
\end{frame}

\begin{frame}
\frametitle{Primes}
\begin{definition}
Let $\cP$ denote the set of primes in $\NN$.  For a real number $x \in \RR$,
we denote by $\cP_x$ the subset of primes bounded by $x$.  The cardinality
of this set is denoted by $$\pi(x) = |\cP_x| = |\{ p \in \cP \;:\; p \le x \}|.$$
Finally we denote $\cP(n) \subset \cP$ to be the set of prime divisors of~$n$.
\end{definition}

The infinitude of primes can be expressed equivalently by:
\begin{enumerate}
\item $\cP$ is not finite.
\item $\cP_x \ne \cP$ for any $x \in \RR$.
\item $\cP(n) \ne \cP$ for any $n \in \NN$.
\item The function $\pi: \RR \rightarrow \NN$ is not bounded.
\end{enumerate}
The earliest proofs assumed that $\cP$ was finite and derived a contradiction.
%Analytic approaches to the problem consider the growth of the function $\pi$.
\end{frame}

\begin{frame}
\frametitle{Euclid's proof}
\begin{proof}[Proof [Euclid{]}]
Suppose that $\cP$ is finite, set
$$
n = \prod_{p\in\cP} p,
$$
and let $q$ be a prime divisor of $n+1$.  By construction, $q$ is a
prime divisor of both $n$ and and $n+1$, hence of $\gcd(n,n+1) = 1$,
a contradiction.
\end{proof}
\vspace{2mm}

{\bf Remark.}
Expressed differently, this argument can be viewed as a construction
of a new prime $q$ outside of any finite subset $S \subseteq \cP$.
\vspace{2mm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof 2: Fermat numbers}
% Short title:
\section{\#2: Fermat numbers}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Proof by Fermat numbers}

The next proof constructs an infinite family of subsets $S_n \subseteq \cP$
which are nonempty and pairwise disjoint. In particular, if $(a_n)$ is a
sequence such that
$$
a_n > 1, \mbox{ and }
\gcd(a_m,a_n) = 1 \mbox{ for all } m \ne n,
$$
then $(S_n) = (\cP(a_n))$ is such a family.
The infinitude of $\cP$ follows.

\setbeamertemplate{qed symbol}{}
\begin{proof}[Proof [Fermat numbers{]}]
Let $(F_n) = (3,5,17,\dots)$ the sequence of Fermat numbers, defined by
$$
F_n = 2^{2^n} + 1.
$$
Clearly $F_n > 1$ for all $n$.  It remains to show that $\gcd(F_m,F_n) = 1$
(we say that $F_m$ and $F_n$ are coprime).
\end{proof}
\setbeamertemplate{qed symbol}{\qed}

\end{frame}

\begin{frame}
\frametitle{A recursion for Fermat numbers}

{\bf Interlude.} In order to show that Fermat numbers are coprime, we prove
the following recursion for Fermat numbers.
\begin{lemma}
For all $n > 1$ the following recursion
$
\displaystyle
\prod_{m=0}^{n-1} F_m = F_n - 2
$
holds.
\end{lemma}

\begin{proof}[Proof by induction]
For $n = 1$ the equality $F_0 = F_1 - 2 = 3$ is verified.  Assuming the recursion
holds for $n$, then
$$
\prod_{m=0}^{n} F_m = (F_n - 2)F_n = (2^{2^n}-1)(2^{2^n}+1) = 2^{2^{n+1}}-1 = F_{n+1}-2,
$$
and the recursion follows by induction.
\end{proof}

\end{frame}

\begin{frame}
\frametitle{Coprimality of Fermat numbers}
\begin{proof}[Proof by Fermat numbers continued]
Let $r = \gcd(F_m,F_n)$, for $m < n$. To complete the proof, we show
that $r = 1$. By the lemma, $F_m$ divides $F_n - 2$.
Thus $r = 1$ or $2$, and since $F_n$ is odd, $r = 1$.
\vspace{2mm}

To conclude, we recall that we have $F_n > 1$ for all $n \in \NN$,
which implies that the set $\cP(F_n)$ of prime divisors of $F_n$ is nonempty.

Moreover $\gcd(F_m,F_n) = 1$ implies that $\cP(F_m) \cap \cP(F_n) = \emptyset$,
and consequently
$$
\bigcup_{n=0}^\infty \cP(F_n)
$$
is an infinite subset of $\cP$.
\end{proof}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof 3: Mersenne numbers}
% Short title:
\section{\#3: Mersenne numbers}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Proof by Mersenne numbers}

\begin{proof}[Proof by Mersenne numbers]
Suppose that $\cP$ is finite and $p = \max(\cP)$. Let $2^p-1$ be the
$p$-th Mersenne number, and suppose that $q$ is a prime divisor.
\vspace{1mm}

Then $2^p \equiv 1 \bmod q$ and since $p$ is prime (and $2 \not\equiv 1
\bmod q$), the element $2$ has order $p$ in $\FF_q^*$ (by Lagrange).
\vspace{1mm}

In particular $p$ divdes $q-1$, and so $p < q$, a contradiction.
\end{proof}
\vspace{4mm}

{\bf Remark.}
The proof is constructive: for any given finite set of primes
$S \subset \cP$ one can construct a new prime outside of $S$.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof 4: An analytic lower bound}
% Short title:
\section{\#4: Analytic lower bound}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{An analytic lower bound}

\setbeamertemplate{qed symbol}{}
\begin{proof}[Proof by analysis]
We show that the function $\pi(x) = |\cP_x|$ is bounded below by $\log(x)$.
We observe that
$$
\log(x) = \int_1^x \frac{1}{t} dt \le 1 + \frac{1}{2} + \cdots \frac{1}{n},
$$
for all $n \le x < n+1$. If $S(x)$ is the set of positive integers whose
prime divisors are in $\cP_x$, then
$$
\log(x) \le \sum_{m \in S(x)} \frac{1}{m}
  = \prod_{p\in\cP_x} \left(\sum_{i=0}^\infty \frac{1}{p^i}\right)\cdot
$$
\end{proof}
\setbeamertemplate{qed symbol}{\qed}

\end{frame}

\begin{frame}
\frametitle{An analytic lower bound continued}

\begin{proof}[Proof continued]
This gives the inequality
$$
\log(x) \le \prod_{p\in\cP_x} \left(\sum_{i=0}^\infty \frac{1}{p^i}\right)
= \prod_{p\in\cP_x} \frac{1}{1-1/p} = \prod_{p\in\cP_x} \frac{p}{p-1}\cdot
$$
If we denote $\cP_x = \{p_1,p_2,\dots,p_{\pi(x)}\}$ such that $p_k < p_{k+1}$,
and observe that $p_k \ge k+1$, then
$$
\log(x) \le \prod_{k=1}^{\pi(x)} \frac{p_k}{p_k-1} \le \prod_{k=1}^{\pi(x)} \frac{k+1}{k} = \pi(x) + 1.
$$
Thus $\log(x) - 1 \le \pi(x)$. Since $\log(x)$ is unbounded so is $\pi(x)$.
\end{proof}
{\bf Remark.} This proof is remarkable for giving not only a proof of
infinitude, but also an explicit lower bound on $\pi(x)$.
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof 5: Furstenberg's topological proof}
% Short title:
\section{\#5: Furstenberg's topological proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Fursternberg's exotic topology}

Furstenberg's proof uses an exotic topology on $\ZZ$ in order to give
an elegant but nonconstructive proof of the infinitude of primes.
The idea is to declare the arithmetic sequences
$$
S(a,b) = a + b\ZZ = \{ a + bn \;:\; n \in \ZZ \},
$$
to be open.  The topology generated by the basis
$$
\cB = \{ S(a,b) \;:\; a, b \in \ZZ \},
$$
is called the {\it evenly spaced topology} on $\ZZ$.
\vspace{2mm}

We remark that $U \subset \ZZ$ is an open in this topology if and only
for each $x \in U$, there exists $b \in \ZZ$ such that $S(x,b) \subseteq U$.
\end{frame}

\begin{frame}
\frametitle{Fursternberg's topological proof}

The evenly spaced topology of Furstenberg satisfies the following propoerties.
\begin{enumerate}
\item
If $U$ is open then either $U = \emptyset$ or $U$ is not finite.
\item
The sets $S(a,b)$ are both open and closed, since $\ZZ$ is the
disjoint union: $\ZZ = S(0,b) \cup S(1,b) \cup \cdots \cup S(b-1,b)$.
\item
$\ZZ\backslash\{\pm1\} = \displaystyle \bigcup_{p\in\cP}S(0,p)$.
\end{enumerate}

These properties give the following simple proof.

\begin{proof}[Furstenberg's proof]
If $\cP$ were finite, then $\ZZ\backslash\{\pm1\}$ would be closed
by~\textbf{2}, hence $\{\pm1\}$ would be open, contradicting~\textbf{1}.
\end{proof}

\end{frame}

\end{document}

\begin{frame}
\frametitle{}
\end{frame}

