Examples

Sunday, 10 March 2019

8:22 PM

Exercise. Without solving the congruences below, find the number of their
solutions, in terms of the original modulus and of a smallest modulus.

151 — 18 (mod '21)

GCD = 3 -> 3 different solutions

GCD(15,21) = 3|18 -> unique solution modulo 7

3 different solutions modulo 21

(b) 16x
10 (mocl '22)

GCD = 2

2 19

No solution

17x
20 (mod '23)

GCD = 1