The Sixth Lesson of the Course
Commentary on Modular Arithmetic
20feb12\begin{document} \maketitle
\section{Introduction}
You will find all but the last section here in D'Angelo-West, Chapter 7.
The approach is considerably simplified and directed to one goal, namely
our exposition of the RSA Public Key Encryption algorithm.
\section{Clock arithmetic}
For practical reasons, modular arithmetic is introduced in the schools under
the name of \textit{ clock arithmetic} because analog clock faces are still
objects of considerable interest to bored students. Addition, subtraction,
multiplication and division around a 12 or a 24 hour daily clock, or a
calendar with 7 days in the week is a easily mastered. But how realistic
are such exercises?
\subsection{Digital computers}
Well, consider the digital computer. Stored numbers have a physical basis,
determined by their \textit{ type}, consisting of a few \textit{ words}
each composed of a fixed number of binary digits. Thus, a 32-bit computer
stores its \textit{ double integers} in two 32-bit words. Real numbers are
approximated by so-called \textit{ floating point numbers} which consist
of a 32-bit binary fraction $-1< u < 1$, called the \textit{ mantissa}, and a
perhaps 16-bit \textit{ exponent} $e$ representing the number $m2^e$.
Floating point arithmetic is quite complicated, and not discussed in this
course. But integral arithmetic is an application of modular arithmetic.
\section{Definitions and Vocabulary}
Here are is the new vocabulary needed to discuss modular arithmetic.
\begin{itemize}
\item The \textbf{modulus} is a whole number $m>1$
\item Two integers are \textbf{ congruent } if they have the same
non-negative remainder when divided by the modulus. We write this
relation in one of several ways, depending on the context:
\begin{itemize}
\item $a \equiv b \mbox{ mod}(m)$ is alway unambiguously understood.
\item $a \equiv b \ (m)$ is an abbreviation of the above for the lazy.
\item $a \equiv_m b$ is convenient when calculating
\item $a =(m)= b$ in emails as long as you say what you mean once.
\item In Python, it would be $ a\%m == b\%m $.
\end{itemize}
\item To say $c \equiv_m 0$, is equivalent to $m|c$, and to $(\exists q)(c=mq)$.
\item So $ b-a \equiv_m 0 $ is yet another way of writing $a\equiv_m b$.
\item And $(\exists t)\ b = a + tm $ another.
\end{itemize}
\section{Four-function arithmetic modulo $m$}
To say that we can add, subtract and multiply in fixed modulus can be
formalized by this propositions
\textbf{Proposition: }
\begin{eqnarray*}
\mbox{ If } a &\equiv_m& b \\
\mbox{ and } s &\equiv_m& t \\
\mbox{ then } a+s &\equiv_m& b+t \\
\mbox{ and } a-s &\equiv_m& b-t \\
\mbox{ and } as &\equiv_m& bt \\
\end{eqnarray*}
but $ a/s \equiv_m b/t $ might fail to be true even if $\neg(s \equiv_m 0)$.
As in the arithmetic of the rational numbers, one need \textit{ reciprocals},
also called \textit{ multiplicative inverses} for division.
\textbf{ Proof: }
Using the very last paraphrase of congruence above, some integer arithmetic,
especially the distributive law makes the rest of the proof a good exercise.
\subsection{Modular division}
The reason that division is not a sure thing in modular arithmetic is the
following situation when the modulus is composite, $ m = ab $. Since both
$1< a,b < m$, neither is divisible by $m$. So neither is congruent to
$0$ modulo($m$), but their product is, $ab=m\equiv_m 0 $. Such numbers
are called \textit{ zero-divisors modulo}$m$.
For example. Modulo $6$ neither $2$ nor $3$ is a multiple of $6$, but
their product is. Thus the equation $2x\equiv_6 1$ cannot have
a solution. For, if it did, multiply both sides of the congruence by
$3$ and see what happens.
Question: Show that, if $m=ab$, the assumption that $b$ has a reciprocal
mod($m$) leads to a contradiction.
On the other hand, suppose gcd$(a,m)=1$ then
\[1 = as +mt \equiv_m as \], and $a$ has the multiplicative inverse,
namely $s$, in the arithmetic modulo $m$. Since a prime is relatively
prime to every integer except $0$, every integer not divisible by a
prime modulus, has a reciprocal modulo that prime.
Algebraists summarize the above by defining structures such as
the \textit{ring of integers modulo} $m$, written $\mathbb{Z}_m$.
When the modulus is a prime $p$, the ring $\mathbb{Z}_p$ becomes
a field. Essentially, a ring is an algebraic structure with two
operations, addition and multiplication, satisfying all the usual
properties these operations have among the integers. If, in
addition, every non-zero element of ring has a reciprocal (a.k.a.
multiplicative inverse), then it is called a field. Familiar
fields are $\mathbb{Q}$ and $\mathbb{R}$.
An element of $\mathbb{Z_m}$ is an \textit{ equivalence class } modulo $m$.
This concept is no more difficult to understand than the equivalence
of the two rationals $\frac{2}{3}=\frac{400}{600}$, except that you learned
the latter back in grade school.
\section{Applications of Modular Arithmetic}
\subsection{Powers hold no terror modulo $m$}
Note how easy it is to compute $6^{82}$ modulo $7$:
\[ 6^{82} \equiv_7 (-1)^{82} = 1 \Rightarrow 6^{82} \equiv_7 1 \]
What about modulo $13$ ? \\
Step 1: Build a table of squares:
\begin{eqnarray*}
6^2=36 &\equiv_{13}& -3 \\
6^4=(6^2)^2 &\equiv_{13}& (-3)^2 = 9 \equiv -4 \\
6^8 &\equiv& 16 \equiv 3 \\
6^{16} &\equiv& 3^2 \equiv -4 \\
6^{32} &\equiv& 3 \\
6^{64} &\equiv& -4 \\
\end{eqnarray*}
Step 2: Resolve exponent in binary: \\
\begin{eqnarray*}
82 & = & 64 + 16 + 2 = 2^6 + 2^4 + 2^1 =_2 1010010 \\
6^{82} & = & 6^{64} 6^{16} 6^2 \equiv_{13} (-4)(-4)(-3)\equiv 3(-3) \equiv -9 \equiv 4 \\
\end{eqnarray*}
Comment: In the practical world the numbers $a,e,m$ for solving $a^e \equiv_m ?$
are gigantic, and require a computer. In the classroom, they are tiny, and take
a little of figuring. For your homework, I recommend Python on your computer.
Question: Just what are all the powers of $2$ modulo $13$?
\subsection{Divisibility rules for whole numbers}
We all recognize whether a decimal number is divisible by 2,5,10 immediately.
Most of us know the \textit{ Rule of 3s}, which says to add up the digits.
But only if you've studies modular arithmetic would you know why, and also
how to devise any other, such as the \textit{ Rule of 13.}
For divisibility of $a$ by $2,3,4,9,10,11$ we can use this strategy. Write the
number as a decimal $a=d_n ... d_2 d_1 d_0 $ and recall that this means
$ a = \Sigma_{i=0}^n d_i 10^i $. Since $10 \equiv_2 0$, when this polynomial
in powers of 10 is reduced modulo$2$ we are left with just the unit digit
\[ \Sigma_{i=0}^n d_i 10^i \equiv_2 d_0 \].
Question. Use this argument to determine that
$ \Sigma_{i=0}^n d_i 10^i \equiv_k d_0 $ for $k=2,5,10$.
Since $10 \equiv_3 = 1$ and $10 \equiv_9 = 1 $ we see that we can
simplify the problem by adding the digits of $a$, iterativly if
necessary, for $3$ and $9$. For example
\[ 1234321 \equiv_3 16 \equiv_3 7 \equiv_3 1\]
\[ 1234321 \equiv_9 16 \equiv_9 7 \equiv_9 7\].
is not divisible by $3$, while $123432$ is divisible by $3$. For
divisibility by $11$ you take the alternating sum of the digits:
$ d_0 - d_1 + d_2 -+d_n$.
Question. Is $1234321$ divisible by $9$? What about by $11$?
Justify your solution, don't just state it.
Already for $7$ things are more difficult. And $13$ requires
some real ingenuity. See if you can figure out a strategy by yourself
instead of being told or you looking it up.
\subsection{Solving equations}
The first equation you every saw in elementary algebra
might have looked like this: $ 3x = 7$, and you were either taught that
it had no solution because 7 is not a multiple of 3, or that its solution
is $x =\frac{7}{3}$. (Actually, if you were taught by an obedient but
uninspired teacher, you would have written $x = 2\frac{1}{7}$. This is OK if you
speak it out loud, but not in an algebra class, where it becomes
$x = \frac{2}{7}$ after "simplifying a product of fractions".)
In modular arithmetic we solve equations like $ ax \equiv_m b $ for $x$.
\textbf{ Proposition: } Given $a,b,m$, $ ax \equiv_m b $ for $x$ has
a solution if and only if $(a,m)|b$.
\textbf{ Proof: }
Suppose first that $d=\mbox{gcd}(a,m)$ divides $b$. Then $b=de$ and
a solution to $ax + my = d$ furnishes a solution
\[ a(xe) + m(ye) =de = b \]. So we have solution
\[ a(xe)\equiv_m b \].
Conversely, suppose we have the solution $ax + my = b$. Since
$d|a$ and $d|m$, we have $d|$LHS. So $d|$RHS. q.e.d.
\section{Fermat's Little Theorem (FLT)}
\textbf{Theorem} If $p$ is prime and $(a,p)=1$ then $a^{p-1}\equiv_p 1 $.
Equivalently:
\begin{enumerate}
\item If $p$ is prime and $\neg(p|a)$ then $p| a^{p-1} - 1$
\item If $p$ is prime and $gcd(a,p)=1$ then $a^p \equiv_p a $.
\item If $p$ is prime and $a\%p \ne 0 $ then $p | a^p - a $.
\end{enumerate}
\subsection{Project idea:} Why did Fermat state this proposition in
a letter to a friend?
\subsection{Motivation}
Suppose we calculate the residue module a prime of successive powers of
an integer $\{a\%p, a^2\%p, a^3\%p, ....\} $. There are only $p$ possible
numbers that appear in this infinite sequence, namely $\{0,1,2,...,p-1\}$.
Now invoke the second hypothesis. If $p$ does not divide $a$ then the
number $0$ will never appear in this sequence. And, once we've
proved the theorem, the number $1$ will appear in this squence.
Exercise: Write a Python program to investigate this sequence for a list
of 10 pairs of numbers $a,p$.
\textbf{ Proof: }
Consider the numbers $\{ a, 2a, 3a, .... ,(p-1)a \}$ as well as their
residues modulo $p$, namely $\{r_1, r_2, ...,r_{p-1}\ | \ r_j = ja\%p \}$.
Note that while in the first set there can be huge as well as negative
numbers, in the second set $ 0 < r_j < p$. Moreover, they must all be different
by the following argument.
\textbf{Lemma:} $(\forall j > i)(r_j \ne r_i)$
\textbf{Proof of lemma: } By contradiction (i.e. the negation is false),
Suppose $r_j=r_i=r \mbox{ but } j > i $.
\begin{eqnarray*}
ja &=& pq + r \\
ia &=& pq' + r \\
(j-i)a &=& p(q-q') \\
p|(j-i)& & \mbox{ since } (a,p)=1 \\
\end{eqnarray*}
The contraction is in the last line, since $j-i$ is too small to be a
multiple of $p$, right?
\textbf{ Continuation of the main proof: }
So there are exactly $p-1$ different numbers in the set $\{r_j\}$, hence
this is just a permuation of the the numbers $\{1,2,...,p-1\}$. So their
products are identical $r_1 r_2 ... r_{p-1} = (p-1)!$. We have
\begin{eqnarray*}
(a)(2a)...(p-1)a &=& a^{p-1}(p-1)! \\
(a)(2a)...(p-1)a &\equiv& r_1 r_2 ... r_{p-1} = (p-1)! \\
\therefore a^{p-1}(p-1)! &\equiv & (p-1)! \\
\therefore p&| & (a^{p-1}-1)(p-1)! \\
\therefore p&| & (a^{p-1}-1) \mbox{\ think why }\\
\therefore a^{p-1} &\equiv_p& 1\\
\end{eqnarray*}
The "think why" step answers these natural questions:
\begin{itemize}
\item What's so special about $p-1$?
\item Why shouldn't $p|a$?
\item What's great about $p$ being a prime?
\item How do I memorize this proof for the midterm?
\end{itemize}
\section{Aplication to the RSA encryption }
Next Lesson
\end{document}