Description

CS 70 Discrete Mathematics and Probability Theory

1 Modular Inverses
Recall the definition of inverses from lecture: let a,m∈Z and m > 0; if x∈Z satisfies ax≡ 1 (mod m), then we say x is an inverse of a modulo m.
Now, we will investigate the existence and uniqueness of inverses.
(a) Is 3 an inverse of 5 modulo 10? (b) Is 3 an inverse of 5 modulo 14?
(c) Is each 3+14n where n∈Z an inverse of 5 modulo 14?
(d) Does 4 have inverse modulo 8?
(e) Suppose x,x0 ∈Z are both inverses of a modulo m. Is it possible that x6≡x0 (mod m)?
2 Paper GCD
Given a sheet of paper such as this one, and no rulers, describe a method to find the GCD of the width and the height of the paper. You can fold or tear the paper however you want, and ultimately you should produce a square piece whose side lengths are equal to the GCD.
3 Amaze Your Friends
possibly fear) in your friends by tricking them into thinking you can perform mental arithmetic with very large numbers.
So, what are the last digit of the following numbers?
(a) 112017
(b) 910001
(c) 3987654321