Differences between revisions 6 and 7
Revision 6 as of 2005-10-17 19:45:22
Size: 3199
Editor: yakko
Comment:
Revision 7 as of 2005-10-18 01:11:05
Size: 8254
Editor: yakko
Comment:
Deletions are marked like this. Additions are marked like this.
Line 35: Line 35:
Let $p$ be a prime and $a\in Z^{+}$ such that $a\operatorname{mod}p\neq0$.
Then
[Fermat's Little Theorem]Let $p$ be a prime and $a\in Z^{+}$ such that
$a\operatorname{mod}p\neq0$. Then
Line 43: Line 43:
\begin{proof}[Fermat's Little Theorem] \begin{proof}
Line 49: Line 49:
a\times Z_{p}\backslash\left\{ 0\right\} & =\left\{ a,2a,3a,...,\left( a\times Z_{p}\backslash\left\{ 0\right\} &  =\left\{ a,2a,3a,...,\left(
Line 51: Line 51:
& \equiv\left\{ a\operatorname{mod}p,2a\operatorname{mod}p,...,\left( &  \equiv\left\{ a\operatorname{mod}p,2a\operatorname{mod}p,...,\left(
Line 56: Line 56:
a\times2a\times3a\times...\times\left( p-1\right) a & =a^{p-1}\left( a\times2a\times3a\times...\times\left( p-1\right) a &  =a^{p-1}\left(
Line 58: Line 58:
& =a^{p-1}\left( p-1\right) ! &  =a^{p-1}\left( p-1\right) !
Line 63: Line 63:
2a\operatorname{mod}p\times...\times\left( p-1\right) a\operatorname{mod}%
p\label{eq:1}%
2a\operatorname{mod}p\times...\times\left( p-1\right) a\operatorname{mod}p
\label{eq:1}%
Line 74: Line 74:
a^{p-1}\left( p-1\right) !\equiv\left( p-1\right) !\operatorname{mod}%
p\label{eq:2}%
a^{p-1}\left( p-1\right) !\equiv\left( p-1\right) !\operatorname{mod}p
\label{eq:2}%
Line 94: Line 94:

Unknown environment 'definition'

Unknown environment 'lemma'

Unknown environment 'theorem'

Unknown environment 'proof'

Unknown environment 'theorem'

Unknown environment 'proof'

Unknown environment 'theorem'

Unknown environment 'corollary'

Unknown environment 'theorem'

Unknown environment 'proof'

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

Csce877Ch8Notes (last edited 2020-01-26 17:11:14 by 68)