Fermat's Little Theorem

\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
\usepackage{geometry}
\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}}
\geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in}

%%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

What is a prime number?

A prime number is a number that is divisable only by 1 and itself.

What is the meaning of the expression a divides b?

a divides b if a is a factor of b.

What is Euler's totient?

Given a number n the totient of n is the number of integers less than n that are relatively prime to n.

The Miller-Rabin test can determine if a number is not prime but can't determine if a number is prime. How can such an algorithm be used to test for primality?

By repeatedly running the test with different random numbers we and getting indeterminite answers we increase the probability that a number is prime.

What is a primative root of a number?

A primitive root is a number a that generates (via powers) a set (like Zn). We can also say that the highest possible exponent to which a number can belong (mod n) is latex2($\phi(n)$). If a number is of this order, it is referred to as a primative root.

What is the difference between an index and a discrete logarithm?

Given a primary root a, the index i of a number n is the power of a such that latex2($n=a^i$). The index thought of as a function behaves like a logarithm.

\usepackage{geometry}
\geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in}
%%end-prologue%%
The equation below gives the exponential form and then the logarithmic form where $x=a^c$:
\begin{eqnarray}
   x = a^{ind_{a,p}(x)} \bmod p \\
   ind_{a,p}(x)= c \bmod p
\end{eqnarray}