attachment:fermatlittle.tex of Csce877Ch8Notes

   1 \documentclass[]{article}
   2 \usepackage{amsmath}%
   3 \setcounter{MaxMatrixCols}{30}%
   4 \usepackage{amsfonts}%
   5 \usepackage{amssymb}%
   6 \usepackage{graphicx}
   7 \usepackage{geometry}
   8 \newtheorem{theorem}{Theorem}
   9 \newtheorem{acknowledgement}[theorem]{Acknowledgement}
  10 \newtheorem{algorithm}[theorem]{Algorithm}
  11 \newtheorem{axiom}[theorem]{Axiom}
  12 \newtheorem{case}[theorem]{Case}
  13 \newtheorem{claim}[theorem]{Claim}
  14 \newtheorem{conclusion}[theorem]{Conclusion}
  15 \newtheorem{condition}[theorem]{Condition}
  16 \newtheorem{conjecture}[theorem]{Conjecture}
  17 \newtheorem{corollary}[theorem]{Corollary}
  18 \newtheorem{criterion}[theorem]{Criterion}
  19 \newtheorem{definition}[theorem]{Definition}
  20 \newtheorem{example}[theorem]{Example}
  21 \newtheorem{exercise}[theorem]{Exercise}
  22 \newtheorem{lemma}[theorem]{Lemma}
  23 \newtheorem{notation}[theorem]{Notation}
  24 \newtheorem{problem}[theorem]{Problem}
  25 \newtheorem{proposition}[theorem]{Proposition}
  26 \newtheorem{remark}[theorem]{Remark}
  27 \newtheorem{solution}[theorem]{Solution}
  28 \newtheorem{summary}[theorem]{Summary}
  29 \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
  30 \geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in}
  31 
  32 \title{Fermat's Little Theorem}
  33 \author{Dr. Scot Anderson}
  34 
  35 \begin{document}
  36 	
  37 	\maketitle
  38 	
  39 	\begin{abstract}
  40 		
  41 	\end{abstract}
  42 
  43 \begin{theorem}
  44 [Fermat's Little Theorem]Let $p$ be a prime and $a\in Z^{+}$ such that
  45 $a\operatorname{mod}p\neq0$. Then
  46 \begin{equation}
  47 a^{p-1}\equiv1\operatorname{mod}p
  48 \end{equation}
  49 
  50 \end{theorem}
  51 
  52 \begin{proof}
  53 Consider $Z_{p}=\left\{  0,1,...,p-1\right\}  $, we know that multiplying each
  54 element of $Z_{p}$ by $a$ modulo $p$ just gives us $Z_{p}$ in some order.
  55 Since $0\times a\operatorname{mod}p=0$ we have the last $p-1$ numbers of
  56 $Z_{p}$ multiplied by $a$ as:%
  57 \begin{align}
  58 a\times Z_{p}\backslash\left\{  0\right\}   &  =\left\{  a,2a,3a,...,\left(
  59 p-1\right)  a\right\} \nonumber\\
  60 &  \equiv\left\{  a\operatorname{mod}p,2a\operatorname{mod}p,...,\left(
  61 p-1\right)  a\operatorname{mod}p\right\}
  62 \end{align}
  63 If we multiply all the numbers in the set we have
  64 \begin{align}
  65 a\times2a\times3a\times...\times\left(  p-1\right)  a  &  =a^{p-1}\left(
  66 1\times2\times...\times\left(  p-1\right)  \right) \nonumber\\
  67 &  =a^{p-1}\left(  p-1\right)  !
  68 \end{align}
  69 and
  70 \begin{equation}
  71 a^{p-1}\left(  p-1\right)  !\equiv a\operatorname{mod}p\times
  72 2a\operatorname{mod}p\times...\times\left(  p-1\right)  a\operatorname{mod}p
  73 \label{eq:1}%
  74 \end{equation}
  75 Because we know that all the terms in (\ref{eq:1}) map to some unique element
  76 in $Z_{p}$ not $0$ we have the following%
  77 \begin{equation}
  78 a^{p-1}\left(  p-1\right)  !\equiv\left(  1\times2\times...\times\left(
  79 p-1\right)  \right)  \operatorname{mod}p
  80 \end{equation}
  81 and
  82 \begin{equation}
  83 a^{p-1}\left(  p-1\right)  !\equiv\left(  p-1\right)  !\operatorname{mod}p
  84 \label{eq:2}%
  85 \end{equation}
  86 Since $\left(  p-1\right)  $ is relatively prime to $p$ (because $p$ is prime)
  87 we can divide out $\left(  p-1\right)  !$ from each side of (\ref{eq:2}) to
  88 get the result:%
  89 \[
  90 a^{p-1}\equiv1\operatorname{mod}p
  91 \]
  92 
  93 \end{proof}
  94 
  95 \begin{theorem}
  96 An alternate form of Fermat's Little theorem: Let $p$ be prime and $a\in
  97 Z^{+}$ such that $a\operatorname{mod}p\neq0$. Then%
  98 \[
  99 a^{p}=a\operatorname{mod}p
 100 \]
 101 
 102 \end{theorem}
 103 
 104 \begin{definition}
 105 Let $n\in Z^{+}$ then we define the totient function $\phi\left(  n\right)  $
 106 is defined to be the number of positive integers less than $n$ that are
 107 relatively prime to $n$. That is
 108 \begin{equation}
 109 \phi\left(  n\right)  =\left\{  x:x\in Z^{+},x<n,\gcd\left(  x,n\right)
 110 =1\right\}
 111 \end{equation}
 112 
 113 \end{definition}
 114 
 115 \begin{lemma}
 116 Let $n$ be a prime number. Then%
 117 \begin{equation}
 118 \phi\left(  n\right)  =n-1
 119 \end{equation}
 120 
 121 \end{lemma}
 122 
 123 \begin{theorem}
 124 Given a composit number $n=p\times q$ where $p,q$ are prime then
 125 \begin{equation}
 126 \phi\left(  n\right)  =\phi\left(  p_{1}\right)  \times\phi\left(
 127 p_{2}\right)
 128 \end{equation}
 129 
 130 \end{theorem}
 131 
 132 \begin{proof}
 133 Consider that the set of residues in $Z_{n}$ is $\left\{
 134 0,1,...,pq-1\right\}  $. Now the residues that are not relatively prime to $p$
 135 are
 136 \begin{equation}
 137 \left\{  p,2p,...,\left(  q-1\right)  p\right\}  \label{eq:3}%
 138 \end{equation}
 139 and the residues that are not relatively prime to $q$ are
 140 \begin{equation}
 141 \left\{  q,2q,...,\left(  p-1\right)  q\right\}  \label{eq:4}%
 142 \end{equation}
 143 Clearly the size of the two sets of residues not relatively prime to $n$ are
 144 $\left(  p-1\right)  $ and $\left(  q-1\right)  $ plus the $0$ element. So we
 145 have
 146 \begin{align}
 147 \phi\left(  n\right)    & =pq-\left[  \left(  p-1\right)  +\left(  q-1\right)
 148 +1\right]  \nonumber\\
 149 & =pq-\left(  p-1\right)  -\left(  q-1\right)  -1\nonumber\\
 150 & =pq-p-q+1\nonumber\\
 151 & =p\left(  q-1\right)  -\left(  q-1\right)  \nonumber\\
 152 & =\left(  p-1\right)  \left(  q-1\right)
 153 \end{align}
 154 
 155 \end{proof}
 156 
 157 \begin{theorem}
 158 [Euler's Theorem]Let $a$ and $n$ be relatively prime positive numbers, then
 159 \begin{equation}
 160 a^{\phi\left(  n\right)  }\equiv1\left(  \operatorname{mod}n\right)
 161 \label{eq:5}%
 162 \end{equation}
 163 
 164 \end{theorem}
 165 
 166 \begin{proof}
 167 First we not that if $n$ is prime that the Theorem holds from Fermat's little
 168 Theorem. Namely (\ref{eq:5}) reduces to
 169 \begin{equation}
 170 a^{n-1}=1\operatorname{mod}n
 171 \end{equation}
 172 Consider the set of integers relatively prime to $n$:
 173 \[
 174 R=\left\{  x_{1},...,x_{\phi\left(  n\right)  }\right\}
 175 \]
 176 Multiplying the set by $a$ modulo $n$ gives:%
 177 \[
 178 S=\left\{  ax_{1}\operatorname{mod}n,...,ax_{\phi\left(  n\right)
 179 }\operatorname{mod}n\right\}
 180 \]
 181 We claim that $S$ is a permutation of $R$. Consider that $a$ and $x_{i}\in R$
 182 are relatively prime to $n$. Then $ax_{i}$ must also be relatively prime to
 183 $n$ and $ax_{i}\operatorname{mod}n\neq0$. Thus all the members of $S$ are
 184 relatively prime to $n$. There can be no duplicates in $S$ because
 185 \[
 186 ax_{i}\operatorname{mod}n=ax_{j}\operatorname{mod}n\rightarrow x_{i}%
 187 \operatorname{mod}n=x_{j}\operatorname{mod}n
 188 \]
 189 because there exists a $a^{-1}$ in $Z_{n}$. But $x_{i}<n$ and $x_{j}<n$, so we
 190 must have that
 191 \[
 192 x_{i}=x_{j}%
 193 \]
 194 and we have that there are no duplicates in $S$. Therefore $S$ is a
 195 permutation of $R$. Consider%
 196 \[
 197 \prod_{i=1}^{\phi\left(  n\right)  }\left(  ax_{i}\operatorname{mod}n\right)
 198 =\prod_{i=1}^{\phi\left(  n\right)  }x_{i}%
 199 \]
 200 Then%
 201 \[
 202 \prod_{i=1}^{\phi\left(  n\right)  }ax_{i}\equiv\prod_{i=1}^{\phi\left(
 203 n\right)  }x_{i}\left(  \operatorname{mod}n\right)
 204 \]
 205 Which gives%
 206 \[
 207 a^{\phi\left(  n\right)  }\times\prod_{i=1}^{\phi\left(  n\right)  }%
 208 x_{i}\equiv\prod_{i=1}^{\phi\left(  n\right)  }x_{i}\left(  \operatorname{mod}%
 209 n\right)
 210 \]
 211 Now since $\prod_{i=1}^{\phi\left(  n\right)  }x_{i}$ is relatively prime to
 212 $n$, we can cancel on each side to get the result%
 213 \[
 214 a^{\phi\left(  n\right)  }\equiv1\left(  \operatorname{mod}n\right)
 215 \]
 216 
 217 \end{proof}
 218 
 219 \begin{theorem}
 220 Alternate form of Euler's Theorem: Let $a$ and $n$ be relatively prime
 221 positive numbers, then%
 222 \[
 223 a^{\phi\left(  n\right)  +1}=a\left(  \operatorname{mod}n\right)
 224 \]
 225 
 226 \end{theorem}
 227 
 228 \begin{corollary}
 229 Let $n=pq$ and $m$ be integers where $p$ and $q$ are prime numbers and
 230 $0<m<n$. Then
 231 \[
 232 m^{\phi\left(  n\right)  +1}=m^{\left(  p-1\right)  \left(  q-1\right)
 233 +1}\equiv m\left(  \operatorname{mod}n\right)
 234 \]
 235 
 236 \end{corollary}
 237 
 238 \begin{theorem}
 239 [CRT]Let $S=\left\{  m_{1},...,m_{k}\right\}  $ and%
 240 \[
 241 M=\prod_{i=1}^{k}m_{i}%
 242 \]
 243 where for all $m_{i},m_{j}\in S,\gcd\left(  m_{i},m_{j}\right)  =1$ (that is
 244 they are pairwise relatively prime). We can represent any integer in $Z_{m}$
 245 by the $k-$tuple whose elements are in $Z_{m_{i}}$. That is we have a
 246 bijection:
 247 \[
 248 A\longleftrightarrow\left(  a_{1},...,a_{k}\right)
 249 \]
 250 
 251 \end{theorem}
 252 
 253 \begin{proof}
 254 Define
 255 \[
 256 a_{i}=A\operatorname{mod}m_{i}%
 257 \]
 258 Let
 259 \[
 260 M_{i}=M/m_{i}\text{ for }1\leq i\leq k
 261 \]
 262 so that the following condition holds:%
 263 \[
 264 M_{i}=0\left(  \operatorname{mod}m_{i}\right)
 265 \]
 266 Since $M_{i}$ is relatively prime to $m_{i}$ we define the following:%
 267 \[
 268 c_{i}=M_{i}\times\left(  M_{i}^{-1}\operatorname{mod}m_{i}\right)  \text{ for
 269 }1\leq i\leq k
 270 \]
 271 We claim that the following holds, but why we have no idea!%
 272 \[
 273 A\equiv\left(  \sum_{i=1}^{k}a_{i}c_{i}\right)  \operatorname{mod}M
 274 \]
 275 
 276 \end{proof}
 277 
 278 \end{document}