\documentclass[envcountsect]{beamer}
%\includegraphics[height=6cm](full frame)
\usepackage{times}
%\usetheme{JuanLesPins}
\usetheme{Darmstadt}
%Frankfurt}
\logo{\includegraphics[height=35px]{pics/logo.jpg}}
%\logo{\includegraphics[height=30px]{pics/uteplogo100.jpg}}
\title{Math in the News: Mersenne Primes}
\institute{{\large Helmut Knaust}\medskip\\Department of Mathematical Sciences\\The University of Texas at El Paso\\El Paso TX 79968-0514\medskip\\\tt{hknaust@utep.edu}}
\date{{\small{\emph{Greater El Paso Council of Teachers of Mathematics}\\Fall Conference}}\medskip\\{\small October 18, 2008}}
\setbeamertemplate{theorems}[normal font]
\newtheorem{defi}{Definition}
\newtheorem{con}[defi]{Conjecture}
\newtheorem{thm}[defi]{Theorem}
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\nat}{\field{N}}
\newcommand{\zet}{\field{Z}}
\newcommand{\real}{\field{R}}
\newcommand{\rat}{\field{Q}}
\newcommand{\cpl}{\field{C}}
\newcommand{\ilf}[1]{$\displaystyle #1 $}
\newcommand{\sol}[2]{\\{\textcolor{orange}{\textbf{\tiny Solved by #1\hfill#2}}}}
\renewcommand\thefootnote{\fnsymbol{footnote}}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

\section{Math in the News}
\begin{frame}
\tableofcontents[hideallsubsections]
\end{frame}


\begin{frame}
\begin{figure}
\includegraphics[height=5cm]{pics/UCLA.jpg}
\end{figure}
By the way, the number of atoms in the universe has about 80~digits\ldots
\end{frame}


\section{Prime numbers}
\subsection{Definition and Examples}
\begin{frame}
\begin{defi}
A \textbf{prime number} is a natural number that has exactly two divisors (1 and itself)
\end{defi}\vspace{1cm}
Here are the first 100 prime numbers: 
\begin{figure}
\includegraphics[width=10cm]{pics/01.pdf}
\end{figure}
\end{frame}



\begin{frame}
\begin{thm}<1->
A natural number $p>1$ is prime if and only if no prime number $\leq\sqrt{p}$ divides $p$.
\end{thm}\vspace{1cm}
\visible<2->{For example, to check that 107 is a prime number, we have to check whether 107 is divisible by by 2, 3, 5 and 7.}
\end{frame} 

\subsection{Basic Results and Techniques}
\begin{frame}
Another way to find prime numbers is the \emph{Sieve of Eratosthenes} ($\approx$ 240~BC):
\begin{figure}
\includegraphics<1>[height=6cm]{pics/02.pdf}%
\includegraphics<2>[height=6cm]{pics/03.pdf}%
\includegraphics<3>[height=6cm]{pics/04.pdf}%
\includegraphics<4>[height=6cm]{pics/05.pdf}%
\includegraphics<5>[height=6cm]{pics/06.pdf}%
\includegraphics<6>[height=6cm]{pics/07.pdf}%
\includegraphics<7>[height=6cm]{pics/08.pdf}%
\medskip
\end{figure}
\end{frame}

\begin{frame}
The next slide shows a graphical representation of the \emph{Sieve of Eratosthenes} for all numbers $\leq 601^2=361\,201$.\vspace{0.5cm}
\begin{itemize}
\item
Black dots represent primes, 
\item
White dots represent composite numbers.
\end{itemize}
\end{frame}

\begin{frame}
\begin{figure}
\includegraphics<1>[height=8cm]{pics/003.pdf}%
\includegraphics<2>[height=8cm]{pics/007.pdf}%
\includegraphics<3>[height=8cm]{pics/017.pdf}%
\includegraphics<4>[height=8cm]{pics/043.pdf}%
\includegraphics<5>[height=8cm]{pics/103.pdf}%
\includegraphics<6>[height=8cm]{pics/307.pdf}%
\includegraphics<7>[height=8cm]{pics/601.pdf}%
\end{figure}
\end{frame}

\begin{frame}
\begin{thm}[Euclid, $\approx$ 300 BC]<1->
\textbf{The Fundamental Theorem of Arithmetic.}\\
Every natural number greater than 1 can be written as the product of (one or more) primes. The factorization is unique up to reordering.
\end{thm}\vspace{1cm}
\visible<2->{For example: $564\,738\,409\,098=2\times 3^3\times 109 \times 3\,083\times 31\,121$.}
\end{frame}

\section{How Many Primes?}
\subsection{Euclid's Theorem}
\begin{frame}
\begin{thm}[Euclid, $\approx$ 300 BC]<1->
There are infinitely many prime numbers. 
\end{thm}\vspace{.5cm}

\visible<2->{\textbf{Proof:} Suppose there are only finitely many primes. More precisely, suppose that
\[\{p_1,p_2,p_3,\ldots,p_n\}\] is a complete list of all prime numbers.}\vspace{.5cm}

\visible<3->{Consider the number $N=p_1\times p_2\times\cdots\times p_n+1$.}\vspace{.5cm}

\visible<4->{Observe that $N$ is not divisible by any of the primes $p_1,p_2,p_3,\ldots p_n$ on our complete list.}
\end{frame} 
\begin{frame}
\visible<1->{Now there are two possibilities: If $N$ is prime, we obtain a contradiction since $N$ is not on our complete list of primes.}\vspace{.5cm} 

\visible<2->{If, on the other hand, $N$ is not prime, it must be divisible by one of the primes on our list - but it is not!}\vspace{.5cm}

\visible<3->{In either case we get a contradiction to our assumption that there are only finitely many primes. So there must be infinitely many primes!}
\end{frame} 

\subsection{The Prime Number Theorem}
\begin{frame}The most celebrated result in number theory was conjectured by both Legendre and Gauss at the end of the 18th century, but only proved a century later:\vspace{0.5cm}
\begin{thm}[Hadamard/de la Vall\'{e}e Poussin, 1896]
\textbf{The Prime Number Theorem.}\\
Let $\Pi(n)$ denote the number of prime numbers $\leq n$. Then 
\[\lim_{n\to\infty}\frac{\Pi(n)}{n/\ln(n)}=1.\]
\end{thm}
\end{frame}

\begin{frame}
The approximation is pretty slow:
\begin{figure}
\includegraphics[width=10cm]{pics/10.pdf}
\end{figure}
\end{frame}

\subsection{Classical Conjectures and Recent Results}
\begin{frame}
\begin{con}[Goldbach, 1742]<1->
\textbf{The Goldbach Conjecture.}\\
Every even natural number greater than 2 is the sum of two primes.
\end{con}\vspace{0.25cm}
\visible<2->{Here is an example: $46=17+29\ (=3+43=5+41=23+23)$.\vspace{0.5cm}}

\visible<3-> {Note that the Goldbach Conjecture would imply that every odd prime number $>5$ is the sum of three prime numbers.} 
\end{frame}

\begin{frame}
The best known result is \vspace{0.5cm}
\begin{thm}[Vinogradov, 1937]<1->
Every \textbf{large} odd prime number is the sum of three primes.
\end{thm}\vspace{0.5cm}
\visible<2->{``Large" currently means ``greater than $10^{1345}$".}
\end{frame}

\begin{frame}
\begin{con}<1->
\textbf{The Twin Prime Conjecture.}\\
There are infinitely many pairs of primes with difference 2.
\end{con}\vspace{0.25cm}
\visible<2->{Examples are 5 and 7, 461 and 463.}\vspace{.5cm}

\visible<3->{The best result known is 
\begin{thm}[Chen, 1966] There are infinitely many pairs $p,\ p+2$ such that \begin{itemize}
\item $p$ is prime, and \item $p+2$ is prime or a product of two primes.\end{itemize}
\end{thm}}
\end{frame}

\begin{frame}
\begin{thm}[Green-Tao Theorem, 2004]<1->
There are arbitrarily long sequences of primes in arithmetic progression.
\end{thm}\vspace{0.5cm}
\visible<2->{Here is an example of five primes in arithmetic progression:  \[5, 11, 17, 23, 29.\]
The longest currently known sequence of primes in arithmetic progression was found in 2004. It has length $23$, starts at $56\,211\,383\,760\,397$, with differences $44\,546\,738\,095\,860$.}
\end{frame}

\begin{frame}
\begin{figure}
\includegraphics{pics/Tao.jpg}
\end{figure}
\begin{center}Terence Tao, 1975--\\2006 Fields Medal Recipient\end{center}
\end{frame}

\section{Mersenne Primes}
\subsection{Definition and Examples}
\begin{frame}
\begin{defi}<1->
A prime number of the form $2^p-1$ is called the \textbf{Mersenne prime} $M_p$. The number $p$ is then called a \textbf{Mersenne exponent.}\vspace{0.5cm}
\end{defi}
\visible<2->{Here are some examples: If $p=2$, $2^2-1=3$ is a Mersenne prime; $p=7$ yields the Mersenne prime $2^7-1=127$.} \vspace{0.5cm}

\visible<3->{This does not work for all $p$, even is $p$ is a prime number. For example $2^{11}-1=2047$ is not a prime:
\[2^{11}-1=23\times 89\]} 
\end{frame}

\subsection{Mersenne's Claim}
\begin{frame}
\begin{figure}
\includegraphics[height=5cm]{pics/Mersenne.jpg}
\end{figure}
\begin{center}Marin Mersenne, 1588--1648\end{center}
\end{frame}

\begin{frame}
\visible<1->{Marin Mersenne boldly claimed in 1644 that a complete list of Mersenne exponents less than 258 is given by 

\[\{2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257\}\]}\vspace{0.5cm}

\visible<2->{Here is the list of the corresponding 11~numbers of the form $2^p-1$:
\begin{figure}
\includegraphics[width=10cm]{pics/09.pdf}
\end{figure}}
\end{frame}

\begin{frame}
\visible<1->{Mersenne was wrong---two numbers on his list are not primes:
\[2^{67}-1=93\,707\,721\times 61\,838\,257\,287\]
\begin{eqnarray*}
2^{257}-1&=&35\,006\,138\,814\,359\\
&\times& 1\,155\,685\,395\,246\,619\,182\,673\,033\\
&\times& 374\,550\,598\,501\,810\,936\,581\,776\,630\,096\,313\,181\,393
\end{eqnarray*}}

\visible<2->{Worse---he also missed three exponents:
\[2^{61}-1, \ 2^{89}-1 \mbox{ and } 2^{107}-1 \mbox{ are prime numbers.}\]}
\end{frame}

\begin{frame}
\visible<1->{Mersenne's list again:
\[\{2, 3, 5, 7, 13, 17, 19, 31, \alert{67}, 127, \alert{257}\}\]\vspace{0.5cm}}

\visible<2->{Here is the corrected list of Mersenne exponents less than 258:

\[\{2, 3, 5, 7, 13, 17, 19, 31, \alert{61}, \alert{89}, \alert{107}, 127\}\]}
\end{frame}

\begin{frame}
\begin{thm}<1->
If $a^p-1$ is a prime number, then $a=2$ and $p$ is prime.
\end{thm}

\visible<2->{\textbf{Proof:} I will only prove that $2^p-1$ prime implies that $p$ is prime.
Assume that $p$ is not prime, then $p = m\times  k$, with $m,k\geq 2$.
So \[2^p-1 =  (2^m)^k-1.\]}

\visible<3->{\noindent Do you remember how to factor $x^3-1$? $(2^m)^k-1$ works the same way:}
\visible<4->{\[(2^m)^k-1 = (2^m-1) \times \left((2^m)^{k-1}+ (2^m)^{k-2}+ (2^m)^{k-3} +\cdots + (2^m) +1\right).\]
End of the story!  $2^p-1$ is divisible by $2^m-1$, and hence not prime.}
\end{frame}

\section{Perfect Numbers}
\subsection{Definition and Examples}

\begin{frame}
\begin{defi}<1->
A natural number is called a \textbf{perfect number} if it equals the sum of its proper divisors.
\end{defi}\vspace{0.5cm}
\visible<2->{Here are the first two examples:
\[6=1+2+3,\]
\[28=1+2+4+7+14.\]}
\end{frame}

\subsection{Perfect Numbers and Mersenne Primes}
\begin{frame}
\visible<1->{As it turns out there is a perfect correspondence between Mersenne primes and \textbf{even} perfect numbers.}

\begin{thm}[Euclid, $\approx$ 300 BC]<2->
If $2^p-1$ is prime, then $2^{p-1}\times (2^p-1)$ is perfect.
\end{thm}

\begin{thm}[Euler, 1707--1783]<3->
If $n$ is an even perfect number, then $n=2^{p-1}\times (2^p-1)$ for some Mersenne prime $2^p-1$. 
\end{thm}

\begin{con}<4->
All perfect numbers are even.
\end{con}
\end{frame}

\section{Computing Mersenne Primes}
\subsection{Known Mersenne Primes}
\begin{frame}
\begin{figure}
\includegraphics[width=10cm]{pics/Primes1.pdf}
\end{figure}
\end{frame}

\begin{frame}
\begin{figure}
\includegraphics[width=10cm]{pics/Primes2.pdf}
\end{figure}
\end{frame}

\subsection{Lucas-Lehmer Test}
\begin{frame}
Nowadays, primality of Mersenne numbers is established with a test developed by \'{E}douard Lucas~(1842--1891) and improved by Derrick H.~Lehmer~(1905--1991):

\begin{thm}[Lucas-Lehmer Test, 1870s/1930s]
Consider the sequence
\[s_0=4,\quad s_n=s_{n-1}^2-2 \mbox{ for } n\geq 1.\]
Let $p$ be an odd prime. Then $2^p-1$ is a Mersenne prime if and only if $s_{p-2}=0 \pmod{2^p-1}$.
\end{thm}
\end{frame}

\begin{frame}
Here is how this works to check that $2^7-1=127$ is a Mersenne prime:\vspace{0.5cm}

\begin{center}
\begin{tabular}{|r|r|r|}
\hline
n&$s_n$&$s_n \pmod{127}$\\  \hline
0&4&4\\
1&14&14\\
2&194&67\\
3&4\,487&42\\
4&1\,762&111\\
5&12\,319&0\\ \hline
\end{tabular}
\end{center}
\end{frame}

\begin{frame}
\begin{figure}
\includegraphics[width=8cm]{pics/lehmermachine.jpg}

Lehmer's \emph{Photoelectric Number Sieve}
\end{figure}
\begin{center}
\end{center}
\end{frame}

\subsection{GIMPS}
\begin{frame}
\begin{figure}
\href{http://www.mersenne.org}{\includegraphics[width=9cm]{pics/gimps.jpg}}
\end{figure}
\begin{center}
\href{http://www.mersenne.org}{www.mersenne.org}
\end{center}
\end{frame}

\subsection*{Conclusion}
\begin{frame}
\begin{center}
\Large{\emph{All Questions Answered,}}\\
\Large{\emph{All Answers Questioned}}~\footnote{Borrowed from Donald Knuth}\vspace{1cm}\\
Contact:\quad\texttt{hknaust@utep.edu}\end{center}
\end{frame}

\appendix
\begin{frame}
\begin{figure}
\includegraphics[height=7cm]{pics/LLnb.pdf}
\end{figure}
\begin{center}
\end{center}
\end{frame}

\begin{frame}
\begin{columns}[t]
\column{5cm}
\begin{center}
David Hilbert\\(1862--1943)
\end{center}
\vspace{3.0cm}
\begin{center}
\emph{We Must Know}\\
\emph{We Shall Know}
\end{center}
\column[T]{5cm}
\includegraphics[height=7cm]{pics/DH.jpg}
\end{columns}
\end{frame}
\end{document}