Mod, Modulus, Modular ArithmeticDate: 05/14/2003 at 16:28:14 From: Nick Subject: Mod Hi, We're learning about 'mod' in math class, and I was wondering if you could explain it to me. We learned that clocks run on 'mod 12', and that mod 12 has a set of numbers {0, 1, 2, 3, ... 11}. So, 12 is congruent to 0, 13 is congruent to 1, etc. We also learned about "casting out nines," which has something to do with mod 9. I understand that in mod 12, anything that is 24 and under, you can just convert from military time, i.e., 13 is equal to 1, 14 is 2, etc. But what about mod 9? How do you convert numbers to this "mod"? What does "mod" even stand for? Date: 05/15/2003 at 09:20:38 From: Doctor Peterson Subject: Re: Mod Hi, Nick. Modular arithmetic can be presented in a couple different ways, some much more advanced than others. It sounds as if you have been introduced to it as "clock arithmetic." The connection to "military time" is tricky, because as you may have noticed, your "mod 12 clock" has a 0 at the top rather than a 12, so it doesn't really correspond exactly to a real clock. I wouldn't want to tie my understanding of mod 12 to 12- or 24-hour clocks, but some of the ideas involved are certainly related. Let's take a different view of modular arithmetic, giving you a different perspective that is a little more advanced. First, what does "mod" mean? We use it this way: 3 = 15 (mod 12) which means that 3 and 15 leave the same remainder when you divide by 12; or, equivalently, that their difference is a multiple of 12. As I discuss in the following Dr. Math archived answer, "mod" is short for "modulo", which is Latin for "with respect to the modulus ...". Here we are calling 12 the modulus, that is, the number on which we are basing our calculations. In turn, we call the whole system "modular arithmetic." What is Modulus? http://mathforum.org/library/drmath/view/54363.html So congruence (mod 12) means that two numbers differ from one another by a multiple of 12. If we took the number line and wrapped it around a circle with circumference 12 units, we would find that 3, 15, 27, and so on all land on the same spot on the circle, since they differ by 12 from one to the next; all numbers that land on the same place in the circle are called congruent, meaning that as far as the circle is concerned, they are the same. The "clock" idea comes from this representation of numbers in a circle. Now we can move one step further by thinking of this as a whole new number system, consisting of just the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} with operations defined only on these numbers. For example, 3+4 = 7 as usual, since 7 is in this set; but 10+11 = 9 rather than 21, because 21 is not in the set, and we replace it by the number congruent to 21 (mod 12) that IS in the set, namely 9. We can find this number by dividing 21 by 12 and taking the remainder. So our operation of addition amounts to adding, and then taking the remainder so as to get back into the set. For that reason, you can think of modular arithmetic as remainder arithmetic. You can think of each of the 12 numbers in our set as a name for the set consisting of all numbers whose remainder is that value. We use the remainder as the name for the set, so that 3 stands for the set {3, 15, 27, ...}, which is called the congruency class of 3. When we perform an operation like addition on two of these new numbers, we mean that if you take any number from each of the two congruency classes and add them, the sum will be in a new congruency class whose name we find by taking the remainder. That leads us into a really advanced view of modular arithmetic, which I won't dig into too deeply. The important thing is to remember that we take the remainder after any operation, or whenever we want to convert a normal number into a modular number. So to use "mod 9", you just replace 12 with 9 in everything I've said, dividing by 9 and taking the remainder, which will be between 0 and 8 inclusive. Here are a few other references that show how it can be useful: Using Mod to Find Digits in Large Numbers http://mathforum.org/library/drmath/view/55787.html Casting Out Nines and Elevens http://mathforum.org/library/drmath/view/55805.html Remainder when Dividing Large Numbers http://mathforum.org/library/drmath/view/51598.html Chinese Remainder Theorem and Modular Arithmetic http://mathforum.org/library/drmath/view/56010.html (That last one is pretty complicated, but shows more of how modular arithmetic is used to do bigger things than describe clocks.) Cut-the-Knot: Modular Arithmetic - Alexander Bogomolny http://www.cut-the-knot.org/blue/Modulo.shtml Clock (Modular) Arithmetic Pages - Susan Addington http://www.math.csusb.edu/faculty/susan/modular/modular.html If you have any further questions, feel free to write back. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/