## 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}