Handout Exercises (to be presented in class on Thursday, September 22)
Exercise 1. The linear congruence (mod m) has a solution if and only if the equation has a solution
Exercise 2. The linear congruence (mod m) has at least one solution if and only if b is a multiple of gcd(a, m).
Exercise 3. If gcd(a, m) = 1, then prove that the linear congruence (mod m) has a unique solution.
Exercise 4. If gcd(a, m) = d and d | b, then prove that the linear congruence (mod m) has exactly d solutions. (Hint: If is a solution to the linear congruence, then show that , k = 0, 1, 2, 3, …, d-1, is a solution too. What if k > d?)
a) Let be the set of all possible remainders modulo m. Which elements in have multiplicative inverses? That is, for which does there exist a solution to the equation: (mod m)? Explain. (NOTE: In the situation where a solution of (mod m) exists, it is typically denoted by .)
b) Let denote the set of elements in that have multiplicative inverses. Prove that whenever .
Exercise 6. Prove that if gcd(c, m) = 1, then (mod m) implies (mod m).