Math 3221 Number Theory - Homework Until Test 2 Worksheet With Answers - Philipp Braun Page 10
ADVERTISEMENT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16Section 4.3
53
47
page 73, 1. Use the binary exponentiation algorithm to compute both 19
(mod 503) and 141
(mod 1537).
53
32
4
53
32
16
32
4
4
Solution. 19
= 19
1916 19
19, so 19
19
19
130321 19
19
(19
)
44 19
32
4
32
16
2
2
19
(44)
44 19
19
3, 748, 096 44 19
(19
)
243 44 19
243
243 44 19
59049 243 44 ˙ 19
(198 243) (44 19)
48114 836
329 333
406 (mod 503)
47
32
8
4
2
47
32
8
2
2
32
8
141
= 141
141
141
141
141, so 141
141
141
(141
)
19881 141
141
141
2
32
4
2
32
2
(1437)
1437 141
141
(141
)
2, 064, 969 1437 141
141
(778)
778 1437 141
8
4
4
2
(141
)
605284 778 1437 141
(1243)
1243 778 1437 141
(1, 545, 049)
1243 778 1437
2
141
364
1243 778 1437 141
132496 1243 778 1437 141
(314 1243) (778 1437) 141
390302 1, 117, 986 141
1441 587 141
845867 141
517 141
72897 658 (mod
1537).
2. Prove the following statements:
2
(a) For any integer a, the units digit of a
is 0, 1, 4, 5, 6, or 9.
3
(b) Any one of the integers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 can occur as units digit of a
.
4
(c) For any integer a, the units digit of a
is 0, 1, 5, or 6.
(d) The units digit of a triangular number is 0, 1, 3, 5, 6, or 8.
Proof. Let a be an integer.
(a) By Division Algorithm, a is of the form 10k + r, where k is an integer and r
2
2
2
2
2
2
2
0, 1,
, 9 . a
= (10k + r)
= 10
k
+ 2 10 r + r
, and since 10 is a factor of both 10
k
2
2
and 2 10 r, a
r
(mod 10). Considering the values r can have, we get:
2
2
in case r = 0: a
0
0 (mod 10),
2
2
in case r = 1: a
1
1 (mod 10),
2
2
in case r = 2: a
2
4 (mod 10),
2
2
in case r = 3: a
3
9 (mod 10),
2
2
in case r = 4: a
4
16
6 (mod 10),
2
2
in case r = 5: a
5
25
5 (mod 10),
2
2
in case r = 6: a
6
36
6 (mod 10),
2
2
in case r = 7: a
7
49
9 (mod 10),
2
2
in case r = 8: a
8
64
4 (mod 10), and finally
2
2
2
in case r = 9: a
9
81
1 (mod 10). So we see that in each case a
is congruent to
2
either 0, 1, 4, 5, 6, or 9 (mod 10), which means that one of these is the units digit of a
.
3
3
(b) Using the same method as in (a), we have a
r
(mod 10), because by Binomial
3
Theorem the other summands of the binomial extension of (10k + r)
have a factor 10.
Considering the cases, we see that
3
3
in case r = 0: a
0
0 (mod 10),
3
3
in case r = 1: a
1
1 (mod 10),
10
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education