1.2 Modular Equivalences

July 17, 2008 in Textbooks

When considering divisibility properties it is convienient to partition the set ${\Bbb N}$ into subsets— each with some “nice” property. The reader is of course familiar with the sets $E = \{ 0, 2, 4, \ldots \}$ and $O = \{1, 3, 5 \ldots \}$ of even numbers and odd numbers. Together these sets form a partition of ${\Bbb N}$ —this means that each element of $\Bbb N$ 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 $n \in E$ , then $2 \mid n$ ”). 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 $O$ 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 $a$ and $b$ 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 $a {\mathrel{\equiv_2}} b.$ This is pronounced “ $a$ is equivalent mod 2 to $b$ ” (or, as some authors prefer, as “ $a$ is equivalent to $b$ (mod two)”) $\null^*$ . It means simply that the numbers $a$ and $b$ have the same remainder when you divide them by two.

Footnote: $\null^*$ The notation is essentially that of C. F. Gauss in his masterpiece Disquisitiones Arithmeticae published in 1801. Gauss wrote in Latin and used the word modulus (small measure) for the “number-to-divide-by”.

Formally, one speaks of equivalence modulo two”, but this is usually shortened to “mod two”.

Thus, for example we have $37 {\mathrel{\equiv_2}} 2001$ , $1776 {\mathrel{\equiv_2}}0$ , and $52 \not{\mathrel{\equiv_2}} 25$ .

Suppose we were to partition $\Bbb N$ instead into three sets. Let’s call the sets $X$ , $Y$ , and $Z$ . Imagine going through the natural numbers one at a time and “counting off”:

The resulting partition of $\Bbb N$ is
$X = \{ 0, 3, 6, \ldots \} \qquad Y = \{ 1, 4, 7, \ldots \} \qquad Z = \{ 2, 5, 8, \ldots \} .$ Each of these sets can be characterized by looking at the remainders of its elements when divided by three—the elements of $X$ have remainder zero, those of $Y$ have remainder one, and those of $Z$ 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{\mathrel {\equiv_3} } b$ (“a is equivalent mod three to b”). For example, $4 {\mathrel {\equiv_3} } 7$ , $29 {\mathrel {\equiv_3} }101$ , and $6 \not{\mathrel {\equiv_3} }2$ .

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 $a {\mathrel {\equiv_n}} b,$ meaning that $a$ and $b$ have the same remainder when you divide each of them by $n$ .

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 $17 {\mathrel {\equiv_{12}} } 5.$ 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, … }
01:00 = {1, 13, 25, 37, …}
02:00 = {2, 14, 26, 38, … }
…

Modular arithmetic is sometimes even called “clock arithmetic” because of this familiar example. What modulus should we use to consider minutes rather than hours?

Readers familiar with a certain amount of geometry might recognize another application of modular arithmetic in the concept of adding angles: $270^\circ + 180^\circ = 90^\circ,$
for example, because degree measures ( ${}^\circ$ ) 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: $E + E = E \quad E + O = O \quad O + O = E \quad O + E = O$ (“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 $X$ , $Y$ , and $Z$ : for example, we could say that $Y + Z = X,$ meaning that whenever we add an element of $Y$ and an element of $Z$ , the answer will be in $X$ . $\null^*$

$\null^*$ Look at enough examples to become convinced or consider the following
Proof:
Let $y \in Y$ and $z \in Z$ .
Then there exist $n \in {\Bbb N}$ and $m \in {\Bbb N}$ such that $y = 3n + 1$ and $z = 3m + 2$ (i.e., $y$ is one more than a some multiple of 3 and $z$ is two more than some multiple of three).
We then have
$y+z = 3n+1 + 3m+2$
$=3n+3m+3$
$=3(n+m+1)$ .
This number is a multiple of three, so $y + z \in X$ .

5 Comments

vlorbik

July 17, 2008 at 3:26 pm

on the printed page it was gorgeous.
this hybrid-TeX-HTML editor is from hell.
i quit.

Reply
Myrtle Hocklemeier

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.

Reply
vlorbik

January 19, 2011 at 5:59 pm

$R({\Bbb Z}_2) = \langle {\Bbb Z}_2, \oplus_2 ,\otimes_2 \rangle$

${\Bbb Z}_2 = \{ [0]_2, [1]_2 \}$

$[0]_2 = 2{\Bbb Z} = \{\ldots -2, 0, 2, 4, \ldots \} (= \{2z\}_{z\in {\Bbb Z}})$

$[1]_2 = \{2z+1\}_{z\in {\Bbb Z}}= \{\ldots -1, 1, 3, 5, \ldots\}$

$[0]_2 \oplus [0]_2 = [0]_2$

$[0]_2 \oplus [1]_2 = [1]_2$

$[1]_2 \oplus [0]_2 = [1]_2$

$[1]_2 \oplus [1]_2 = [0]_2$

$[0]_2 \otimes [0]_2 = [0]_2$

$[0]_2 \otimes [1]_2 = [0]_2$

$[1]_2 \otimes [0]_2 = [0]_2$

$[1]_2 \otimes [1]_2 = [1]_2$
***************************************************
$R({\Bbb Z}_3) = \langle {\Bbb Z}_3, \oplus_3, \otimes_3 \rangle$

${\Bbb Z}_3 = \{ [0]_3, [1]_3, [2]_3 \}$

$[0]_3 = 3{\Bbb Z} = \{\ldots -3, 0, 3, 6, \ldots \} (= \{3z\}_{z\in {\Bbb Z}})$

$[1]_3 = \{3z+1\}_{z\in {\Bbb Z}}= \{\ldots -2, 1, 4, 7, \ldots\}$

$[2]_3 = \{3z+1\}_{z\in {\Bbb Z}}= \{\ldots -1, 2, 5, 8, \ldots\}$

$[0]_3 \oplus [0]_3 = [0]_3$

$[0]_3 \oplus [1]_3 = [1]_3$

$[0]_3 \oplus [2]_3 = [2]_3$

$[1]_3 \oplus [0]_3 = [1]_3$

$[1]_3 \oplus [1]_3 = [2]_3$

$[1]_3 \oplus [2]_3 = [0]_3$

$[2]_3 \oplus [0]_3 = [2]_3$

$[2]_3 \oplus [1]_3 = [0]_2$

$[2]_3 \oplus [2]_3 = [1]_3$

$[0]_3 \otimes [0]_3 = [0]_3$

$[0]_3 \otimes [1]_3 = [0]_3$

$[0]_3 \otimes [2]_3 = [0]_3$

$[1]_3 \otimes [0]_3 = [0]_3$

$[1]_3 \otimes [1]_3 = [1]_3$

$[1]_3 \otimes [2]_3 = [2]_3$

$[2]_3 \otimes [0]_3 = [0]_3$

$[2]_3 \otimes [1]_3 = [2]_2$

$[2]_3 \otimes [2]_3 = [1]_3$

Reply

1 cut & paste | the livingston review Pingback on Sep 22nd, 2020 at 4:12 pm
[…] 1.1: Natural Numbers (1995) much my most-read post07/17/08 Section 1.2: Modular Equivalences (1995) more from the same lecture […]
2 Vlorbik On Math Ed | the livingston review Pingback on Dec 14th, 2020 at 12:58 pm
[…] 07/16/08Section 1.1: Natural Numbers (1995) much my most-read post 07/17/08 Section 1.2: Modular Equivalences (1995) more from the same lecture […]

the livingston review