Modular Arithmetic and Quotient Sets

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

\displaystyle 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,...

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:

\displaystyle 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3,...

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 11+2? In ordinary arithmetic, it is 13, but on a clock, it is 1. 1 is the remainder of 11+2 when divided by 12. 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 5, after 100 hours, where will it point? We do the procedure earlier, and get the remainder when 5+100=105 is divided by 12. We will then get 9. 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 5 o’clock minus say, 7 hours? We don’t say “-2 o’clock”. Instead we say that it is 10 o’clock. So there is a way of keeping the numbers positive: Just keep adding 12 until we get a positive number less than 12. This is also similar to the remainder procedure above. Essentially we just add or subtract 12 until we get a positive number less than or equal to 12. Later we will change our notation and instead choose non-negative numbers less than 12.

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 \mathbb{Z}/12\mathbb{Z}. 12\mathbb{Z} means to the set of integer multiples of 12 like ...,-36, -24, -12, 0, 12, 24,36,... and so on. \mathbb{Z}/12\mathbb{Z} means that if two numbers differ by any number in the set 12\mathbb{Z}, 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 13 o’clock is equivalent to 1 o’clock (not using military time here by the way) since they differ by 12, while 100 is equivalent to 4 since they differ by 96 which is a multiple of 12. For the purposes of notation, we write 13\sim 1 and 100\sim 4. Our equivalence relation in this case can be expressed by writing n+12\sim n for any integer n.

All the numbers that are equivalent to each other form an equivalence class. We can think of \mathbb{Z}/12\mathbb{Z} 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 \displaystyle 0,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11 represent the respective equivalence classes which they belong to. Note that we chose 0 instead of 12 to represent the equivalence class which they belong to – while we’re used to saying 12 o’clock, mathematicians will usually choose 0 to “represent” all its other buddies that are equivalent to it.

We can think of the process of going from the set of integers \mathbb{Z} to the set of equivalence classes \mathbb{Z}/12\mathbb{Z} 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 \mathbb{Z} an equivalence class in \mathbb{Z}/12\mathbb{Z}. The set of integers that get sent to the equivalence class of 0, i.e. the set of integer multiples of 12, is called the kernel of this function.

\mathbb{Z}/12\mathbb{Z} 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: \mathbb{Z}/2\mathbb{Z} can be thought of as just 0 and 1, reminiscent of “bits” in computer science and engineering. Alternatively, one may think of \mathbb{Z}/2\mathbb{Z} 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 \mathbb{R}/\mathbb{Z}, where \mathbb{R} is the real line. \mathbb{R}/\mathbb{Z} 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

14 thoughts on “Modular Arithmetic and Quotient Sets

  1. Pingback: Homotopy Theory | Theories and Theorems

  2. Pingback: Homology and Cohomology | Theories and Theorems

  3. Pingback: More on Vector Spaces and Modules | Theories and Theorems

  4. Pingback: Basics of Algebraic Geometry | Theories and Theorems

  5. Pingback: Projective Geometry | Theories and Theorems

  6. Pingback: Exact Sequences | Theories and Theorems

  7. Pingback: Algebraic Numbers | Theories and Theorems

  8. Pingback: Localization | Theories and Theorems

  9. Pingback: Divisors and the Picard Group | Theories and Theorems

  10. Pingback: Valuations and Completions | Theories and Theorems

  11. Pingback: Elliptic Curves | Theories and Theorems

  12. Pingback: The Moduli Space of Elliptic Curves | Theories and Theorems

  13. Pingback: Reduction of Elliptic Curves Modulo Primes | Theories and Theorems

  14. Pingback: Covering Spaces | Theories and Theorems

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s