Introduction
What if I asked you what the remainder was when we divide 15 by 5, You would say 0. In Modular Arithmetic, we write this as 15 ≡ 0 (mod 5), or 15 is congruent to 0 modulo 5.
Definition:
a ≡ b (mod m) means the remainder when a is divided by m, is the same s when b is divided by m.
Addition Rule:
The addition rule is good when we know 2 relations, and we want to add them. It states:
Suppose a ≡ c (mod m) and b ≡ d (mod m), then a + b ≡ c + d (mod m)
Example 1
What is (1235 + 129310) (mod 5)? This question asks the remainder when (1235 + 129310) is divided by 5. Obviously, we could just add, and divide by 5 to get the remainder, or we can observe that both of the addends are 0 mod 5. Then
(1235 + 129310) ≡ 0 + 0 (mod 5). Thus the answer is 0.
Multiplication Rule
The multiplication rule is good when we know 2 relations, and we want to multiply them. It states:
Suppose a ≡ c (mod m) and b ≡ d (mod m), then a * b ≡ c * d (mod m)
Example 1:
What is (44 * 113) (mod 12)? This question asks the remainder when (44 * 113) is divided by 12. Obviously, we could just multiply, and divide by 12 to get the remainder, or we can use the multiplication rule.
(44 * 113) ≡ (8 * 5) ≡ 40 ≡ 4 (mod 12). So, our answer is 4.
Why is this useful in coding?
In coding, we often want to find remainders in order to make our code more efficient. In other words, instead of looping over millions of data points, if we know that a pattern exists within the data, we can use modular arithmetic to greatly simply our work.
Exercises:
1. Find (123 * 3129 * 23) (mod 10)
2. Find (15 + 10 + 3 + 19) (mod 2)
3. Can we take something mod 1? What would this look like? (Hint: think decimals!)