## Section2.2Modular Arithmetic

We have just learned modular arithmetic that wraps around at 26 based on the number of letters in the alphabet. However, there is no reason to limit ourselves to this particular mod. Throughout our tour of cryptology we will see many different applications of modular arithmetic. An example of modular arithmetic that you are already familiar with is clock arithmetic. This is really arithmetic mod 12 (or maybe 24). Thus we will now introduce a general definition of modular arithmetic. Actually, we will have three definitions! But first we will start with the intuitive idea. This is a little less precise, so we won't normally use this as a definition but it describes the concept best.

###### Definition2.2.1.Modular Arithmetic: Intuitive Idea.

Congruence mod $n$ describes wrapping around at $n$ so that:

\begin{equation*} n \equiv 0 \pmod {n} \end{equation*}
\begin{equation*} n+1 \equiv 1 \pmod {n} \end{equation*}
\begin{equation*} n+2 \equiv 2\pmod {n} \end{equation*}

And so on.

For example, $28=26+2$ so we write $28 \equiv 2 \pmod {26}\text{.}$ We read the expression $28 \equiv 2 \pmod {26}$ as “28 is congruent to 2 mod 26”. The notation for modular arithmetic includes two symbols, the congruence symbol ($\equiv$) and the mod. Both of these symbols together indicate that the equation is not an exact equality but a modular condition and the mod indicates the specific modulus we are using. It is standard practice to write the $\pmod{26}$ on the right side of the equation, but it is really a clarification for the $\equiv$ symbol. Writing terms on the left or right of the congruence symbol does not matter and we could also have written $2 \equiv 28 \pmod {26}$ with the same meaning. Since $28+26=54\text{,}$ all of the following are true:

• $\displaystyle 54 \equiv 28 \pmod {26}$
• $\displaystyle 28 \equiv 54 \pmod {26}$
• $\displaystyle 2 \equiv 54 \pmod {26}$
• $\displaystyle 54 \equiv 2 \pmod {26}$

While Definition 2.2.1 conveys the intuitive idea of what modular arithmetic is, it is not always the easiest way to see if two numbers are congruent. For example, is $454 \equiv 1234 \pmod{26}\text{?}$ We could think about how many times we would wrap around mod 26 as we increase from 454 to 1234.

\begin{equation*} 454 \equiv 454+26 \equiv 480 \pmod{26} \end{equation*}
\begin{equation*} 454 \equiv 480+26 \equiv 506 \pmod{26} \end{equation*}
\begin{equation*} 454 \equiv 506+26 \equiv 532 \pmod{26} \end{equation*}

Since every time we wrap around mod 26 is the same as adding 26, if we repeat this THIRTY times we have

\begin{equation*} 454 \equiv 454+26(30) \equiv 1234 \pmod{26} \end{equation*}

so that $454 \equiv 1234 \pmod{26}$ IS true. However, this is not always the easiest way to check this. The second definition connects modular arithmetic to division and remainders.

###### Definition2.2.2.Modular Arithmetic: Second Definition.

For integers $a\text{,}$ $b\text{,}$ and $n>0\text{,}$ we say that $a \equiv b \pmod {n}$ if $a$ and $b$ have the same remainder when dividing by $n\text{.}$

Remember that integers can be positive or negative whole numbers, but cannot include fractions or irrational numbers. We call the set of integers $\mathbb{Z}=\{\ldots,-4,-3,-2,-1,0,1,2,3,4,\ldots\}\text{.}$ Using the letter Z may seem surprising, but Z is from the German word for the integers, Zahlen

For example, 1234 divided by 26 gives $47.46153\cdots$ so that there is a quotient of 47 with a remainder of $12=1234-(47)26\text{.}$ Similarly, 454 divided by 26 gives a quotient of 17 with a remainder of 12. The remainder is the same in both cases, so $454 \equiv 1234 \pmod{26}\text{.}$ Does it always make sense to talk about quotients and remainders for integers? Yes, as long as you are not dividing by 0!

The division algorithm holds for negative $n$ as well, but we will never have a negative number for a mod, so this is sufficient for us.

Note that $r=0$ is an important special case, so we will state that as a separate definition.

###### Definition2.2.4.

For integers $a\text{,}$ $b$ we say that $a$ divides $b$ if $b=ak$ for some integer $k\text{.}$ The notation for this is $a \mid b\text{.}$

Let's do an example of clock arithmetic instead of mod 26. Is $41 \equiv 17 \pmod{12}\text{?}$ Is $41 \equiv 72 \pmod{12}\text{?}$ Applying Theorem 2.2.3 yields:

\begin{equation*} 41=12\times3+5 \end{equation*}
\begin{equation*} 17=12\times1+5 \end{equation*}
\begin{equation*} 72 =12\times6+0 \end{equation*}

Now by Definition 2.2.2, since 41 and 17 both have a remainder of 5 when divided by 12, $41 \equiv 17 \pmod{12}\text{.}$ However, 41 and 72 do not have the same remainder when divided by 12, so $41 \not\equiv 17 \pmod{12}\text{.}$

###### Example2.2.5.

Reduce the following numbers by the given mod. Reducing mod $n$ means we want to find the smallest positive number that each is congruent to mod $n\text{.}$

1. $\displaystyle 17 \pmod 9$
2. $\displaystyle 106 \pmod {13}$
3. $\displaystyle (25-9) \pmod 7$
4. $\displaystyle 12\times 18 \pmod 7$
Solution

We can do this using either Definition 2.2.1 or Definition 2.2.2. For Definition 2.2.1, we subtract off the modulus until we reach a number that is between 0 and $n\text{.}$ For Definition 2.2.2, we divide by $n$ and see what the remainder is.

1. From Definition 2.2.1, $17-9=8$ so $17 \equiv 8 \pmod 9\text{.}$
2. From Definition 2.2.2, $106=13(8)+2$ so $106 \equiv 2 \pmod {13}\text{.}$
3. From Definition 2.2.1, $(25-9)-7-7=16-14=2$ so that $(25-9) \equiv 2 \pmod 7\text{.}$
4. From Definition 2.2.2, $12\times 18=216=7(30)+6$ so that $12\times 18 \equiv 6 \pmod 7\text{.}$

There are many ways to think of modular arithmetic, but at this point in time it's best to get some examples under our belt.

From the questions in Investigation: Modular Arithmetic you should have discovered two more ways to think about modular arithmetic.

###### Definition2.2.6.Modular Arithmetic: Third Definition.

For integers $a\text{,}$ $b\text{,}$ and $n \gt 0\text{,}$ we say that $a \equiv b \pmod {n}$ if $a=b+nk$ for some integer $k\text{.}$

###### Example2.2.7.

To see Definition 2.2.6 in action, we answer the following questions: Is $70 \equiv 54 \pmod{26}?$ Is $70 \equiv 54 \pmod{8}?$

1. We need to be able to write $70=54+26k$ for some integer $k\text{.}$ If we subtract 54 from both sides, we would need $16=26k$ for an integer $k\text{.}$ But this would require that $k=\frac{16}{26}$ and this is definitely not an integer, so $70 \not\equiv 54 \pmod {26}\text{.}$
2. However, solving the equation $70=54+8k$ for $k$ gives $k=2$ which is an integer, so $70 \equiv 54 \pmod {8}\text{.}$
###### Definition2.2.8.Modular Arithmetic: Fourth Definition.

For integers $a\text{,}$ $b\text{,}$ and $n \gt 0\text{,}$ we say that $a \equiv b \pmod {n}$ if $a-b=nk$ for some integer $k\text{.}$

###### Example2.2.9.

To apply Definition 2.2.8, we determine the following: Is $138 \equiv 225 \pmod{3}\text{?}$ Is $100 \equiv 301 \pmod{22}\text{?}$

1. To check the first one, we have $138-225=-87=3(-29)\text{.}$ Since $-29$ is an integer, we have $138 \equiv 225 \pmod{3}\text{.}$
2. For the second part, $100-301=-201\text{.}$ Since 201 is not a multiple of 22, there is no integer $k$ such that $201=22k$ and thus $100 \not\equiv 301 \pmod {22}\text{.}$

We can't really have four different definitions for one idea! Unless, of course, they are all really the same. That is, we know need to show that all of these definitions are really the same. We will start by showing that definition 2 and 4 are equivalent. In order to do this, we have to show that definition 2 implies definition 4 AND definition 4 implies definition 2. This type of mathematical statements is usually written as “if and only if”.

We start by assuming that $a$ and $b$ have the same remainder when divided by $n\text{.}$ By the division algorithm we can write $a=q_1 n +r$ and $b=q_2 n +r$ for integers $q_1\text{,}$ $q_2$ and $r$ where $0 \le r \lt n\text{.}$ If we subtract the second equation from the first,

\begin{equation*} a-b=q_1 n +r-(q_2 n +r)=q_1 n - q_2 n = n(q_1-q_2). \end{equation*}

Since $q_1$ and $q_2$ are integers, $q_1-q_2$ is an integer. So we let $k=q_1-q_2$ and thus $a-b= nk$ for some integer $k\text{.}$

For the other direction, we assume that $a-b= nk$ for an integer $k\text{.}$ We want to show that the remainders are equal but we can't assume it. However, we can still apply the division algorithm to write $a=q_1 n +r_1$ and $b=q_2 n +r_2$ for integers $q_1\text{,}$ $q_2\text{,}$ $r_2$ and $r_2$ where $0 \le r_1 \lt n$ and $0 \le r_2 \lt n\text{.}$ Let's again subtract the equations to get

\begin{equation*} a-b=q_1 n +r_1-(q_2 n +r_2)=q_1 n - q_2 n +r_1-r_2= n(q_1-q_2) +r_1-r_2. \end{equation*}

By assumption $a-b= nk$ for an integer $k\text{.}$ Combining our two results about $a-b$ gives

\begin{equation*} nk= n(q_1-q_2) +r_1-r_2. \end{equation*}

Rearranging the equation gives

\begin{equation*} r_1-r_2= nk-n(q_1-q_2) = n(k-q_1+q_2). \end{equation*}

Since $q_1\text{,}$ $q_2$ and $k$ are all integers, this means $k-q_1+q_2$ is an integer. Thus, $r_1-r_2$ is an integer multiple of $n\text{.}$ Let's think about which multiple that could be. We also know $0 \le r_1 \lt n$ and $0 \le r_2 \lt n\text{.}$ We use this to think about the size of $r_1-r_2\text{.}$ Multiplying the second inequality by $-1$ gives $-n \lt -r_2 \le 0\text{.}$ Combining both inequalities gives

\begin{equation*} -n \lt r_1-r_2 \lt n. \end{equation*}

Which multiplie of $n$ lives in the range strictly greater than $-n$ and strictly less than $n\text{?}$ Only one, the zero multiple! Thus, $r_1-r_2=0$ and $r_1=r_2\text{.}$

You'll show definition 3 and 4 are equivalent in the homework. This will show definitions 2,3 and 4 are all equivalent. Definition 1 is more of an intuitive idea rather than a precise definition, so we won't show formally that it is equivalent to the others but you should think about why its true.

Now that we have a good knowledge of modular arithmetic we can return to using Sage to implement our mathematical formula for shift ciphers. Sage is based on the Python language and you have already seen several interactive Sage cells in your texbook. In this next investigation, you will start thinking about the programming aspect of using Sage. You can learn about some of the basics of Python and Sage in Appendix B.