Elementary Discrete Mathematics 2

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).

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\)”.

\(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{.}\)

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.

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{.}\)

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{.}\)

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{.}\)