Forward to §2.1 | Back to §1.3 | Up | Table of Contents | About this document

**Definition 1.4.1.**
Let a and n > 0 be integers.
The set of all integers which have the same remainder as a
when divided by n is called the
**congruence class**
of a modulo n, and is denoted by [a]_{n}, where

[a]_{n} =
{ x in **Z** |
x a (mod n) }.

**Proposition 1.4.2.**
Let n be a positive integer, and let a,b be any integers.
Then the addition and multiplication of congruence classes
given below are well-defined :

[a]_{n} + [b]_{n} = [a+b]_{n}
and
[a]_{n}[b]_{n} = [ab]_{n}.

**Definition 1.4.3.**
If [a]_{n} belongs to **Z**_{n},
and [a]_{n}[b]_{n} = [0]_{n}
for some nonzero congruence class [b]_{n},
then [a]_{n} is called a
**divisor of zero**,
modulo n.

**Definition 1.4.4.**
If [a]_{n} belongs to **Z**_{n}, and
[a]_{n}[b]_{n} = [1]_{n},
for some congruence class [b]_{n}, then
[b]_{n} is called a
** multiplicative inverse **
of [a]_{n} and is denoted by
[a]_{n}^{-1}.

In this case, we say that
[a]_{n} and [b]_{n} are
**invertible**
elements of
**Z**_{n}, or
**units**
of **Z**_{n}.

**Proposition 1.4.5.**
Let n be a positive integer.

**(a)**The congruence class [a]_{n}has a multiplicative inverse in**Z**_{n}if and only if (a,n)=1.**(b)**A nonzero element of**Z**_{n}either has a multiplicative inverse or is a divisor of zero.

**Corollary 1.4.6.**
The following conditions on the modulus n > 0 are equivalent :

**(1)**The number n is prime.**(2)****Z**_{n}has no divisors of zero, except [0]_{n}.**(3)**Every nonzero element of**Z**_{n}has a multiplicative inverse.

**Definition 1.4.7.**
Let n be a positive integer.
The number of positive integers less than or equal to n which
are relatively prime to n will be denoted by
(n).
This function is called
**Euler's phi-function**,
or the
**totient function**.

**Proposition 1.4.8.**
If the prime factorization of n is
n =
p_{1}^{m1}
p_{2}^{m2}
** · · · **
p_{n}^{mn} ,
then

(n)
= n(1-1/p_{1})(1-1/p_{2})
** · · · **
(1-1/p_{k}).

**Definition 1.4.9.**
The set of units of **Z**_{n},
the congruence classes [a]_{n},
such that (a,n)=1, will be denoted by

**Z**_{n}^{×}.

**Proposition 1.4.10.**
The set **Z**_{n}^{×} of units of
**Z**_{n} is closed under multiplication.

The following theorem shows that raising any congruence class in
**Z**_{n}^{×}
to the power (n)
yields the congruence class of 1.
It is possible to give a purely number theoretic proof at this point,
but in Example
3.2.12
there is a more elegant proof using elementary group theory.

**Theorem 1.4.11. [Euler] **
If (a,n) = 1, then
a^{ (n)}
1 (mod n).

**Corollary 1.4.12. [Fermat]**
If p is prime, then
a^{p} a(mod p),
for any integer a.

ax b (mod n)

can be viewed as an equation in
[a]_{n} [x]_{n} = [b]_{n} .

ax b (mod n)

can get you into trouble unless gcd (a,n) = 1. Instead of thinking in terms of division, it is probably better to think of multiplying both sides of the equation
[a]_{n} [x]_{n} = [b]_{n}

It is well worth your time to learn about the sets
**Z**_{n} and **Z**_{n}^{×}.
They will provide an important source of examples in Chapter 3,
when we begin studying groups.

The exercises for Section1.4 of the text contain several definitions
for elements of **Z**_{n}.
If gcd (a,n) = 1,
then the smallest positive integer k such that
[a]^{k} = [1]
is called the **multiplicative order** of [a] in
**Z**_{n}^{×}.
The set **Z**_{n}^{×} is said to be **cyclic**
if it contains an element of multiplicative order
(n).
This is equivalent to saying that
**Z**_{n}^{×}
is cyclic if it has an element [a]
such that each element of
**Z**_{n}^{×}
is equal to some power of [a].
Finally, the congruence class [a] is said to be
**idempotent** if [a]^{2} = [a],
and **nilpotent** if [a]^{k} = [0] for some k.

**30.**
Find the multiplicative inverse
of each nonzero element of **Z**_{7}.
*Solution*

**31.**
Find the multiplicative inverse of each nonzero element of
**Z**_{13}.
*Solution*

**32.**
Find [91]_{501}^{-1}, if possible
(in **Z**_{501}^{×}).
*Solution*

**33.**
Find [3379]_{4061}^{-1},
if possible (in **Z**_{4061}^{×}).
*Solution*

**34.**
In **Z**_{20} :
find all units (list the multiplicative inverse of each);
find all idempotent elements;
find all nilpotent elements.
*Solution*

**35.**
In **Z**_{24} :
find all units (list the multiplicative inverse of each);
find all idempotent elements;
find all nilpotent elements.
*Solution*

**36.**
Show that **Z**_{17}^{×} is cyclic.
*Solution*

**37.**
Show that **Z**_{35}^{×} is not cyclic
but that each element has the form

[8]_{35}^{i} [-4]_{35}^{j},
for some positive integers i,j.
*Solution*

**38.**
Solve the equation
[x]_{11}^{2} + [x]_{11} - [6]_{11}
= [0]_{11}.
*Solution*

**39.**
Let n be a positive integer, and let a in **Z** with gcd (a,n) = 1.
Prove that if k is the smallest positive integer for which
a^{k} 1 (mod n),
then k | (n).
*Solution*

**40.**
Prove that [a]_{n} is a
nilpotent element
of **Z**_{n} if and only if
each prime divisor of n is a divisor of a.
*Solution*

Solutions to the problems | Forward to §2.1 | Back to §1.3 | Up | Table of Contents