Math 3221 Number Theory - Homework Until Test 2 Worksheet With Answers - Philipp Braun Page 7
ADVERTISEMENT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16Sections 4.1 & 4.2
page 67, 1. Prove each of the following assertions:
(a) If a
b (mod n) and m n, then a
b (mod m)
(b) If a
b (mod n) and c > 0, then ca
cb (mod cn)
(c) If a
b (mod n) and the integers a, b, n are all divisible by d > 0, then a/d
b/d (mod n/d)
Proof. (a) a
b (mod n)
n (a
b). Since m n, by Theorem 2.2 (iv) m (a
b), or
in other words a
b (mod m).
(b) a
b (mod n)
n (a
b). Thus there is an integer d such that nd = a
b. Multiply
both sides with c to get cnd = c(a
b) = ca
cb. Since c > 0 and n > 0, cn > 0, and since
cn (ca
cb), ca
cb (mod cn).
(c) a
b (mod n)
n (a
b). Therefore there is an integer c such that cn = a
b. If
a, b and n all are divisible by d, then cn/d = (a
b)/d = a/d
b/d, where cn/d, a/d, b/d
all are integers. So n/d (a/d
b/d). Since d > 0, n/d > 0 and therefore a/d
b/d (mod
n/d).
2
2
2. Give an example to show that a
b
(mod n) need not imply a
b (mod n).
2
2
Solution. Let a = 2, b = 3, n = 5. Then a
= 4, b
= 9, and 4
9 (mod 5) (because
9
4 = 5, where 5 is obviously a multiple of 5), but 2
3 (mod 5) (because 3
2 = 1, and
1 is not a multiple of 5).
3. If a
b (mod n), prove that gcd(a, n) = gcd(b, n).
Proof. a
b (mod n)
n
(a
b)
there is an integer c such that cn = a
b.
Let d be any divisor of both a and n. Then there are integers k, l such that dk = a and
dl = n, which means cdl = dk
b, or in other words b = dk
cdl = d(k
cl), so d divides
b. Especially gcd(a, n) gcd(b, n). Similarly we can show that gcd(b, n) gcd(a, n), which
forces the gcd’s to be equal.
50
65
4. (a) Find the remainders when 2
and 41
are divided by 7.
5
5
5
5
5
(b) What is the remainder when the following sum is divided by 4? 1
+ 2
+ 3
+
+ 99
+ 100
5 10
50
5
50
10
Solution. (a) 2
= 2
, and 2
32
5 (mod 7). By Theorem 4.2 (f), 2
5
2 5
10
2
50
5
(mod 7). 5
= 5
, and 5
25
4 (mod 7). Again by Theorem 4.2 (f), 2
4
(mod
5
5
2
5
50
2
7). 4
= (2
)
, and 2
5 (mod 7), as we already saw. Hence 2
5
25
4 (mod 7),
50
i.e. the remainder when dividing 2
by 7 is 4.
65
65
65
Since 41
( 1) (mod 7), 41
( 1)
(mod 7) by Theorem 4.2 (f). Since ( 1)
=
1,
65
56
41
1
6 (mod 7), so the remainder when dividing 41
by 7 is 6.
5
(b) The even numbers to the fifth power have a factor 2
and therefore are divisible by
4 (i.e. congruent 0 (mod 4)). The other numbers are alternating either congruent 1 or
congruent -1, and so are their fifth powers. Since the sum of numbers is congruent to the
5
5
5
sum of any numbers their summands are congruent to by Theorem 4.2 (d), 1
+ 2
+ 3
+
7
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education