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?)
Exercise 5.
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).