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}