Modular Arithmetic

00:00 In the previous lesson, I gave an overview of the course. In this lesson, I’m going to describe modular arithmetic.

00:08 Modular arithmetic is a special type of arithmetic done on a group of integers that have the property that when you reach the end of that grouping of integers, they wrap around and go back to the beginning of that group of integers.

00:22 The most common example of this is a 12-hour clock. Consider it being 2:00. You add 5 hours, and it’s now 7:00. So far, simple math. Now it’s 7:00, add 6 hours, and it’s now 1:00. That’s modulus arithmetic.

00:43 The mod 12 has been passed, so the value resets and starts at the next integer again. Mathematically, this takes the idea of 7 + 6, which is 13. Performing a mod 12 on it gives you the result of 1.

01:01 A common concept that you’ll come across when dealing with modular arithmetic is congruence. Congruence is like a lighter version of equals. Consider the following example.

01:13 This is read as “13 and 1 are congruent modulo 12.” 1 divided by 12 is 0 remainder 1. 13 divided by 12 is 1 remainder 1. The remainders are referred to as the modulus. And because the remainders are the same, 13 and 1 are congruent modulo 12.

01:36 Of course, this keeps going. Adding 12 to 13, giving you 25. Adding 12 again gives you 37, and so on. All of them end up with a remainder of 1 and therefore are congruent.

01:52 Another way to consider this is two integers are congruent modulo n if n is a whole divisor of their difference. An example might make that mathematically-sounding sentence a little easier to grasp. Back to 13 and 1 being congruent mod 12, 13 minus 1 is 12. Because 12 is a whole divisor of 12, 13 and 1 are considered congruent.

02:20 Doing it again with 25. 25 minus 1 is 24, 24 divided by 12 is 2. Once again, it’s a whole number, therefore 25 and 1 are congruent mod 12. The end result of subtracting one number from the other is a whole number divisible by the modulus.

02:40 Congruence can apply to negatives as well. Consider 2 being congruent to -3 modulus 5. Applying the rule from before, 2 minus -3 is five, and of course, 5 is a whole factor of 5.

02:58 Try it again with -8 and 7. -8 minus 7 is -15, which is a factor of 5 when you multiply it by -3. Again, whole number division results in no remainder, so these values are congruent.

03:13 You can do it with negatives on both sides as well. -3 minus -8 gives you 5. Once again, simple division gives you a whole factor of 5, so -3 and -8 are congruent mod 5.

03:29 That’s enough background. Next up, let’s see how this works inside of Python.