Preview Extract

ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
Chapter 2
Congruence in Z and Modular
Arithmetic
2.1
Congruence and Congruence Classes
โ
1. (a) 25โ1 = 24 = 16 โก 1 (mod 5). (b) 47 1 = 46 = 4096 โก 1 (mod 7).
11โ1
10
(c) 3
= 3 = 59049 โก 1 (mod 11).
2. (a) Use Theorems 2.1 and 2.2: 6k + 5 โก 6.1 + 5 โก 11 โก 3 (mod 4).
(b)2r + 3s โก 2.3 + 3.(โ7) โก โ15 โก 5 (mod 10).
3. (a) Computing the checksum gives
10 ยท 3 + 9 ยท 5 + 8 ยท 4 + 7 ยท 0 + 6 ยท 9 + 5 ยท 0 + 4 ยท 5 + 3 ยท 1 + 2 ยท 8 + 1 ยท 9
= 30 + 45 + 32 + 54 + 20 + 3 + 16 + 9 = 209.
Since 209 = 11 ยท 19, we see that 209 โก 0 (mod 11), so that this could be a valid ISBN number.
(b) Computing the checksum gives
10 ยท 0 + 9 ยท 0 + 8 ยท 3 + 7 ยท 1 + 6 ยท 1 + 5 ยท 0 + 4 ยท 5 + 3 ยท 5 + 2 ยท 9 + 1 ยท 5
= 24 + 7 + 6 + 20 + 15 + 18 + 5 = 95.
Since 95 = 11 ยท 8 + 7, we see that 95 โก 7 (mod 11), so that this could not be a valid ISBN
number.
(c) Computing the checksum gives
10 ยท 0 + 9 ยท 3 + 8 ยท 8 + 7 ยท 5 + 6 ยท 4 + 5 ยท 9 + 4 ยท 5 + 3 ยท 9 + 2 ยท 6 + 1 ยท 10
= 27 + 64 + 35 + 24 + 45 + 20 + 27 + 12 + 10 = 264.
Since 264 = 11 ยท 24, we see that 264 โก 0 (mod 11), so that this could be a valid ISBN number.
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
Congruence in Z and Modular Arithmetic
12
4. (a) Computing the checksum gives
3 ยท 0 + 3 + 3 ยท 7 + 0 + 3 ยท 0 + 0 + 3 ห 3 + 5 + 3 ยท 6 + 6 + 3 ยท 9 + 1 = 90.
Since 90 = 10 ยท 9, we have 90 โก 0 (mod 10), so that this was scanned correctly.
(b) Computing the checksum gives
3 ยท 8 + 3 + 3 ยท 3 + 7 + 3 ยท 3 + 2 + 3 ห 0 + 0 + 3 ยท 0 + 6 + 3 ยท 2 + 5 = 71.
(c) Computing the checksum gives
3 ยท 0 + 4 + 3 ยท 0 + 2 + 3 ยท 9 + 3 + 3 ห 6 + 7 + 3 ยท 3 + 0 + 3 ยท 3 + 4 = 83.
Since 83 = 10 ยท 8 + 3, we have 83 โก 3 (mod 10), so that this was not scanned correctly.
5. Since 5 โก 1 (mod 4), it follows from Theorem 2.2 that 52 โก 12 (mod 4), so that (applying Theorem
1000
2.2 again) 53 โก 13 (mod 4). Continuing,
โก 11000 โก 1 (mod 4). Since 51000 โก 1
1000 we get 5
(mod 4), Theorem 2.3 tells us that 5
= [1] in Z4 .
6. Given n โ (a โ b) so that a โ b = nq for some integer q. Since k โ n it follows that k โ (a โ b) and
therefore a โก b (mod k).
7. By Corollary 2.5, a โก 0, 1, 2 or 3 (mod 4). Theorem 2.2 implies a2 โก 0, 1 (mod 4). Therefore a2
cannot be congruent to either 2 or 3 (mod 4).
8. By the division algorithm, any integer n is expressible as n = 4q + r where r โ {0, 1, 2, 3}, and n
โก r (mod 4). If r is 0 or 2 then n is even. Therefore if n is odd then n โก 1 or 3 (mod 4).
9. (a) (n โ a)2 โก n2 โ 2na + a2 โก a2 (mod n) since n โก 0 (mod n).
(b) (2n โ a)2 โก 4n2 โ 4na + a2 โก a2 (mod 4n) since 4n โก 0 (mod 4n).
10. Suppose the base ten digits of a are (cncnโ1 . . . c1co). (Compare Exercise 1.2.32). Then a =
cn10n + cnโ110nโ1 +. . . c110 + c0 โก c0 (mod 10), since 10k โก 0 (mod 10) for every k โฅ 1.
11. Since there are infinitely many primes (Exercise 1.3.25) there exists a prime p > โชa โ bโช. By
hypothesis, p โช (a โ b) so the only possibility is a โ b = 0 and a = b.
12. If p โก 0, 2 or 4 (mod 6), then p is divisible by 2. If p โก 0 or 3 (mod 6) then p is divisible by 3.
Since p is a prime > 3 these cases cannot occur, so that p โก 1 or 5 (mod 6). By Theorem 2.3 this
says that [p] = [1] or [5] in Z6.
13. Suppose r, r’ are the remainders for a and b, respectively. Theorem 2.3 and Corollary 2.5 imply: a โก b
(mod n) if and only if [a] = [b] if and only if [r] = [r’]. Then r = r’ as in the proof of Corollary
2.5(2).
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
Since 71 = 10 ยท 7 + 1, we have 71 โก 1 (mod 10), so that this was not scanned correctly.
2.2 Modular Arithmetic
13
14. (a) Here is one example: a = b = 2 and n = 4.
(b) The assertion is: if n โช ab then either n โช a or n โชb. This is true when n is prime by
Theorem 1.8.
15. Since (a, n) = 1 there exist integers u, v such that au + nv = 1, by Theorem 1.3. Therefore
au โก au + nv โก 1 (mod n), and we can choose b = u.
ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
16. Given that a โก 1 (mod n), we have a = nq + 1 for some integer q. Then (a, n) must divide a โ nq
= 1, so (a, n) = 1. One example to see that the converse is false is to use a = 2 and n = 3. Then
(a, n) = 1 but [a] โ [1].
17. Since 10 โก โ1 (mod 11), Theorem 2.2 (repeated) shows that 10n โก (โl)n (mod 11).
18. By Exercise 23 we have 125698 โก 31 โก 4 (mod 9), 23797 โก 28 โก 1 (mod 9) and 2891235306 โก 39 โก
12 โก 3 (mod 9). Since 4โ
1 โข 3 (mod 9) the conclusion follows.
19. Proof: If [a] = [b] then a โก b (mod n) so that a = b + nk for some integer k. Then (a, n) = (b, n)
using Lemma 1.7.
20. (a) One counterexample occurs when a = 0, b = 2 and n = 4.
(b) Given a2 โก b2 (mod n), we have n โช (a2 โ b2) = (a + b)(a โ b). Since n is prime, use
Theorem 1.8 to conclude that either nโช(a + b) or n โช (a โ b).Therefore, either a โก b
(mod n) or a โก โb (mod n).
21. (a) Since 10 โก 1 (mod 9), Theorem 2.2 (repeated) shows that 10n โก 1 (mod 9).
(b) (Compare Exercise 1.2.32). Express integer a in base ten notation: a = cn10n + . . . +
c110+ c0 . Then a โก cn+ cn – t + . . . c1 + c0 (mod 9), since 10k โก 1 (mod 9).
22. (a) Here is one example: a = 2, b = 0, c = 2, n = 4.
(b) We have n | ab โ ac = a(b โ c). Since (a, n) = l Theorem 1.5 implies that n โช(b โ c) and
therefore b โก c (mod n).
2.2
Modular Arithmetic
1. (a) Answered in the text.
(b)
+
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
3
3
0
1
2
โ
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
Congruence in Z and Modular Arithmetic
14
(d) +
0
1
2
3
4
5
6
7
8
9
10
11
0
0
1
2
3
4
5
6
7
8
9
10
11
1
1
2
3
4
5
6
7
8
9
10
11
0
2
2
3
4
5
6
7
8
9
10
11
0
1
3
3
4
5
6
7
8
9
10
11
0
1
2
4
4
5
6
7
8
9
10
11
0
1
2
3
5
5
6
7
8
9
10
11
0
1
2
3
4
6
6
7
8
9
10
11
0
1
2
3
4
5
7
7
8
9
10
11
0
1
2
3
4
5
6
8
8
9
10
11
0
1
2
3
4
5
6
7
9
9
10
11
0
1
2
3
4
5
6
7
8
10
10
11
0
1
2
3
4
5
6
7
8
9
11
11
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
11
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
8
9
10
11
2
0
2
4
6
8
10
0
2
4
6
8
10
3
0
3
6
9
0
3
6
9
0
3
6
9
4
0
4
8
0
4
8
0
4
8
0
4
8
5
0
5
10
3
8
1
6
11
4
9
2
7
6
0
6
0
6
0
6
0
6
0
6
0
6
7
0
7
2
9
4
11
6
1
8
3
10
5
8
0
8
4
0
8
4
0
8
4
0
8
4
9
0
9
6
3
0
9
6
3
0
9
6
3
10
0
10
8
6
4
2
0
10
8
6
4
2
11
0
11
10
9
8
7
6
5
4
3
2
1
However, the notation must be changed to correspond to the new notation. See the tables
in Example 2 to see what it must look like.
2. To solve x2 โ x = [0] in Z4 , substitute each of [0], [1], [2], and [3] in the equation to see if it is a
solution:
x x2 โ x
Is x2 โ x = [0]?
[0] [0] โ [0] โ [0] = [0] + [0] = [0]
Yes; solution.
[1] [1] โ [1] โ [1] = [1] + [1] = [2]
No.
[2] [2] โ [2] โ [2] = [0] + [2] = [2]
No.
[3] [3] โ [3] โ [3] = [1] โ [3] = [0]
Yes; solution.
3. x = 1, 3, 5 or 7 in โค0. However, the notation should be changed to use, for example,
[3] instead of 3.
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
(c) Answered in the text.
2.2 Modular Arithmetic
15
4. x = 1, 2, 3 or 4 in โค 5. However, the notation should be changed to use, for example,
[3] instead of 3.
5. x = 1, 2, 4, 5 in โค 6. However, the notation should be changed to use, for example,
[3] instead of 3.
6. To solve x2 โ [8] โ x = [0] in Z9 , substitute each of [0], [1], [2], . . . , [8] in the equation to see if it is
a solution:
ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
x
x2 โ [8] โ x
Is x2 โ [8] โ x = [0]?
[0] [0] โ [0] โ [8] โ [0] = [0] + [0] = [0]
Yes; solution.
[1] [1] โ [1] โ [8] โ [1] = [1] + [8] = [0]
Yes; solution.
[2] [2] โ [2] โ [8] โ [2] = [4] + [7] = [2]
No.
[3] [3] โ [3] โ [8] โ [3] = [0] โ [6] = [6]
No.
[4] [4] โ [4] โ [8] โ [4] = [7] โ [5] = [3]
No.
[5] [5] โ [5] โ [8] โ [5] = [7] โ [4] = [2]
No.
[6] [6] โ [6] โ [8] โ [6] = [0] โ [3] = [3]
No.
[7] [7] โ [7] โ [8] โ [7] = [4] โ [2] = [6]
No.
[8] [8] โ [8] โ [8] โ [8] = [1] โ [1] = [2]
No.
The solutions are x = [0] and x = [1].
7. To solve x3 โ x2 โ x โ [1] = [0] in Z8 , substitute each of [0], [1], [2], . . . , [7] in the equation to see if
it is a solution:
x
x3 โ x2 โ x โ [1] Is x3 โ x2 โ x โ [1] = [0]?
[0] [1]
No.
[1] [4]
No.
[2] [7]
No.
[3] [0]
No.
[4] [5]
No.
[5] [4]
No.
[6] [3]
No.
[7] [0]
Yes; solution.
The only solution is x = [7].
8. To solve x3 + x2 = [2] in Z10 , substitute each of [0], [1], . . . , [9] in the equation to see if it is a
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
Congruence in Z and Modular Arithmetic
16
x
x 3 โ x2
Is x3 โ x2 = [2]?
[0] [0]
No.
[1] [2]
Yes; solution.
[2] [2]
Yes; solution..
[3] [6]
No.
[4] [0]
No.
[5] [0]
No.
[6] [2]
Yes; solution.
[7] [2]
Yes; solution.
[8] [6]
No.
[9] [0]
No.
The solutions are x = [1], [2], [6], and [7].
9. (a) a = 3 or 5.
(b) a = 2 or 3.
(c) No such element exists in โค 6.
However, the notation should be changed to use, for example, [3] instead of 3.
10. Part 3: [a] โ [b] = [a + b] = [b + a] = [b] โ [a] since a + b = b + a in โค.
Part 7: [a] ([b] [c]) = [a] [be] = [a(bc)] = [(ab)c] = [ab] [c] = ([a] [b]) [c].
Part 8: [a] ([b] โ [c]) = [a] [b + c] = [a(b + c)] = [ab + ac] = [ab] โ [ac] = ([a] [b]) โ ([a
[c]).
Part 9: [a] [b] = [ab] = [ba] = [b] [a].
11. Every value of x satisfies these equations.
12. See Exercise 2.1.14.
13. See Exercise 2.1.22.
14. (a) x = 0 or 4 in โค 5.
(b) x = 0, 2, 3 or 5 in โค 6.
However, the notation should be changed to use, for example, [3] instead of 3.
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
solution:
2.3 The Structure of Zp (p Prime) and Zn
15. (a) (a + b)5 = a5 + b5 in โค 5.
17
(b) (a + b)3 = a3 + b3 in โค 3.
(c) (a + b)2 = a2 + b2 in โค 2.
(d) One is led to conjecture that (a + b)7 = a7 + b7 in โค 7 .
To investigate the general result for any prime exponent, use the Binomial Theorem and Exercise
1.4.13.
ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
However, the notation should be changed to use, for example, [a] instead of a .
16. (a) a = 1, 2, 3 or 4 in โค 5.
(b) a = 1 or 3 in โค 4.
(c) a = 1 or 2 in โค 3
(d) a = l or 5 in โค 6.
However, the notation should be changed to use, for example, [3] instead of 3.
2.3
The Structure of Zp (p Prime) and Zn
1. (a) 1, 2, 3, 4, 5, 6
(b) 1, 3, 5, 7
(c) 1, 2, 4, 5, 7, 8
(d) 1, 3, 7, 9
2. (a) Since 7 is prime, part (3) of Theorem 2.8 says that there are no zero divisors in Z7 .
(b) The zero divisors are 2, 4, and 6, since 2 ยท 4 = 0 and 6 ยท 4 = 0. Further computations will show
that the other elements of Z8 are not zero divisors.
(c) The zero divisors are 3 and 6, since 3 ยท 6 = 0. Further computations will show that the other
elements of Z9 are not zero divisors.
(d) The zero divisors are 2, 4, 5, 6, and 8, since 2 ยท 5 = 4 ยท 5 = 6 ยท 5 = 8 ยท 5 = 0. Further computations
will show that the other elements of Z10 are not zero divisors.
3. In Zn , it appears that every nonzero element is either a unit or a zero divisor.
4. (a) 1 solution in โค 7
(b) 2 solutions in โค 8
(c) 0 solutions in โค 9
(d) 2 solutions in โค |0.
5. We first show that ab 6= 0. If ab = 0, then since a is a unit, then aโ1 ab = 0, so that b = 0. But b is
a zero divisor, so that b 6= 0 and thus ab 6= 0. Now, since b is a zero divisor, choose c 6= 0 such that
bc = 0; then (ab)c = a(bc) = 0 shows that ab is also a zero divisor.
6. Since n is composite, write n = ab where 1 < a, b < n. Then in Zn , [a] 6= 0 and [b] 6= 0, since both
a and b are less than n, but [a][b] = [ab] = [n] = 0, so that a and b are zero divisors.
7. If ab = 0 in โค p then ab โก 0 (mod p) so that p โช ab. By Theorem 1.8 we conclude that p โช a or
p โช b. Then a โก 0 (mod p) or b โก 0 (mod p). Equivalently, a = 0 or b = 0 in โค p .
8. (a) For instance choose a even and b odd.
(b) Yes.
9. (a) Suppose a is a unit. Choose b such that ab = 0. Then since a is a unit, we have aโ1 ab =
aโ1 0 = 0, so that b = 0. Thus a is not a zero divisor, since any such b must be zero.
(b) This statement is the contrapositive of part (a), so is also true.
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
Congruence in Z and Modular Arithmetic
18
11. Since a is a unit, the equation ax = b has the solution aโ1 b, since aaโ1 b = b. Now, suppose that
ax = b and also ay = b. Then a(x โ y) = 0. Since a is not a zero divisor, and a 6= 0 since it is a
unit, it follows that x โ y = 0 so that x = y. Hence the solution is unique.
12. If x = [r] is a solution then [ar] = [b] so that ar โก b (mod n) and ar โ b = kn for some integer k.
Then d โช a and d โช n implies d โช (ar โ kn) = b.
13. Since d divides each of a, b and n there are integers a1, n1, b1. with a = da1, b = db1. and n =
dn1. By Theorem 1.3 there are integers u, v with au + nv = d so that au โก d (mod n). Therefore
a(ub1) โก b1d = b (mod n) so that x = [ub1] is one solution. Since an1 = a1dn1 = a1n โก 0 (mod n) we
see that x = [ub1 + n1t] is a solution for every integer t.
14. (a) If [ub1 + sn1] and [ub1 + tn1] are equal in โคn for some 0 โค s < t < d, then n โช (tn1 โ sn1)
= (t โ s)n1 so that d โช (t โ s) contrary to 0 < (t โ s) < d.
(b) If x = [r] is a solution then [ar] = [b] = [a โ
ub1] so that n โช a(r โ ub1) so that a(r โ ub1) =
nw for some integer w. Cancel d to obtain a1(r โ ub1) = n1w. Since (a1, n1) = 1, (Why?)
Theorem 1.5 implies n1โช(r โ ub1) so that r = ub1 + tn1 for some t. Then x = [r] = [ub1 +
tn1]. Divide t by d to get t = dq + k where 0 โค k < d. Then x = [ub1 + (dq + k)n1] = [ub1
+ kn1] because [dn1] = [n] = [0].
15. (a) 15x = 9 in Z18 if and only if 15x โก 9 (mod 18) if and only if 5x โก 3 (mod 6) if and only if x
โก 3 (mod 6) if and only if x โก 3, 9, 15 (mod 18) if and only if x = [3], [9], [15] in Z18.
(b) x = 3, 16, 29, 42 or 55 in Z65.
16. By Exercise 10, every nonzero element of Zn is a unit or a zero divisor, but not both. So the
statement we are trying to prove is equivalent to the following statement: If a 6= 0 and b are
elements of Zn and ax = b has no solutions in Zn , prove that a is not a unit. The contrapositive
of this statement, which is equivalent to the statement itself, is: If a 6= 0 and b are elements of Zn
and a is a unit, then ax = b has at least one solution in Zn . But Exercise 11 proves this statement.
17. Suppose that a and b are units. Then (ab)(bโ1 aโ1 ) = a(bbโ1 )aโ1 = aaโ1 = 1, so that ab is a unit.
18. See the Hint when 0 < 1. Otherwise, if 0 6< 1, then since 0 = 1, we must have 1 < 0 since we have
fully ordered Zn . Adding 1 to both sides repeatedly, using rule (ii), gives nโ1 < nโ2 < ยท ยท ยท < 1 < 0,
so that, by rule (i), n โ 1 < 0. Now add 1 to both sides to get 0 < 1, which is a contradiction.
ยฉ 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
ยฉ Cengage Learning. All rights reserved. No distribution allowed without express authorization.
10. No element can be both a unit and a zero divisor, by Exercise 9. Choose x 6= 0 โ Zn , and consider
the set of products {x ยท 1, x ยท 2, . . . , x ยท (n โ 1)}. This set has n โ 1 elements. If x is not a zero divisor,
then 0 is not one of those elements. So there are two possibilities: either no element is duplicated
in that list, or there is a duplicate. If there is no duplicate, then since there are n โ 1 elements and
n โ 1 possible values, one of the elements must be 1; that is, for some a โ Zn , we have x ยท a = 1.
Thus x is a unit. If there is a duplicate, say x ยท a = x ยท b, then x ยท (a โ b) = 0, so that x is a zero
divisor, which contradicts our original assumption. This shows that if x is not a zero divisor, then
it is a unit.

## Document Preview (9 of 206 Pages)

You are viewing preview pages of the document. Purchase to get full access instantly.

-37%

### Abstract Algebra : An Introduction, 3rd Edition Solution Manual

$18.99 ~~$29.99~~Save:$11.00(37%)

24/7 Live Chat

Instant Download

100% Confidential

Store

##### Lucas Clark

0 (0 Reviews)

## Best Selling

Test Bank for Hospitality Facilities Management and Design, 4th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

Chemistry: Principles And Reactions, 7th Edition Test Bank

$18.99 ~~$29.99~~Save:$11.00(37%)

2023-2024 ATI Pediatrics Proctored Exam with Answers (139 Solved Questions)

$18.99 ~~$29.99~~Save:$11.00(37%)

Solution Manual for Designing the User Interface: Strategies for Effective Human-Computer Interaction, 6th Edition

$18.99 ~~$29.99~~Save:$11.00(37%)

Data Structures and Other Objects Using C++ 4th Edition Solution Manual

$18.99 ~~$29.99~~Save:$11.00(37%)

The World Of Customer Service, 3rd Edition Test Bank

$18.99 ~~$29.99~~Save:$11.00(37%)