Math 25: Solutions To Homework # 3 Worksheet - Dartmouth College Page 4
ADVERTISEMENT
1
2
3
4We need to find the least positive integer solution to the system of congruences
x
1 (mod 2)
x
2 (mod 3)
x
3 (mod 4)
x
4 (mod 5)
x
5 (mod 6)
x
0 (mod 7).
Since the moduli are not pairwise coprime, we can’t use the Chinese Remainder Theorem.
However, we notice from the first and fourth congruences that x must end in a 9, and from
the last congruence, it must be a multiple of 7. Since 49
2 (mod 3), we try the next
number satisfying these properties, which is 119. It is easy to check that 119 satisfies every
congruence.
(3.3 # 14(b)) Use induction to show that if a
, a
, . . . , a are integers, and b is another integer
1
2
such that (a
, b) = (a
, b) =
= (a , b) = 1, then (a
a
a , b) = 1.
1
2
1
2
The base case is trivial. Suppose the statement is true for n. Now suppose that (a
, b) =
1
(a
, b) =
= (a , b) = (a
, b) = 1. By the induction hypothesis, (a
a
a , b) = 1, so
2
+1
1
2
there are integers s and t such that
a
a
a s + bt = 1.
1
2
Multiplying through by a
, we have
+1
a
a
a a
s + a
bt = a
.
1
2
+1
+1
+1
Also, since (a
, b) = 1, we have integers e and f such that a
e + bf = 1. Substituting
+1
+1
for a
, we have
+1
(a
a
a a
s + a
bt)e + bf = 1.
1
2
+1
+1
Rewriting, we have
(a
a
a a
(se) + b(a
te + f ) = 1,
1
2
+1
+1
so (a
a
a a
, b) = 1. Therefore, the statement is true for all positive integers n.
1
2
+1
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education