Forward to Chapter 1 review | Back to §1.3 problems | Up | Table of Contents | About this document


§ 1.4 Integers Modulo n: Solved problems

30. Find the multiplicative inverse of each nonzero element of Z7.

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







































































31. Find the multiplicative inverse of each nonzero element of Z13.

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 Z13.

Next problem | Next solution | Up | Table of Contents







































































32. Find [91]501-1, if possible (in Z501×).

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







































































33. Find [3379]4061-1, if possible (in Z4061×).

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







































































34. In Z20, find all units (list the multiplicative inverse of each); find all idempotent elements; find all nilpotent elements.

Comment: We know that Zn 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 Z20 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 Z20 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 Z20 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







































































35. In Z24 : find all units (list the multiplicative inverse of each); find all idempotent elements; find all nilpotent elements.

Solution: The solution is similar to that of the previous problem. The units of Z24 are the equivalence classes represented by 1, 5, 7, 11, 13, 17, 19, and 23. For each of these numbers we have
x2 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







































































36. Show that Z17× is cyclic.

Comment: To show that Z17× 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 Zp× is cyclic, but there is no known algorithm for actually finding the one element whose powers cover all of Zp×.

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







































































37. Show that Z35× is not cyclic but that each element has the form
[8]35i [-4]35j, for some positive integers i,j.

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 Z35 must be of this form.

Finally, ([8]i [-4]j)12 = ([8]4)3i ([-4]6)2j = [1], so no element of Z35 has multiplicative order 24, showing that Z35 is not cyclic.

Next problem | Next solution | Up | Table of Contents







































































38. Solve the equation [x]112 + [x]11 - [6]11 = [0]11.

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







































































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 ak 1 (mod n), then k | (n).

Solution: Assume that k is the smallest positive integer for which ak 1 (mod n). We can use the division algorithm to write
(n) = qk + r, where 0 r < k, and q in Z. Since ak 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
ar = a (n) - kq = a (n) (ak)-q 1 (mod n),
so we must have r = 0 since r < k and k is the smallest positive integer with
ak 1 (mod n).

Next problem | Next solution | Up | Table of Contents







































































40. Prove that [a]n is a nilpotent element of Zn if and only if each prime divisor of n is a divisor of a.

Solution: First assume that each prime divisor of n is a divisor of a. If
n = p1a1 p2a2 · · · ptat is the prime factorization of n, then we must have
a = p1b1 p2b2 · · · ptbt 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 | ak, and so [a]nk = [0]k.

Conversely, if [a]n is nilpotent, with [a]nk = [0], then n | ak, so each prime divisor of n is a divisor of ak. But if a prime p is a divisor of ak, 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