Math 3221 Number Theory - Homework Until Test 2 Worksheet With Answers - Philipp Braun Page 8
ADVERTISEMENT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
165
5
+ 99
+ 100
1 + 0
1 +
1 + 0
0 (mod 4), i.e. the remainder when dividing
the sum by 4 is 0.
103
53
333
111
5. Prove that the integer 53
+ 103
is divisible by 39, and that 111
+ 333
is divisible by
7.
103
53
103
53
Proof. 53
+ 103
( 1)
+ 1
1 + 1
0 (mod 3) (by Theorem 4.2 (f)), and
103
53
103
53
103
53
53
+ 103
1
+ ( 1)
(mod 13), so both 3 and 13 divide 53
+ 103
. Since 3 and
13 are relatively prime (in fact, they are both prime numbers), the fist statement is true
by Collary 2 of Theorem 2.4.
333
111
333
111
3
37
For the second statement, note that 111
+ 333
( 1)
+ 4
1 + (4
)
37
37
1 + (64)
=
1 + 1
1 + 1
0 (mod 7).
6. For n
1, use congruence theory to establish each of the following divisibility statements:
2
5
2
(a) 7 5
+ 3 2
.
+2
2 +1
(b) 13 3
+ 4
.
5 +1
+2
(c) 27 2
+ 5
.
+2
2 +1
(d) 43 6
+ 7
.
2
3
Proof. (a) For n = 1, the statement is true since 7 49 = 25 + 24 = 25 + 3 8 = 5
+ 3 2
.
2k
5k 2
2(k+1)
Assume the statement is true for n = k. Then 5
+ 3 2
0 (mod 7). 5
+ 3
5(k+1) 2
2
2k
5
5k 2
2k
5k 2
2k
5k 2
5k 2
2
5
5
+ 2
3 2
25 5
+ 32 3 2
25(5
+ 3 2
) + 7 3 2
2k
5k 2
2k
5k 2
(mod 7). Since 5
+ 3 2
0 (mod 7), 25(5
+ 3 2
)
0 (mod 7) by Theorem
5k 2
4.2 (e). Since 7 is a factor, 7 3 2
0 (mod 7). Therefore the statement is true for
n = k + 1 by Theorem 4.2 (d).
3
3
(b) For n = 1, we have 13
91 = 27 + 64 = 3
+ 4
, which is true since 13 7 = 91.
(k+1)+2
2(k+1)+1
k+2
2
2k+1
Assume the statement is true for n = k. Then 3
+ 4
3 3
+ 4
4
k+2
2k+1
2k+1
k+2
2k+1
3(3
+ 4
) + 13 4
(mod 13). By induction assumption, 3
+ 4
0 (mod
k+2
2k+1
2k+1
13), so 3(3
+ 4
)
0 (mod 13) by Theorem 4.2(e). Since 13 is a factor of 13 4
,
2k+1
13 4
0 (mod 13). By Theorem 4.2 (d), the statement is true for n = k + 1.
6
3
(c) For n = 1, it is stated that 27
189 = 64 + 125 = 2
+ 5
, which is true since
5(k+1)+1
(k+1)+2
27 7 = 189. Assume the statement is true for n = k. Then 2
+ 5
5
5k+1
k+2
5k+1
k+2
5k+1
k+2
5k+1
2
2
+ 5 5
32 2
+ 5 5
5(2
+ 5
) + 27 2
(mod 27). By
assumption and since 27 is a factor of the second summand, for the same reasons as in
5k+1
k+2
5k+1
parts (a) and (b), 5(2
+ 5
) + 27 2
0 (mod 27), hence the statement is true
for n = k + 1.
3
3
(d) Since 43
559 = 216 + 343 = 6
+ 7
because 43 13 = 559, the statement is true
for n = 1. Assume the statement is true for n = k. Similar to parts (a), (b) and (c),
(k+1)+2
2(k+1)+1
k+2
2
2k+1
k+2
2k+1
k+2
2k+1
2k+1
6
+7
6 6
+7
7
6 6
+49 7
6( 6
+7
)+43 7
0 + 0
0 (mod 43), thus the statement is true for n = k + 1.
8
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education