Math 312 Worksheet - University Of British Columbia -2016 Page 5
ADVERTISEMENT
1
2
3
4
5
6
7
8Math 312, Midterm
5
PROBLEM 4 (15 points)
100
(a) (8pts) Show that 7
1 (mod 1000).
3
3
Answer: Note that 1000 = 2
5
= 8 125. By the CRT is suffices
to show that
100
100
7
1 (mod 8)
and
7
1 (mod 125).
3
2
Since φ(8) = 4 and φ(5
) = 4 5
= 100 we have from Euler’s theorem
that
4
25
25
100
(7
)
1
1 (mod 8)
and
7
1 (mod 125),
as desired.
999
(b) (7pts) Find the three last decimal digits of 7
.
(Hint: 1001 = 7 11 13)
999
1000
100
10
Answer: Note that 7 7
= 7
(7
)
1 (mod 1000), where
999
1
we used (a) in the last congruence. Thus 7
7
(mod 1000). Now
1
1001 = 7 11 13 implies 7 (11 13)
1 (mod 1000) that is 7
999
11 13 = 143 (mod 1000). We conclude that 7
143 (mod 1000)
999
then 143 are the three last decimal digits of 7
.
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education