Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search