*Solution:*
Since 6 -1 (mod 7),
the class [6]_{7} is its own inverse.
Furthermore,

2 · 4 = 8
1 (mod 7),
and 3 · 5 = 15
1 (mod 7),

so [2]_{7} and [4]_{7} are inverses of each other,
and [3]_{7} and [5]_{7} are inverses of each other.

Next problem | Next solution | Up | Table of Contents

*Comment:*
If ab 1 (mod n),
then [a]_{n} and [b]_{n} are inverses,
as are [-a]_{n} and [-b]_{n}.

If ab -1 (mod n),
then [a]_{n} and [-b]_{n} are inverses,
as are [-a]_{n} and [b]_{n}.

It is useful to list the integers with
m ± 1 (mod n),
and look at the various ways to factor them.

*Solution:*
Note that 14, 27, and 40 are congruent to 1,
while 12, 25, and 39 are congruent to -1.

Using 14, we see that [2]_{13} and [7]_{13} are inverses.

Using 12, we see that [3]_{13} and [-4]_{13} are inverses,
as are the pairs [4]_{13} and [-3]_{13},
and [6]_{13} and [-2]_{13}.

Using 40, we see that [5]_{13} and [8]_{13} are inverses.
Finally, here is the list of inverses:

[2]_{13}^{-1} = [7]_{13};

[3]_{13}^{-1} = [9]_{13};

[4]_{13}^{-1} = [10]_{13};

[5]_{13}^{-1} = [8]_{13};

[6]_{13}^{-1} = [11]_{13};

Since [12]_{13}^{-1} = [-1]_{13}^{-1} = [-1]_{13} = [12]_{13},
this takes care of all of the nonzero elements of **Z**_{13}.

Next problem | Next solution | Up | Table of Contents

*Solution:*
We need to use the Euclidean algorithm to find
a linear combination of 91 and 501 that equals 1.
The matrix form of the Euclidean algorithm yields the following matrices.

Thus (2)(501) + (-11)(91) = 1, so
(-11)(91) 1 (mod 501),
and therefore

[91]_{501}^{-1}
= [-11]_{501}
= [490]_{501}.

Next problem | Next solution | Up | Table of Contents

*Solution:*
The inverse does not exist, since the following computation
shows that 3379 is not relatively prime to 4061.

At the next step, 31 | 651, and so gcd(4061,3379)=31.

Next problem | Next solution | Up | Table of Contents

*Comment:*
We know that **Z**_{n} has
(n) units.
They occur in pairs, since

gcd(a,n) = 1 if and only if gcd(n-a,n) = 1.
This helps to check your list.

*Solution:*
The units of **Z**_{20} are the equivalence classes represented by
1, 3, 7, 9, 11, 13, 17, and 19.
We have

[3]_{20}^{-1} = [7]_{20},

[9]_{20}^{-1} = [9]_{20},

[11]_{20}^{-1} = [11]_{20},

[13]_{20}^{-1} = [17]_{20}, and

[19]_{20}^{-1} = [19]_{20}.

The idempotent elements of **Z**_{20}
can be found by using trial and error.

They are [0]_{20}, [1]_{20}, [5]_{20},
and [16]_{20}.

If you want a more systematic approach,
you can use the hint in Exercise 1.4.13 of the text:

if n = bc, with gcd (b,c) = 1,
then any solution to the congruences

x 1 (mod b)
and x 0 (mod c) will be
idempotent modulo n.

The nilpotent elements of **Z**_{20} can be found by using
trial and error, or by using
Problem 1.4.40 (later in this section).

They are [0]_{20} and [10]_{20}.

Next problem | Next solution | Up | Table of Contents

*Solution:*
The solution is similar to that of the previous problem.
The units of **Z**_{24} are the equivalence classes
represented by 1, 5, 7, 11, 13, 17, 19, and 23.
For each of these numbers we have

x^{2} 1 (mod 24),
and so each element is its own inverse.

The idempotent elements are
[0]_{24},
[1]_{24},
[9]_{24},
[16]_{24},
and the nilpotent elements are
[0]_{24},
[6]_{24},
[12]_{24},
[18]_{24}.

Next problem | Next solution | Up | Table of Contents

*Comment:*
To show that **Z**_{17}^{×} is cyclic,
we need to find an element whose multiplicative order is 16.
The solution just uses trial and error.
It is known that if p is prime,
then **Z**_{p}^{×} is cyclic,
but there is no known algorithm for actually finding
the one element whose powers cover all of
**Z**_{p}^{×}.

*Solution:*
We begin by trying [2]. We have

[2]^{2} = [4],
[2]^{3} = [8], and
[2]^{4} = [16] = [-1].
Problem 1.4.39 (later in this section)
shows that the multiplicative order of an element
has to be a divisor of 16,
so the next possibility to check is 8. Since

[2]^{8} = [-1]^{2} = [1],
it follows that [2] has multiplicative order 8.

We next try [3]. We have

[3]^{2} = [9],
[3]^{4} = [81] = [-4], and
[3]^{8} = [16] = [-1].
The only divisor of 16 that is left to check is 16 itself,
so [3] does in fact have multiplicative order 16,
and we are done.

Next problem | Next solution | Up | Table of Contents

[8]

*Solution:*
We first compute the powers of [8]:

[8]^{2} = [-6],

[8]^{3} = [8][-6] = [-13], and

[8]^{4} = [-6]^{2} = [1],

so the multiplicative order of [8] is 4,
and the powers we have listed represent the only possible
values of [8]^{i}.

We next compute the powers of [-4]:

[-4]^{2} = [16],

[-4]^{3} = [-4][16] = [6],

[-4]^{4} = [-4][6] = [11],

[-4]^{5} = [-4][11] = [-9], and

[-4]^{6} = [-4][-9] = [1],

so the multiplicative order of [-4] is 6.

There are 24 possible products of the form [8]^{i}[-4]^{j}, for

0 i < 4 and 0
j < 6.
Are these all different? Suppose that

[8]^{i}[-4]^{j}
= [8]^{m}[-4]^{n} ,
for some
0 i < 4 ,
0 j < 6
and 0 m < 4 ,
0 n < 6.

Then [8]^{i-m} = [-4]^{n-j},
and since the only power of [8] that is equal to a power of [-4]
is [1] (as shown by our computations),
this forces i=m and n=j.

We conclude that
since there are 24 elements of the form [8]^{i} [-4]^{j},
every element in **Z**_{35} must be of this form.

Finally, ([8]^{i} [-4]^{j})^{12} = ([8]^{4})^{3i} ([-4]^{6})^{2j} = [1],
so no element of **Z**_{35} has multiplicative order 24,
showing that **Z**_{35} is not cyclic.

Next problem | Next solution | Up | Table of Contents

*Solution:*
We can factor the given expression:

[x]^{2} + [x] - [6] = ([x] + [3]) ([x] - [2]).

Then Corollary1.4.6
implies that either [x] + [3] = [0] or [x] - [2] = [0],
and so the solution is

[x] = [-3] = [8] or [x] = [2].

Next problem | Next solution | Up | Table of Contents

*Solution:*
Assume that k is the smallest positive integer
for which a^{k} 1
(mod n).
We can use the division algorithm to write

(n) = qk + r, where
0 r < k, and q in **Z**.
Since a^{k} 1 (mod n),
we know that gcd (a,n) = 1,
and so we can apply
Theorem 1.4.11,
which shows that a^{
(n)} 1 (mod n).
Thus

a^{r}
= a^{ (n) - kq}
= a^{ (n)}
(a^{k})^{-q}
1 (mod n),

so we must have r = 0 since r < k
and k is the smallest positive integer with

a^{k} 1 (mod n).

Next problem | Next solution | Up | Table of Contents

*Solution:*
First assume that each prime divisor of n is a divisor of a. If

n =
p_{1}^{a1}
p_{2}^{a2}
· · ·
p_{t}^{at}
is the prime factorization of n, then we must have

a =
p_{1}^{b1}
p_{2}^{b2}
· · ·
p_{t}^{bt} d,
where

0 bj
aj for all j.
If k is the smallest positive integer such that

k(bi) ai for all i,
then n | a^{k}, and so [a]_{n}^{k} = [0]_{k}.

Conversely, if [a]_{n} is nilpotent, with [a]_{n}^{k} = [0],
then n | a^{k}, so each prime divisor of n is a divisor of a^{k}.
But if a prime p is a divisor of a^{k},
then by
Lemma 1.2.5
it must be a divisor of a,
and this completes the proof.

Forward to Chapter 1 review | Forward to Chapter 1 review solutions | Back to §1.3 problems | Up | Table of Contents

Forward to Chapter 1 review | Forward to Chapter 1 review solutions | Back to §1.3 problems | Up | Table of Contents