\documentclass[10pt,envcountsect]{beamer}

\mode<presentation> {
  \usetheme{Warsaw}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pstricks}
\usepackage{multicol}
\usepackage{multido}
\newcommand{\Z}{\mathbf{Z}}


\begin{document}

\title{Episode 04 -- Gaussian primes}
\subtitle{European section -- Season 3}
\date{}

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


\begin{frame}{Units and primes}
\begin{definition}[Units]
Any Gaussian integer is obviously divisible by $1$, $-1$, $i$ and $-i$, as $(-1)\times (-1)=1$ and $i\times(-i)=1$. We call these four special numbers the \emph{units} of $\Z[i]$.
\end{definition}\pause

\begin{definition}[Gaussian prime]
Any Gaussian integer $g$ is divisible by $1$, $-1$, $i$, $-i$, $g$, $-g$, $-ig$ and $ig$. A \emph{Gaussian} prime is a Gaussian integer that is not divisible by an integer different from these ones.\\
In other words, a Gaussian integer $g$ is not \emph{prime} if it can be written as a non-trivial product $g=e\times f$, where neither $e$ nor $f$ are units.
\end{definition}

\end{frame}


\begin{frame}{Conjugate and norm}

\begin{definition}[Conjugate]
The \emph{conjugate} of a Gaussian integer $g=a+bi$ is $\bar{g}=a-bi$.
\end{definition}\pause

\begin{example}
The conjugate og $g=-3+4i$ is $\bar{g}=-3-4i$.
\end{example}\pause

\begin{definition}
The product of a Gaussian integer $g=a+bi$ and its conjugate $\bar{g}=a-bi$ is a non-negative real number, as $$g\times\bar{g}=(a+bi)(a-bi)=a^2-(bi)^2=a^2+b^2.$$
This number is defined as the norm of $g$, noted $N(g)$.
\end{definition}\pause

\begin{example}
The norm of $g=-3+4i$ is $N(g)=(-3)^2+4^2=25$.
\end{example}

\end{frame}


\begin{frame}{Conjugate and norm}
\begin{center}
\psset{unit=0.6cm}
\begin{pspicture}(-6,-6)(6,6)
\multido{\n=-5+1}{11}{
\multido{\d=-5+1}{11}{
\psdot[dotstyle=o,dotsize=2pt](\n,\d)
}}
\psline(-5,0)(5,0)
\psline(0,-5)(0,5)
\psdots(0,0)(0,1)(1,0)
\uput[dl](0,0){$0$}
\uput[ul](0,1){$i$}
\uncover<+->{\uput[dr](1,0){$1$}}
\uncover<+->{\psdot(4,3)\uput[u](4,3){$g=a+bi$}}
\uncover<+->{\psdot(4,-3)\uput[d](4,-3){$\bar{g}=a-bi$}}
\uncover<+->{\psline(0,0)(4,3)
\uput[dr](2,1.5){$\sqrt{N(g)}=\sqrt{a^2+b^2}$}}
\uncover<+->{\psline(0,0)(4,-3)
\uput[ur](2,-1.5){$\sqrt{N(\bar{g})}=\sqrt{N(g)}$}}
\end{pspicture}
\end{center}

\end{frame}

\begin{frame}{Two important questions}

\begin{block}{Question 1}
What Gaussian integers are prime and, in particular, are all prime integers Gaussian primes ?
\end{block}\pause
 
\begin{block}{Question 2}
Is it still possible to decompose uniquely any Gaussian integer into a product of Gaussian primes ?
\end{block}

\end{frame}

\begin{frame}{Gaussian primes}
\begin{center}
\psset{unit=0.4cm}
\begin{pspicture}(-10,-10)(10,10)
\multido{\n=-10+1}{21}{
\multido{\d=-10+1}{21}{
\psdot[dotstyle=o,dotsize=2pt](\n,\d)
}}
\psline(-10,0)(10,0)
\psline(0,-10)(0,10)
\psdots(0,0)(0,1)(1,0)
\uput[dl](0,0){$0$}
\uput[ul](0,1){$i$}
\end{pspicture}
\end{center}

\end{frame}


\begin{frame}{Primality in $\Z[i]$}

\begin{theorem}
A Gaussian integer $g=a+bi$ is prime if and only if \pause
\begin{itemize}
\item one of $a$ and $b$ is zero and the other is a prime of the form $4n+3$ or its negative $-(4n+3)$ ;\pause
\item or both are nonzero and the norm of $g$, $N(g)=a^2+b^2$ is prime.
\end{itemize}
\end{theorem}

\end{frame}

\begin{frame}{Primality in $\Z[i]$}

\begin{block}{Proof.}
We will just prove the first case, specifically the case when $b=0$ and $a+bi=a\in\Z$.\pause To do so, we will use two lemmas.\pause

\begin{lemma}
If $a=4n+1$, there exists two integers $x$ and $y$ such that $a=x^2+y^2=(x+iy)(x-iy)$. This result is known as ``Fermat's theorem on sums of two squares.''
\end{lemma}\pause

\begin{lemma}
No sum of integer squares can be written $4n+3$.
\end{lemma}\pause

It's obvious that $a$ must be a prime integer, and that if $a=4n$ or $4n+2$ it is not prime, as it is divisible by $2$.\pause\ If $a=4n+1$, Fermat's theorem on sums of two squares assures us that there exists two integers $x$ and $y$ such that $a=x^2+y^2=(x+iy)(x-iy)$, so $a$ is composite.\pause\ Therefore, if $a$ is prime, it must be a prime integer of the form $4n+3$. 
\end{block}

\end{frame}

\begin{frame}{Primality in $\Z[i]$}

\begin{proof}[Continued]
We must now prove the reciprocal : if $a$ is a prime integer of the form $4n+3$, then it's a Gaussian prime.\pause\ Suppose that $g=a+0i$ for a prime integer $a=4n+3$ and that it can be factored $g=hk$.\pause\ Then $a^2=N(g)=N(h)N(k)$.\pause If the factorization is non-trivial, then $N(h)=N(k)=a$.\pause\ But $h$ is not an integer, so its norm is of the form $u^2+v^2$.\pause\ Then $u^2+v^2=a=4n+3$, which is in contradiction with lemma 2.\pause\ So the factorization must have been trivial and $g$ is a Gaussian prime.
\end{proof}

\end{frame}


\begin{frame}{Examples of Gaussian primes}

\begin{center}
The following Gaussian integers are prime.

\bigskip

\LARGE
\begin{tabular}{cp{0.5cm}cp{0.5cm}cp{0.5cm}c}
$1+i$ && $2+i$ && $3$ && $3+2i$ \\[15pt]
$4+i$ && $5+2i$ && $7+i$ && $5+4i$ \\[15pt]
$7$ && $7+2i$ && $6+5i$ && $8+3i$ \\[15pt]
$6+i$	&& $8+5i$ && $9+4i$ &&\\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Gaussian primes on a lattice}

\begin{center}
\includegraphics[scale=0.19]{Gaussian_primes.eps}
\end{center}


\end{frame}



\begin{frame}{Unique factorization in $\Z[i]$}

\begin{theorem}
The set $\Z[i]$ is a \emph{unique factorization domain} : any Gaussian integer can be written as a product of Gaussian primes, and this decomposition is unique except for reordering or multiplication by units.
\end{theorem}

\end{frame}



\end{document}
