We’ve already seen a bit of Modular Arithmetic in the previous lesson (Number Bases and Conversion). In this lesson we will delve a little deeper and explore Modular Arithmetic further.
When dividing two integers we can break down the parts of the division equation into several components. Those components are the Dividend, Divisor, Quotient and Remainder. If expressed as a formula they look like the following:
Dividend/Divisor = Quotient and Remainder
Modular Arithmetic in Number Theory focuses on the Remainder component or what is referred to as the Modulo Operation, Modulus or Mod for short.
Dividend mod Divisor = Remainder
Example: What is 23 mod 7 ?
- 23/7 = 3 remainder 2
- Since the mod operation only cares about the remainder
- 23 mod 7 = 2
Modular Arithmetic and Clocks
What does Modular Arithmetic have to do with Clocks? A lot! In fact, one very useful way to understand Modular Arithmetic is by thinking of clocks and how we use them. A clock has the numbers 1 – 12 on its face. Once we pass 12 o’clock we start again at 1 o’clock and continue in a circular manner. Another way we tell time is with a 24-hour system commonly used by the military. In this system we have the usual hours 1 – 12, but instead of starting at hour 1 again after we pass hour 12, we count hours 13, 14, 15 and so on until 24. In this 24-hour system the 13th hour or 13 o’clock is like 1 o’clock, 14 is like 2 o’clock, 15 like 3 o’clock and so forth. Notice a pattern?
If we extend this idea past 24 hours, we can say that 25 o’clock is also like 1 o’clock or 13 o’clock because they both wrap around the clock and land on the 1 o’clock position. In this clock system we can represent where we are in relation to the numbers 1 – 12 (or 0 – 11 as illustrated). That means that 1, 13, 25, 37, 49 … fall on the same position on the clock and are thought of as the same. 2, 14, 26, 38, 50 … are also thought of as the same.
Image Source: https://mathstats.uncg.edu/
In other words, 13 = 1 + a multiple of 12. 26 = 2 + a multiple of 12. Another way to express this is by saying that 1 is the remainder when we divide 13 by 12. 2 is the remainder when we divide 26 by 12. Mathematically, we write this as 13 ≡ 1 mod 12, 26 ≡ 2 mod 12, etc… This is read as 13 is congruentHaving the difference divisible by a given modulus to 1 mod (or modulo) 12. 26 is congruent to 2 mod 12.
There are many different mods we can work in. Above, we worked in Mod-12. Whatever mod we work with, it is always helpful to think of a clock face with that many numbers. Mod-8 for example can have a clock face numbered 1 – 8 (or in a similar fashion 0 – 7, like our illustration above). Remember that when we pass our highest number, we reset to 1 again.
If we put together what we’ve learned so far, we can formulate a general concept regarding mod. Namely, if we are working in a system of Mod-N (N being a whole number), we write a ≡ b mod n if a and b result in the same remainder when you divide them by n. In other words, a ≡ b mod n if n divides a−b.
Example: What is 17 mod 5?
- We can divide 17 by 5 and whatever the remainder is, is our answer.
- 17/5 = 3 remainder 2.
- 17 mod 5 = 2
- Alternatively, we can continually subtract 5 from 17 until we are left with a number less than 5 (1, 2, 3, or 4).
- 17 – 5 – 5 – 5 = 2
Example: What is -3 mod 4?
- Negative or positive numbers, mods work the same way.
- -3 + 4 = 1
A helpful thing to remember is that if we have a mod b and we increase a by a multiple of b, we get the same result.
For example, the following are all equal to the same number.
- 3 mod 7 = 3
- (3 + 7) mod 7 = 10 mod 7 = 3
- (3 + 14) mod 7 = 17 mod 7 = 3
- (3 + 21) mod 7 = 24 mod 7 = 3
- (3 + 28) mod 7 = 31 mod 7 = 3
You may come across notation that states: a ≡ b mod c. This simply means that a is the same as b when taken mod c.
For example, 3, 10, 17, 24, and 31 are all equal to 3 when taking mod 7. See the examples above. Therefore, we can say:
- 3 ≡ 10 mod 7
- 10 ≡ 31 mod 7
- 24 ≡ 17 mod 7
- … and so on