**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*).