Math 3221 Number Theory - Homework Until Test 2 Worksheet With Answers - Philipp Braun Page 14
ADVERTISEMENT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16Section 4.4
1. Solve the following linear congruences:
(a) 25x
15 (mod 29).
(b) 5x
2 (mod 26).
(c) 6x
15 (mod 21).
(d) 36x
8 (mod 102).
(e) 34x
60 (mod 98).
(f) 140x
133 (mod 301).
Solution. (a) By Theorem 4.7, 25x
15 (mod 29) has a solution since gcd(25, 29) =
1 15. The solution is [18] (mod 29), since 25 18
450
15 (mod 29). The solution is
unique by Theorem 4.7.
(b) Since gcd(5, 26) = 1, 5x
2 (mod 26) has a unique solution, namely [20] (mod 26).
(c) Since gcd(6, 21) = 3 15, 6x
15 (mod 21) has three solutions. By trial-and-error we
get [6] (mod 21) as a solution, so by Theorem 4.7 the others are [13] (mod 21) and [20]
(mod 21).
(d) Since gcd(36, 102) = 6, which does not divide 8, there are no solutions.
(e) Since gcd(34, 98) = 2, 34x
60 (mod 98) has two solutions. By trial-and-error we find
[45] (mod 98) (because 34 45
1530
60 (mod 60)), so the other one is [94] (mod 98).
(f) Since gcd(140, 301) = 7 by the hint, which divides 133, there are seven congruence
classes which elements solve 140x
133 (mod 301). By trial-and-error, we find [16] (mod
301), because 140 16
2240
133 (mod 301). By Theorem 4.7, the other solutions are
[59] (mod 301), [102] (mod 301), [145] (mod 301), [188] (mod 301), [231] (mod 301), and
[274] (mod 301).
2. Using congruences, solve the following Diophantine equations below:
(a) 4x + 51y = 9.
(b) 12x + 25y = 331.
(c) 5x
53y = 17.
Solution. (a) 4x + 51y = 9
4x
9 (mod 51). The solution of this linear congruence is
9 4 15
[15] (mod 51), and with x = 15, we have y =
=
1 we have a solution of 4x+51y = 9.
51
The general solution therefore is x = 15 + 51t, y =
1
4t, where t is any integer.
(b) 12x + 25y = 331
12x
331
6 (mod 25). The solution of this linear congruence
331 12 13
is [13] (mod 25). For x = 13, we have y =
= 7, so the general solution is
25
x = 13 + 25t, y = 7
12t for any integer t.
(c) 5x
53y = 17
5x
17 (mod 53). The solution of this linear congruence is (by
17 5 14
trial-and-error) [14] (mod 53). With x = 14, we get y =
= 1, which leads to the
53
general solution x = 14 + 53t, y = 1 + 5t, where t is an arbitrary integer.
14
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education