Modular arithmetic

Like many seemingly abstract mathematical concepts, the concept of modular arithmetic is rooted in some common everyday practices. Probably even now, while reading this topic, you can see the time displayed on the screen of your laptop or smartphone. You're used to the fact that in 24-hour format, three hours after 22:00 is 1:00, not 25:00. The hour is reset to zero whenever it reaches 24. 12-hour format is a bit more complicated in this regard — a minute after 12:59 pm, we see on our clock "1:00 pm". In a way, 12 plays the role of 0 in this notation.

The most obvious advantage of these resets is avoiding large numbers. We can say that modular arithmetic is a system for dealing with restricted ranges of integers. But it turns out that — when rigorously defined — it can be much more useful and lie in the heart of modern computer security algorithms.

Congruences

Definition. Let $m$ be a positive integer. We say that the integers $a$ and $b$ are congruent modulo $m$ if their difference $a − b$ is divisible by $m$. We write $a \equiv b \pmod m$. The number $m$ is called the modulus.

For instance, $$144 \equiv 24 \pmod {60}\text{,}$$because $$144 -24 \text{ is a multiple of } 60\text{.}$$More familiarly, $144$ minutes is 2 hours and 24 minutes.

Note that $a$ and $b$ can also be negative, and this fact also has parallels in everyday language. As$$50 \equiv -10 \pmod{60}\text{,}$$at 8:50 we can say "it's ten to nine".

Let's fix some modulus $m$.

Recall that every integer $a$ can be represented as:$$a = mq + r \text{ with } 0 \leq r < m \text{.}$$As $r \equiv a \pmod m$, we conclude that for every integer $a$ there is a unique integer $r$ congruent to $a$ modulo $m$ and lying in the range $\{0, 1, \ldots m − 1\}$.

We have also denoted $r$ as $a \bmod m$. Sometimes we refer to $r$ as a residue of $a$ modulo $m$.

Modulo reduction

Let's describe the simplest way to think about modular arithmetic. We do usual operations — addition, subtraction, and multiplication (we'll talk about division later), but replace all operands and all intermediate results with their residues modulo $m$ — that is, numbers from the range $\{0, 1, \ldots m − 1\}$, congruent to these operands modulo $m$. Sometimes such replacement is called reduction modulo $m$. A real-world image for the reduction is the hand of a clock, wrapping around and returning to the same place again. Look at the Shepherd Gate Clock at the entrance to the Greenwich Observatory, remarkable for using the 24-hour dial starting at zero:

You can think about addition modulo 24 as moving the short hand of this clock. Suppose it's 14:00 (that is, 2 pm) now. To add 13 to 14 modulo 24, think where the short hand will be 13 hours later. It will point to 3:00 (3 am), right?

You can write this as $14 + 13 \equiv 3 \pmod {24}$.

Using the same trick to add 30 to 14 modulo 24, we see that the hand of the clock makes one complete turn around in 24 hours and then moves ahead for another 6 hours, giving us the result 20:00 (8 pm). So, $14 + 30 \equiv 20 \pmod {24}$.

Another example will use modulus 60 and contain both addition and multiplication:

$$(46 + 21) \cdot 129 \equiv 67 \cdot 129 \equiv 7 \cdot 9 \equiv 3 \pmod{60}$$We add $46$ to $21$ to obtain $67$, then reduce $67$ and $129$ modulo $60$, getting $7$ and $9$ correspondingly. Then we multiply $7$ by $9$ and reduce the result $63$ modulo $60$.

In fact, we could as well calculate $67 \cdot 129 = 8643$, reduce this number modulo $60$ and obtain $3$. The final result doesn't depend on whether you reduced the intermediate results modulo $m$ or not. This follows from the substitution rules:

$$\text{if } a \equiv a' \pmod m \text{ and } b \equiv b' \pmod m, \\ \text{ then } a + b \equiv a' + b' \pmod m\\ \text {and } ab \equiv a'b' \pmod m\\$$

For example, these properties say that $$239^{533} \equiv 99^{533} \pmod 7,$$because $239 \equiv 99 \pmod 7$ and raising to power $533$ is a repeated multiplication. But it's much more convenient to replace $239$ not with an arbitrary number congruent to it, but with the smallest positive number with this property — with the residue of $239$ modulo $7$:

$$239 \equiv 1 \pmod 7\\ 239^{533} \equiv 1^{533} \pmod 7\\$$So, $239^{533} \equiv 1 \pmod 7$. For a very large number (try to estimate the number of digits needed to write it down!), we can easily say what remainder it gives when divided by $7$. Isn't it surprising?

Modular division

So far we discussed only modular addition and multiplication. What about the other two arithmetic operations?

Subtraction is a composition of multiplication by -1 and addition: $$a - b = a + (-1) \cdot b,$$so it has a similar property:$$\text {if }a \equiv a' \pmod m \text{ and } b \equiv b' \pmod m, \\ \text{ then } a - b \equiv a'- b ' \pmod m$$ Division is much more tricky. We cannot just apply to integers $a$ and $b$ the ordinary division and reduce the result modulo $m$, as the result won't always be an integer. So we introduce the following definition.

Definition. We say that an integer $c$ is inverse to $b$ modulo $m$, if $bc \equiv 1 \pmod m$.

Does every $b$ have an inverse modulo $m$? No, because we can rewrite $bc \equiv 1 \pmod m$ as $bc - 1 = mk$ for some $k$. So, $b$ having an inverse modulo $m$ means the existence of $c$ and $k$ such that:

$$bc + m (-k) = 1$$The left-hand side of this equality must be divisible by $d = \gcd(b, m)$, so there's no such $c$ and $k$ when $d > 1$.

On the other hand, when $d = 1$, you can find $c$ and $k$ using the extended Euclid's algorithm. Note that the algorithm won't necessarily give us $c$ from the range $\{0, 1, \ldots m − 1\}$, but we know that's not a problem — we can always replace the result with its residue modulo $m$.

Let's consider two examples. $18$ has no inverse modulo $60$, as $\gcd(18, 60) = 6$. But $19$ is relatively prime to $60$ and extended Euclid's algorithm gives us the following representation:$$1 = 19 \cdot 19 + 60 \cdot (-6),$$so, $19$ is inverse to itself modulo $60$.

So, modular division can be defined as multiplication by a modular inverse.

Equivalence classes

So far we regarded modular arithmetic as the system dealing with integers from a predefined range and replacing the integers leaving this range with their residues. But there is another possible interpretation, in which modular arithmetic deals with all the integers, but divides them into $m$ equivalence classes — that is, $m$ infinite subsets of integers, each containing only numbers congruent to one another modulo $m$. For example, the equivalence classes modulo 3 are

{..., −9, −6, −3, 0, 3, 6, 9, ...}

{..., −8, −5, −2, 1, 4, 7, 10...}

{...−7, −4, −1, 2, 5, 8, 11, ...}

When doing operations, any member of an equivalence class is substitutable for any other. This follows from the substitution rules — look at them again. In our colorful notation, $a$ and $a'$ are members of the same class and so share the same color, a similar observation is true for $b$ and $b'$. We know, for example, that 1 + 2 = 3, but the substitution rules allow us to generalize this statement and say that any "green" number plus any "blue" number gives a "red" number. We may state that "the green class plus the blue class equals the red class". Of course, usually, mathematicians don't assign colors to classes (although something like "indigo plus mulberry equals citrine would certainly sound interesting!), but refer to the classes through their representatives (arbitrary elements of the classes).

Conclusion

• Integers $a$ and $b$ are congruent modulo $m$ if their difference $a − b$ is divisible by $m$.
• For every integer $a$ there is a unique integer $r$ congruent to $a$ modulo $m$ and lying in the range $\{0, 1, \ldots m − 1\}$, known as $a$'s residue modulo $m$.
• Modular addition, multiplication, and subtraction can be viewed as corresponding ordinary operations with modulo reduction of results (that is, replacement of these results for their residues).
• Modular inverses, when they exist, can be found by Euclid's algorithm.
• Another interpretation of modular arithmetic involves equivalence classes of integers.