Modular Arithmetic and Quotient Sets

There is more than one way of counting. The one we are most familiar with goes like this:

and so on getting to bigger and bigger numbers. The numbers are infinite of course, so with every new count we will be naming a new different number bigger than the previous one.

Another way, also familiar to us but one we don’t often pause to think about, goes like this:

I’m talking about the hours on a clock. This way of counting repeats itself, and there is only a finite set of numbers that it goes over.

If we can do arithmetic with ordinary numbers, so can we with the numbers on a clock. What is ? In ordinary arithmetic, it is , but on a clock, it is . is the remainder of when divided by . This kind of arithmetic is called modular arithmetic, and it is often associated with one of the greatest mathematicians of all time, Carl Friedrich Gauss.

If the hands of a clock now point to , after hours, where will it point? We do the procedure earlier, and get the remainder when is divided by . We will then get . It is strange to talk of multiplication when referring to a clock, but we can do multiplication also in the same way if we want to. As for subtraction, we can ask, what is o’clock minus say, hours? We don’t say “ o’clock”. Instead we say that it is o’clock. So there is a way of keeping the numbers positive: Just keep adding until we get a positive number less than . This is also similar to the remainder procedure above. Essentially we just add or subtract until we get a positive number less than or equal to . Later we will change our notation and instead choose non-negative numbers less than .

Division is too complicated to speak about for now. Instead I’ll just try to link what I said with the more formal aspects of mathematics. This set of “numbers on a clock” we will call . means to the set of integer multiples of like and so on. means that if two numbers differ by any number in the set , we should consider them equivalent. The rule that specifies which numbers are to be considered equivalent to each other is called an equivalence relation.

So o’clock is equivalent to o’clock (not using military time here by the way) since they differ by , while is equivalent to since they differ by which is a multiple of . For the purposes of notation, we write  and . Our equivalence relation in this case can be expressed by writing  for any integer .

All the numbers that are equivalent to each other form an equivalence class. We can think of  as the set of equivalence classes under the notion of equivalence that we have defined here. We can select “representatives” for every equivalence class for ease of notation; we choose, for convenience, that , and represent the respective equivalence classes which they belong to. Note that we chose instead of to represent the equivalence class which they belong to – while we’re used to saying o’clock, mathematicians will usually choose to “represent” all its other buddies that are equivalent to it.

We can think of the process of going from the set of integers  to the set of equivalence classes as being mediated by a function. A function simply assigns to every element in its domain another element from its range. So here the function assigns to every integer in an equivalence class in . The set of integers that get sent to the equivalence class of , i.e. the set of integer multiples of , is called the kernel of this function.

is an example of a so-called quotient set. The rather confusing terminology comes from the fact that we used the group operation of addition to define our equivalence relation; since group operations often use multiplicative notation, the term quotient set makes sense in that context. In this case since our set also forms a group we refer to it also as a quotient group. If we discuss it together with multiplication, i.e. in the context of its structure as a ring, we can also refer to it as a quotient ring. (See also the previous posts Groups and Rings, Fields, and Ideals).

There are many important examples of quotient sets: can be thought of as just and , reminiscent of “bits” in computer science and engineering. Alternatively, one may think of as a set of two equivalence classes; one is made up of all even numbers and the other is made up of all odd numbers. We also have , where is the real line. can be thought of as the circle; I won’t explain now why but one can have a fairly nice mental exercise trying to figure it out (or just check it out on one of the helpful references listed below).

References:

Equivalence Class on Wikipedia

Quotient Group on Wikipedia

Quotient Ring on Wikipedia

Algebra by Michael Artin

Advertisements