Fermat's Little Theorem

\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}

%%end-prologue%%

\begin{theorem}
Let $p$ be a prime and $a\in Z^{+}$ such that $a\operatorname{mod}p\neq0$.
Then
\begin{equation}
a^{p-1}\equiv1\operatorname{mod}p
\end{equation}

\end{theorem}

\begin{proof}[Fermat's Little Theorem]
Consider $Z_{p}=\left\{  0,1,...,p-1\right\}  $, we know that multiplying each
element of $Z_{p}$ by $a$ modulo $p$ just gives us $Z_{p}$ in some order.
Since $0\times a\operatorname{mod}p=0$ we have the last $p-1$ numbers of
$Z_{p}$ multiplied by $a$ as:%
\begin{align}
a\times Z_{p}\backslash\left\{  0\right\}   & =\left\{  a,2a,3a,...,\left(
p-1\right)  a\right\} \nonumber\\
& \equiv\left\{  a\operatorname{mod}p,2a\operatorname{mod}p,...,\left(
p-1\right)  a\operatorname{mod}p\right\}
\end{align}
If we multiply all the numbers in the set we have
\begin{align}
a\times2a\times3a\times...\times\left(  p-1\right)  a  & =a^{p-1}\left(
1\times2\times...\times\left(  p-1\right)  \right) \nonumber\\
& =a^{p-1}\left(  p-1\right)  !
\end{align}
and
\begin{equation}
a^{p-1}\left(  p-1\right)  !\equiv a\operatorname{mod}p\times
2a\operatorname{mod}p\times...\times\left(  p-1\right)  a\operatorname{mod}%
p\label{eq:1}%
\end{equation}
Because we know that all the terms in (\ref{eq:1}) map to some unique element
in $Z_{p}$ not $0$ we have the following%
\begin{equation}
a^{p-1}\left(  p-1\right)  !\equiv\left(  1\times2\times...\times\left(
p-1\right)  \right)  \operatorname{mod}p
\end{equation}
and
\begin{equation}
a^{p-1}\left(  p-1\right)  !\equiv\left(  p-1\right)  !\operatorname{mod}%
p\label{eq:2}%
\end{equation}
Since $\left(  p-1\right)  $ is relatively prime to $p$ (because $p$ is prime)
we can divide out $\left(  p-1\right)  !$ from each side of (\ref{eq:2}) to
get the result:%
\[
a^{p-1}\equiv1\operatorname{mod}p
\]

\end{proof}

Review Questions