Mod, Modulus, Modular Arithmetic

Date: 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/