Let
n be an integer > 1. The
integers
modulo n
are
1:
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.
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:
-
a is a unit in Zn iff a
is coprime to n.
-
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!