4.3. 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\) the reduction of \(a\) modulo \(n\) or say that \(a\) reduces to \(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\))