CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Party Tricks
You are at a party celebrating your completion of the CS 70 midterm. Show off your modular arithmetic skills and impress your friends by quickly figuring out the last digit(s) of each of the following numbers:
(a) Find the last digit of 113142. (b) Find the last digit of 99999.
2 Modular Potpourri
(a) Evaluate 496 (mod 5).
(b) Prove or Disprove: There exists some x ∈ Z such that x ≡ 3 (mod 16) and x ≡ 4 (mod 6).
(c) Prove or Disprove: 2x ≡ 4 (mod 12) ⇐⇒ x ≡ 2 (mod 12).
CS 70, Fall 2021, DIS 3B 1
3 Fibonacci GCD
The Fibonacci sequence is given by Fn = Fn−1 + Fn−2, where F0 = 0 and F1 = 1. Prove that, for all n ≥ 1, gcd(Fn,Fn−1) = 1.
4 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, x′ ∈ Z are both inverses of a modulo m. Is it possible that x ̸≡ x′ (mod m)?
CS 70, Fall 2021, DIS 3B 2