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}
[Fermat's Little 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}
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}
\begin{theorem}
An alternate form of Fermat's Little theorem: Let $p$ be prime and $a\in
Z^{+}$ such that $a\operatorname{mod}p\neq0$. Then%
\[
a^{p}=a\operatorname{mod}p
\]
\end{theorem}
\begin{definition}
Let $n\in Z^{+}$ then we define the totient function $\phi\left( n\right) $
is defined to be the number of positive integers less than $n$ that are
relatively prime to $n$. That is
\begin{equation}
\phi\left( n\right) =\left\{ x:x\in Z^{+},x<n,\gcd\left( x,n\right)
=1\right\}
\end{equation}
\end{definition}
\begin{lemma}
Let $n$ be a prime number. Then%
\begin{equation}
\phi\left( n\right) =n-1
\end{equation}
\end{lemma}
\begin{theorem}
Given a composit number $n=p\times q$ where $p,q$ are prime then
\begin{equation}
\phi\left( n\right) =\phi\left( p_{1}\right) \times\phi\left(
p_{2}\right)
\end{equation}
\end{theorem}
\begin{proof}
Consider that the set of residues in $Z_{n}$ is $\left\{
0,1,...,pq-1\right\} $. Now the residues that are not relatively prime to $p$
are
\begin{equation}
\left\{ p,2p,...,\left( q-1\right) p\right\} \label{eq:3}%
\end{equation}
and the residues that are not relatively prime to $q$ are
\begin{equation}
\left\{ q,2q,...,\left( p-1\right) q\right\} \label{eq:4}%
\end{equation}
Clearly the size of the two sets of residues not relatively prime to $n$ are
$\left( p-1\right) $ and $\left( q-1\right) $ plus the $0$ element. So we
have
\begin{align}
\phi\left( n\right) & =pq-\left[ \left( p-1\right) +\left( q-1\right)
+1\right] \nonumber\\
& =pq-\left( p-1\right) -\left( q-1\right) -1\nonumber\\
& =pq-p-q+1\nonumber\\
& =p\left( q-1\right) -\left( q-1\right) \nonumber\\
& =\left( p-1\right) \left( q-1\right)
\end{align}
\end{proof}
\begin{theorem}
[Euler's Theorem]Let $a$ and $n$ be relatively prime positive numbers, then
\begin{equation}
a^{\phi\left( n\right) }\equiv1\left( \operatorname{mod}n\right)
\label{eq:5}%
\end{equation}
\end{theorem}
\begin{proof}
First we not that if $n$ is prime that the Theorem holds from Fermat's little
Theorem. Namely (\ref{eq:5}) reduces to
\begin{equation}
a^{n-1}=1\operatorname{mod}n
\end{equation}
Consider the set of integers relatively prime to $n$:
\[
R=\left\{ x_{1},...,x_{\phi\left( n\right) }\right\}
\]
Multiplying the set by $a$ modulo $n$ gives:%
\[
S=\left\{ ax_{1}\operatorname{mod}n,...,ax_{\phi\left( n\right)
}\operatorname{mod}n\right\}
\]
We claim that $S$ is a permutation of $R$. Consider that $a$ and $x_{i}\in R$
are relatively prime to $n$. Then $ax_{i}$ must also be relatively prime to
$n$ and $ax_{i}\operatorname{mod}n\neq0$. Thus all the members of $S$ are
relatively prime to $n$. There can be no duplicates in $S$ because
\[
ax_{i}\operatorname{mod}n=ax_{j}\operatorname{mod}n\rightarrow x_{i}%
\operatorname{mod}n=x_{j}\operatorname{mod}n
\]
because there exists a $a^{-1}$ in $Z_{n}$. But $x_{i}<n$ and $x_{j}<n$, so we
must have that
\[
x_{i}=x_{j}%
\]
and we have that there are no duplicates in $S$. Therefore $S$ is a
permutation of $R$. Consider%
\[
\prod_{i=1}^{\phi\left( n\right) }\left( ax_{i}\operatorname{mod}n\right)
=\prod_{i=1}^{\phi\left( n\right) }x_{i}%
\]
Then%
\[
\prod_{i=1}^{\phi\left( n\right) }ax_{i}\equiv\prod_{i=1}^{\phi\left(
n\right) }x_{i}\left( \operatorname{mod}n\right)
\]
Which gives%
\[
a^{\phi\left( n\right) }\times\prod_{i=1}^{\phi\left( n\right) }%
x_{i}\equiv\prod_{i=1}^{\phi\left( n\right) }x_{i}\left( \operatorname{mod}%
n\right)
\]
Now since $\prod_{i=1}^{\phi\left( n\right) }x_{i}$ is relatively prime to
$n$, we can cancel on each side to get the result%
\[
a^{\phi\left( n\right) }\equiv1\left( \operatorname{mod}n\right)
\]
\end{proof}
\begin{theorem}
Alternate form of Euler's Theorem: Let $a$ and $n$ be relatively prime
positive numbers, then%
\[
a^{\phi\left( n\right) +1}=a\left( \operatorname{mod}n\right)
\]
\end{theorem}
\begin{corollary}
Let $n=pq$ and $m$ be integers where $p$ and $q$ are prime numbers and
$0<m<n$. Then
\[
m^{\phi\left( n\right) +1}=m^{\left( p-1\right) \left( q-1\right)
+1}\equiv m\left( \operatorname{mod}n\right)
\]
\end{corollary}
\begin{theorem}
[CRT]Let $S=\left\{ m_{1},...,m_{k}\right\} $ and%
\[
M=\prod_{i=1}^{k}m_{i}%
\]
where for all $m_{i},m_{j}\in S,\gcd\left( m_{i},m_{j}\right) =1$ (that is
they are pairwise relatively prime). We can represent any integer in $Z_{m}$
by the $k-$tuple whose elements are in $Z_{m_{i}}$. That is we have a
bijection:
\[
A\longleftrightarrow\left( a_{1},...,a_{k}\right)
\]
\end{theorem}
\begin{proof}
Define
\[
a_{i}=A\operatorname{mod}m_{i}%
\]
Let
\[
M_{i}=M/m_{i}\text{ for }1\leq i\leq k
\]
so that the following condition holds:%
\[
M_{i}=0\left( \operatorname{mod}m_{i}\right)
\]
Since $M_{i}$ is relatively prime to $m_{i}$ we define the following:%
\[
c_{i}=M_{i}\times\left( M_{i}^{-1}\operatorname{mod}m_{i}\right) \text{ for
}1\leq i\leq k
\]
We claim that the following holds, but why we have no idea!%
\[
A\equiv\left( \sum_{i=1}^{k}a_{i}c_{i}\right) \operatorname{mod}M
\]
\end{proof}