Section 15.2 Modular arithmetic
Now we consider a special equivalence relation on the set of integers that has applications in number theory and cryptography.
Definition 15.2.1.
Fix a nonzero integer \(a\text{.}\) We declare \(m\) and \(n\) to be congruent modulo \(\boldsymbol{a}\text{,}\) and write \(m \equiv n \;(\text{mod }a)\text{,}\) if \(a|(m-n)\text{.}\)
The idea behind this equivalence relation is that we are functionally declaring \(m\) and \(n\) “the same” if they differ by a multiple of \(a\text{.}\) In a way, we are “destroying” the information of \(a\text{.}\) Throughout even very different areas of mathematics, the word “modulo” or “mod” refers to collapsing some information in a structure.
Theorem 15.2.2.
For a fixed nonzero integer \(a\text{,}\) congruence mod \(a\) defines an equivalence relation on \(\mathbb{Z}\text{.}\)
Proof.
Equivalence relations are reflexive, symmetric, and transitive. First, fix an integer \(a\) to be our modulus.
The relation is reflexive because for all \(n \in \mathbb{Z}\text{,}\) \(n-n = 0\) which is divisible by \(a\text{.}\) Therefore, \(n \equiv n \;(\text{mod }a)\text{.}\)
The relation is symmetric. Let \(m, n \in \mathbb{Z}\) and suppose \(m \equiv n \;(\text{mod }a)\text{.}\) That means \(m - n = ak\) for some integer \(k\text{.}\) By that token, \(n-m = -ak = a(-k)\text{,}\) implying that \(n \equiv m \;(\text{mod }a)\) as well.
Finally, the relation is transitive. Let \(k\text{,}\) \(m\text{,}\) and \(n\) be integers such that \(k \equiv m \;(\text{mod }a)\) and \(m \equiv n \;(\text{mod }a)\text{.}\) That means \(k - m = ar\) for some integer \(r\text{,}\) and \(m - n = as\) for some integer \(s\text{.}\) Therefore,
which implies that \(k \equiv n \;(\text{mod }a)\text{.}\)
Thus, the relation described is an equivalence relation on \(\mathbb{Z}\text{.}\)
Example 15.2.3.
In the right context this relation is a familiar one. Suppose it is 10:00 in the morning. What time will it be 37 hours from now? Of course we subtract a full day, or 24 hours, from 37; so what time is it 13 hours from now? It will be 23:00 or 11:00 in the evening, depending on how you tell time. This addition is done modulo 24 (or 12).
Example 15.2.4.
If you have had trigonometry, consider the fact that \(\pi/2\) and \(5\pi/2\) have the same values of sine and cosine. This is because trigonometry on the unit circle is done “modulo \(2pi\)”.
Example 15.2.5.
\(17 \equiv 33 \;(\text{mod }8)\text{,}\) because \(33-17=16\) and \(8|16\text{.}\) You may also think of this as being true because the remainder of both \(17\) and \(33\) is \(1\) upon being divided by \(8\text{.}\) However, \(23 \not\equiv 49 \;(\text{mod }5)\) because \(49-23=26\text{,}\) which is not divisible by \(5\text{.}\)
The equivalence class of a given element mod \(a\) is not difficult to generate with the following observation, via example.
Example 15.2.6.
Suppose we want to know the equivalence class of \(11\) modulo \(6\text{.}\) We are looking for integers \(m\) satisfying \(6|(11-m)\text{;}\) equivalently, integers \(m\) for which there exists a \(k\) such that \(11-m=6k\text{.}\) Or, \(m=11-6k\text{.}\) Therefore, we will allow \(k\) to run through all of its options—both positive and negative—so the integers in the equivalence class of \(11\) mod \(6\) are just the integers that are \(11\) plus some multiple of \(6\text{:}\)
Another equivalence class mod 6 is
Note that there is one equivalence class per possible remainder when dividing by \(6\text{.}\) Here is the full list of equivalence classes:
Observe \([5]=[11]\text{.}\) Equivalence classes can be named after any of their members.
The smallest non-negative member of each class is the remainder of all the members of its class modulo 6.
Example 15.2.7.
Let's simplify \(-11 \;(\text{mod }4)\text{.}\) Here, “simplify” means to write as the smallest non-negative member of the correct equivalence class. In other words, find the remainder \(r\) such that \(-11 = 4q + r\text{.}\) If we take our usual approach of “remove multiples of \(4\text{,}\)” then we will arrive at \(-3\text{,}\) which is not the answer! Remember, we want the smallest non-negative answer.
So, the trick is to get as close to \(0\) as possible—in this case, \(-3\)— and then add the modulus \(4\) one more time. So, \(-3 + 4 = 1\) is the remainder when \(-11\) is divided by \(4\text{.}\) Check for yourself that this is the smallest non-negative member of \(-11\)'s equivalence class modulo \(4\text{.}\)
Finally, we will note some useful algebraic properties of this relation.
Theorem 15.2.8.
Suppose \(u \equiv v\) and \(x \equiv y\) modulo \(a\text{.}\) Then
and
Example 15.2.9.
In certain cryptography contexts it is helpful to know the remainders of large integers modulo something, but it may expensive to calculate those large integers. Instead we exploit the above theorem. Suppose we want to know the value of \((19^{12} - 27 \times 48) \;(\text{mod }9).\) First, observe that since \(27\) is divisible by \(9\text{,}\) \(27 \equiv 0\text{.}\) (It is okay to drop the “\(\text{mod } 9\)” here because it should be clear from context after the above paragraph.) Since \(0\) times anything is \(0\text{,}\) \((19^{12} - 27 \times 48) \equiv 19^{12}\text{.}\) Next, observe \(19 \equiv 1\text{.}\) Then, \(19^{12} \equiv 1^12\text{,}\) which is just \(1\text{.}\) So, \((19^{12} - 27 \times 48) \equiv 1 \;(\text{mod }9)\text{.}\) In fact, since \(1\) is the smallest nonnegative member of its equivalence class, it is the remainder we would get if we divided whatever \(19^{12}-27\times 48\) is by \(9\text{.}\)
Example 15.2.10.
Simplify \((304^4 - 28 \times 110) \;(\text{mod }3)\text{.}\)
Use the arithmetic properties of the relation:
Remember, to simplify an expression modulo \(a\) means to write it as the smallest non-negative number, called the remainder. So, \(2\) is the answer, not \(-1\text{.}\)