# Modular Arithmetic

As we noticed in our work with the Caesar Cipher, for each key value there is at least one letter that results in a computed position value that doesn't fall between 0 and 25. We solved the problem by wrapping the alphabet around back to the letter `A`

. This wrapping around concept is the same way we add when we're talking about time on a clock. If it were 9:00am and someone asked what the time would be in 6 hours, you would answer 3 o'clock, not 15 o'clock. 3 hours before 1 o'clock would be 10 o'clock, not -2 o'clock. Likewise, if someone asked what ciphertext letter would be obtained by enciphering the plaintext letter `x`

with a key of 5, you would respond `C`

by moving 5 letters to the right down the alphabet, wrapping around once you get to `Z`

.

You've probably already realised the couting places along the alphabet is time-consuming and annoying. Much like with telling time, there's a way to compute values that doesn't involve counting. In the case of the clock, $9 + 6 = 15$, which is 3 more than 12 (the number of positions on a clock). We write this fact as $15 \equiv 3 \pmod{12}$ which is read as "15 is equivalent (or congruent) to 3 modulo 12". Similarly, the letter `x`

is encrypted as $ 23 + 5 = 28$, which is 2 more than 26 (the total number of letters in our alphabet). As such, we can write $28 \equiv 2 \pmod{26}$. Now we get the same answer numerically as we would get from counting, 2, which corresponds to the letter `C`

. For large values, we may need to wrap around more than once. For example, what time is it 25 hours after 5 o'clock? $5 + 25 = 30$, which is 6 hours past two complete turns around the clock. It would be 6 o'clock, also denoted as $30 \equiv 6 \pmod{12}$

These types of operations will be extremely important in your work in this course. We call this method of addition **modulo arithmetic**. On a clock the **modulus** is 12, while in the Casear Cipher the **modulus** is 26. Let's define this operation and set some terminology.

Modulo Arithmetic:For a positive integer $n$, two numbers $a$ and $b$ are said to be congruent modulo $n$, if their difference $a − b$ is an integer multiple of $n$. That is, if there exists an integer $k$ such that $a − b = kn$. We write this as $a \equiv b \pmod{n}$. Put another way, $a$ and $b$ are congruent modulo $n$ if there is an integer $k$ (which could be positive, negative, or zero) such that $a = b + kn$. We call $b$ thereductionof $a$ modulo $n$ or say that $a$reducesto $b$. We will use the notation MOD to indicate the reduction (for example: $28 \text{ MOD } 26 = 2$)

## Examples

- $5 \equiv 8 \pmod{3}$ because $5 - 8$ is an integer multiple of $3$ ($-3 = 3 \cdot -1$)
- $17 \equiv 5 \pmod{3}$ because $17 - 5$ is an integer multiple of $3$ ($12 = 3 \cdot 4$)
- $9 \equiv 9 \pmod{11}$ because $9 - 9$ is an integer multiple of $11$ ($0 = 11 \cdot 0$)
- $-2 \equiv 50 \pmod{26}$ because $-2 - 50$ is an integer multiple of $26$ ($-52 = 26 \cdot -2$)