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

 

Back to Block 1 Course Assignments