Math 25: Solutions To Homework # 3 Worksheet - Dartmouth College Page 3
ADVERTISEMENT
1
2
3
42
(4.1 # 26) Show that if p is prime, then the only solutions of the congruence x
x (mod p)
are those integers x such that x
0 or 1 (mod p).
2
If x
x (mod p), then x(x
1)
0 (mod p). Thus p x(x
1), so p x or p x
1.
Hence the only solutions are x
0 (mod p) or x
1 (mod p).
(4.2 # 2) Find all solutions to the following linear congruences.
(b) 6x
3 (mod 9).
Since (6, 9) = 3, there are 3 incongruent solutions. It’s easy to see that x
2 (mod 9)
is one solution. Then since 9/3 = 3, the other solutions are x
2 + 3
5 (mod 9) and
x
2 + 6
8 (mod 9).
(c) 17x
14 (mod 21)
Since (17, 21) = 1, there is a unique solution modulo 21. Using the Euclidean Algorithm
we find that 17(5) 21(4) = 1, so multiplying by 14, we have 17(70) 21(56) = 14. Therefore
the unique solution is x
70
7 (mod 21).
(d) 15x
9 (mod 25).
Since (15, 25) = 5 and 5 9, there are no solutions.
(4.2 # 10) Determine which integers a, where 1
a
14, have an inverse moduo 14, and
find the inverse of each of these integers modulo 14.
The numbers a with an inverse modulo 14 are those for which (a, 14) = 1: 1, 3, 5, 9, 11,
and 13. The inverse of each of these integers modulo 14 is also in that list, since if ab
1
(mod m), then both a and b have an inverse modulo m. So we see that 1 = 1, 3 = 5, 5 = 3,
9 = 11, 11 = 9, and 13 = 13.
(4.2 # 18) Show that if p is an odd prime and a is a positive integer not divisible by p, then
2
the congruence x
a (mod p) has either no solution or exactly two incongruenct solutions.
If the congruence has no solutions, we are done, so suppose that it has at least one
2
2
solution c. Then c
a (mod p), so also ( c)
a (mod p). If c
c (mod p), then
2
2c
0 (mod p). Since p is odd, this implies that p c. But then a
c
0 (mod p). This
is a contradiction since p a. Therefore c and
c are incongruent solutions. Now suppose b
2
2
2
2
is another solution. Then b
c
(mod p), so (b + c)(b
c)
b
c
0 (mod p). Then
either p (b + c) or p (b
c), so b
c (mod p). Therefore there are exactly two inconruent
solutions modulo p.
(4.3 # 12) If eggs are removed from a baseket 2, 3, 4, 5, and 6 at a time, there remain,
respectively, 1, 2, 3, 4, and 5 eggs. But if the eggs are removed 7 at a time, no eggs remain.
What is the least number of eggs that could have been in the basket?
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education