display | more...
Let n be an integer > 1. The integers modulo n are1:
0,1,...,n-1
We can see that there are n of them. The set of all integers modulo n is denoted by Zn.

The first problem is to try to write n or -1 as one of the n items in this list. More generally, if a is an integer we want to be able to put a in the list.

The answer is as follows, given such an a we can choose a (unique) integer k such that a+kn is one of 0,1,...,n-1. Then we define a=a+kn. This makes sense because the right hand side is in our list.

Let's look at an example. n=3.

• 4=1
• 5=2
• 6=0
and so on. More generally, we can see that
• 0=...,-9,-6,-3,0,3,6,9,...
• 1=...,-8,-5,-2,1,4,7,10,...
• 2=...,-7,-4,-1,2,5,8,11,...

Ordinary integers can be added and multiplied (they form a ring). How can we do the same for the integers modulo n? Define:

a+b=a+b
a.b=ab

It turns out that these rules make Zn into a commutative ring. The identity element is 1 and the zero element is 0. This just means that 1.a=a and 0+a=a, for any a.

Let's look at n=3. So we have Z3={0,1,2} and we can see that, for example, 2.2=4=1. Thus, 2 has an inverse (itself) that is, it is a unit. Z3 is a field (every nonzero element is a unit) but this is not true in general. For example, in Z6 the element 2 does not have an inverse. In fact we have 2.3=0. Actually thse two examples are quite typical.

Proposition:

1. a is a unit in Zn iff a is coprime to n.
2. Zn is a field iff n is prime.

Proof: If a is a unit than there exists an integer b such that a.b=1. By definition there esists an integer k with ab-kn=1. If a prime divides a and n then it divides 1, so (a,n)=1. On the other hand, if (a,n)=1 then Euclid's algorithm gives us integers r,s such that 1=ar+ns. Thus 1=ar+ns=a.r and a is a unit. Thus a is not divisible by n. The second stament is clear since a ring is a field iff every nonzero element is a unit.

Zn is well adapted to studying congruences the reason being that a=b iff a is congruent to b modulo n, i.e. a-b is divisible by n. Results about congruences, such as Fermat's little theorem and Wilson's theorem are rather neatly stated this way. For example, the former says that xp=x in Zp, for a prime p.

Finally, we use some technology to give another identification of the ring of integers modulo n. Define a function f:Z-->Zn by f(a)=a. The way we defined addition and multiplication in Zn make it clear that this is a ring homomorphism. By definition it is surjective. It is clearly not injective though. The kernel is the ideal of Z consisting of all mutiples of n. This ideal is denoted by nZ. By the first isomorphism theorem we can deduce that Zn is isomorphic to the quotient ring Z/nZ.

The usual notation is to use a bar rather than an underline. Roll on MathML!

Log in or register to write something here or to contact authors.