Modular arithmetic

After some hiatus, let's return to our discussion of algebraic number theory. Check here for previous articles.

We have already talked briefly about groups and rings (here), but because ring theory is so important to the whole subject, we need to go into it a lot deeper. As preparation for that, we'll look at some of the simplest examples, which will turn out to be greatly generalized in the sequel.

The simplest example of all is probably the ring ℤ of ("rational") integers. We'll assume the properties of ℤ are well enough known as to require no further comment.

The next simplest example is a construction based on ℤ – the ring of integers "modulo" some positive integer n>1. You can read about it in a little more detail here. Of course, if you've studied any elementary number theory, you probably need no further explanation. On the other hand, if your only exposure to it has been courtesy of some writer who talks down to his readers by referring to the topic as "clock arithmetic", the chances are fair to good you could use a less condescending refresher.

In any case, the construction is so important and pervasive in more advanced ring theory and algebraic number theory that it's worth looking at from several points of view. The basic idea could hardly be much simpler. It involves a slightly generalized notion of "equality", or "equivalence" as it's more often referred to.

To begin with, pick and fix an integer n. n is usually assumed positive, though that's not strictly necessary. n, however, does need to be other than 0 or ±1, for reasons which will become obvious. We then say that any other two integers x and y at all are "equivalent modulo n" just in case the difference x-y is divisible by n. (This is why we want n≠0, since division by 0 is meaningless, and also n≠±1, since in that case we would have all integers equivalent modulo ±1. Although that case is meaningful, it isn't very interesting.)

Symbolically, we write x≡y (mod n) if x and y are equivalent modulo n. This notation is chosen to emphasize how ≡ is just a slight variation of the notion of equality. From this point of view, we are still talking about perfectly ordinary rational integers, but using a different notion of when they are "equal". All of the usual facts from elementay number theory about modular arithmetic can be developed from this point of view and the given definition.

But there are other points of view. For example, ≡ (mod n) is just a special case of what is called an "equivalence relation" in set theory. Specifically, let S be any (non-empty) set at all. A relation on a set S is, formally, a mapping from the set of ordered pairs (x,y) of elements of S to the set {0,1} of two elements. If the relation in question is denoted by R, then this function R(x,y) has the value 1 if x and y are in the relation R (which might be, for example, parent and child if S is a set of people). In this case we write xRy, which is not necessarily the same as yRx. On the other hand R(x,y)=0 just in case x and y are not in the indicated relation.

Given all that, there is a special type of relation R on a set S which is technically known as an "equivalence relation". For R to be an equivalence relation, three conditions must be satisfied. First, it must be "reflexive" – xRx for all x∈S. Second, it must be "symmetric" – xRy if and only if yRx, for all x,y. And third, it must be "transitive" – if xRy and yRz then xRz, for all x, y, z.

The interesting thing about equivalence relations is that if R is one on any set S, it is not hard to show that it causes S to be partitioned into disjoint (i. e. non-overlapping) subsets, called "equivalence classes". The classes need not in general all be the same size (regardless of whether S is finite or infinite), but every element of S is in one and only one class, possibly all by itself.

This exercise in abstraction actually has a useful point. Namely, if S=ℤ and R is ≡ (mod n), then obviously we have an equivalence relation on ℤ. Consequently, ℤ is partitioned into equivalence classes. Because of the structure of ℤ and the nature of ≡ (mod n), it turns out that all the equivalence classes are the same size – countably infinite, just like ℤ

From this new point of view, we can give the equivalence classes themselves the structure of a ring. And this ring will be finite in size, having exactly n equivalence classes. We will use the notation ℤ/nℤ for this set of equivalence classes – the reason for the notation will gradually make more sense.

Use the notation [x] for the equivalence class of x∈ℤ. To make a ring out of these equivalence classes, we need to define addition and multiplication. This is easily done: let [x]+[y]=[x+y] and [x][y]=[xy]. There is something subtle that needs to be proved, namely that these definitions are "well-defined", and they do not depend on the choice of a representative element for each equivalence class. For example, suppose [x]=[x′] and [y]=[y′], meaning, if we return to the basic definitions, that x≡x′ (mod n) and y≡y′ (mod n). Then it has to be shown that [x′+y′]=[x+y] and [x′][y′]=[xy]. (This is an easy exercise of unwinding the definitions for the reader.)

Now we can change the point of view just one more time. Let nℤ denote the set of all multiples of integers by the number n. We will redefine x≡y (mod n) from x-y is divisible by n to x-y is a member of the set nℤ. Clearly this doesn't really change anything. The equivalence relation remains the same.

So what have we accomplished? Simply this: starting from the ring ℤ we have found a way to define a new, finite ring ℤ/nℤ, consisting of equivalence classes. In the next installment of this series we will see how to generalize this construction to any "ring of integers of an algebraic number field" in place of ℤ. In the generalization we will replace nℤ with a special type of subring, called an ideal, of the ring of integers.

We will see that the theory of algebraic numbers is largely about the properties of these "ideals". For example, it is not true that any integer of an algebraic number field can be written as a unique product of "prime" numbers. Nevertheless, it is true that any ideal can be written uniquely as a product of "prime" ideals, suitably defined. For many applications in number theory, this is sufficient.

This point of view will also open up many interesting questions. For example, prime ideals in one ring of integers may actually factor into products of distinct prime ideals in the ring of integers of an extension field. And a very central question concerns the rules that govern such factorizations.

Tags: algebraic number theory, modular arithmetic, ring theory