Return to my Mathematics pages
Go to my home page
© Copyright 1999, Jim Loy
I have dealt with modular arithmetic in a few of my articles (Casting Out Nines, Day Of The Week Of Any Date, Primes and 6, Divisibility Tests). It is time that I defined it. Modular arithmetic deals with the remainders that we get from division. As an example, it is now 1PM; what time will it be in 129 hours? The answer is 10PM, and that was rather easy. It is 1PM, 120 hours leaves us at 1PM (5 days went by there), and 9 additional hours advances us to 10PM. We had 1+129 and got 10, and 130/24 gives us a remainder of 10. Technically, we call that arithmetic, modulo 24. And we deal with these number: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 0, 1, 2, ... As you can see, it is a loop. And we don't say that 130 is equal to 10 (as that would be confusing), we say that it is congruent to 10. The sign for congruence, here, is three horizontal lines, just as the equal sign (=) is two horizontal lines. I do not have a symbol for that in HTML, unfortunately. The clock shows us modulo 24, and 60. The calendar is modulo 7. Wednesday + 150 is Saturday, as 150 is congruent to 3 (mod 7) and Wednesday + 3 is Saturday. Anything cyclic is related to modular arithmetic.
77 is congruent to what (mod 3). The answer is 2. What about -77 in mod 3? The answer to that is 1. -77 is congruent to 1 (mod 3). We always get a positive number. And we can have fractions: pi is congruent to 0.14159... (mod 3).
Addendum:
Here is another definition, essentially from an encyclopedia:
b is congruent to c (mod a) means that (b-c) is divisible by a.
This will help us deal with negative numbers, as my first definition allowed a negative remainder (-1 is congruent to 6 (mod 7)). Computer functions give us c less than a and greater than or equal to 0. This number c does not have to be in that range, unless we are looking for a specific c. For example, 15 and 29 are congruent (mod 7), but they are both congruent to 1 (mod 7). It is sometimes OK to leave off the "(mod 7)," if the value of that modulus is perfectly clear from the context.