1 Bijections
Let n be an odd number. Let f(x) be a function from {0,1,...,n−1} to {0,1,...,n−1}. In each of these cases say whether or not f(x) is necessarily a bijection. Justify your answer (either prove f(x) is a bijection or give a counterexample).
(a) f(x)= 2x (mod n). (b) f(x)= 5x (mod n).
(c) n is prime and
(
0 if x = 0,
f(x)= x−1 (mod n) if x 6= 0.
(d) n is prime and f(x)= x2 (mod n).
2 Baby Fermat
Assume that a does have a multiplicative inverse mod m. Let us prove that its multiplicative inverse can be written as ak (mod m) for some k ≥ 0.
(a) Consider the sequence a,a2,a3,... (mod m). Prove that this sequence has repetitions.
(b) Assuming that ai ≡ aj (mod m), where i j, what can you say about ai−j (mod m)?
(c) Prove that the multiplicative inverse can be written as ak (mod m). What is k in terms of i and j?
CS 70, Fall 2018, DIS 4A 1
3 Combining Moduli
Suppose we wish to work modulo n = 40. Note that 40 = 5×8, with gcd(5,8)= 1. We will show that in many ways working modulo 40 is the same as working modulo 5 and modulo 8, in the sense that instead of writing down c (mod 40), we can just write down c (mod 5) and c (mod 8).
(a) What is 8 (mod 5) and 8 (mod 8)? Find a number a (mod 40) such that a ≡ 1 (mod 5) and a ≡ 0 (mod 8).
(b) Now find a number b (mod 40) such that b ≡ 0 (mod 5) and b ≡ 1 (mod 8).
(c) Now suppose you wish to find a number c (mod 40) such that c ≡ 2 (mod 5) and c ≡ 5 (mod 8). Find c by expressing it in terms of a and b.
(d) Repeat to find a number d (mod 40) such that d ≡ 3 (mod 5) and d ≡ 4 (mod 8).
(e) Compute c×d (mod 40). Is it true that c×d ≡ 2×3 (mod 5), and c×d ≡ 5×4 (mod 8)?
