[Modular Equations]
(a) Consider the equation ax = b mod m, where x is the unknown and a, b and m are given. Show
that this equation has either no solutions mod m, or d solutions mod m, where d = gcd(a, m); also, describe when each of these two cases holds. [HINT: Consider the (non-modular) integer equation
ax - km = b (for some integer k), and consider dividing by d.]
(b) Using your answer from the previous part, describe all the solutions mod 63 of each of the following
three equations:
(i) 4x + 28 = 2 mod 63
(ii) 7x + 50 = 35 mod 63
(iii) 7x + 50 = 36 mod 6