### 1.2 Modular Equivalences

When considering divisibility properties it is convienient to **partition** the set into **subsets**— each with some “nice” property. The reader is of course familiar with the sets and of even numbers and odd numbers. Together these sets form a partition of —this means that each element of occurs in exactly one of the given subsets (in other words, “Every natural number is either even or odd (but not both).”).

The even numbers share the property of being divisible by two (in symbols, “If , then ”). This is exactly what it means to be even. The odd numbers obviously share the opposite property of *not* being divisible by two. Another way to say the same thing is that when any element of is divided by two, there will always be a remainder (namely 1). For that matter, we could say that the even numbers all have remainder 0. The point here is that the “even-or–oddness” (the **parity**) of a natural number can be thought of in terms of what happens when you divide by two—specifically, what *remainder* you get.

If natural numbers and have the same parity (both are even or both are odd), we could say they are “equivalent in ‘two-mode’.” The formal symbolism for this is This is pronounced “ is **equivalent mod 2** to ” (or, as some authors prefer, as “ is equivalent to (mod two)”). It means simply that the numbers and have the same remainder when you divide them by two.

Footnote: The notation is essentially that of C. F. Gauss in his masterpieceFormally, one speaks of equivalenceDisquisitiones Arithmeticaepublished in 1801. Gauss wrote in Latin and used the wordmodulus(small measure) for the “number-to-divide-by”.

*modulo*two”, but this is usually shortened to “mod two”.

Thus, for example we have , , and .

Suppose we were to partition instead into *three* sets. Let’s call the sets , , and . Imagine going through the natural numbers one at a time and “counting off”:

X Y Z

0 1 2

3 4 5

6 7 8 …

The resulting partition of is

Each of these sets can be characterized by looking at the remainders of its elements when divided by three—the elements of have remainder zero, those of have remainder one, and those of have remainder two.

So to say that two natural numbers belong to the same set of the partition is the same as saying that they have the same remainder when divided by three. The notation for this is (“a is equivalent mod three to b”). For example, , , and .

The same process we have used for the numbers (or *moduli*—the plural of modulus) two and three can of course be used for any larger natural number. The general notation is of course meaning that and have the same remainder when you divide each of them by .

All of this probably seems pretty abstract and you might very well be wondering if any of it can be used for anything. But I now claim that equivalence mod *twelve* is very much an everyday idea! Consider the following problem: “I start work at 9 o’clock and work for 8 hours. What time is it when I finish work?” Of course the answer is *not* “17 o’clock” but rather “5 o’clock”, the point here being that To make the connection with our earlier discussion more explicit, we can once again partition the natural numbers into sets:

12:00 = {0, 12, 24, 36, … }Modular arithmetic is sometimes even called “clock arithmetic” because of this familiar example. What modulus should we use to consider minutes rather than hours?

01:00 = {1, 13, 25, 37, …}

02:00 = {2, 14, 26, 38, … }

…

Readers familiar with a certain amount of geometry might recognize another application of modular arithmetic in the concept of adding angles:

for example, because degree measures () are defined using mod 360.

Notice that these examples involve the concept of *addition*. How does this connect with our earlier examples? Well, the rules for addition mod two are actually quite well known: (“Even plus even is even, …”). Any even number added to any even number gives an even answer. The point here is that whenever we have to add two numbers, we can tell which set the answer is in whenever we know which sets the original numbers are in.

The same idea can be applied for the “mod 3” sets we have called , , and : for example, we could say that meaning that whenever we add an element of and an element of , the answer will be in .

Look at enough examples to become convinced or consider the followingProof:

Let and .

Then there exist and such that and (i.e., isone morethan a some multiple of 3 and istwo morethan some multiple of three).

We then have

.

This number is a multiple of three, so .

July 17, 2008 at 3:26 pm

on the printed page it was gorgeous.

this hybrid-TeX-HTML editor is from hell.

i quit.

July 22, 2008 at 10:12 pm

I just did an exercise last night which more or less was: Let E,O be elements of a set. Show that the set is a field.

And I was told that since this isomorphically mapped to a field of mod two that they were the same group…not sure if I explained that right. In other words it amounted to the fact that the set {e,o} = {0,1} mod two.

Well, at any rate, it was fun to see this come up on your blog since I had just gone over it. It’s like learning a new word, I had never heard of it before and now it’s coming up everywhere.

January 19, 2011 at 5:59 pm

***************************************************