Math 312 Worksheet - University Of British Columbia -2016 Page 2
ADVERTISEMENT
1
2
3
4
5
6
7
82
PROBLEM 1 (10 points)
Decide if the following statements are true or false. If a statement
is true give a proof and if a statement is false give an example where
it fails.
Let a, a , b, b , c, m
Z with m > 0.
(a) (2pts) If a = da and b = db where d = (a, b) then (a , b ) = 1.
Answer: True.
We have d = ax + by for some x, y
Z; thus d = da x + db y implies
1 = a x + b y, hence (a , b ) = 1 because (a , b ) is the smallest positive
integers that can be written as a integer linear combination of a and
b .
(b) (2pts) If c = 0 and ca
cb (mod m) then a
b (mod m).
Answer: False.
For example, 6 2
6 1 (mod 3) but 2
1 (mod 3).
a
b
(c) (2pts) If a
b (mod m) then c
c
(mod m).
Answer: False.
3
6
We have 6
3 (mod 3) but 2
2
1
2
(mod 3).
(d) (2pts) If 1
a
m
1 then a is invertible modulo m.
Answer: False.
The integer a = 2 is not invertible modulo m = 4 and satisfies
1
2
3 = m
1.
(e) (2pts) If 0
a, b
m
1 and a
b (mod m) then a = b.
Answer: True.
We have a
b = mk, k
Z and
(m
1)
a
b
m
1. The
unique multiple of m in this interval is zero, thus a
b = 0, that is
a = b.
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education