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}

Review Questions