Theorem 4.3. If ca= cb (mod n), then a= b (mod n/d), where d = gcd(c, n).

Theorem 4.3. If ca= cb (mod n), then a= b (mod n/d), where d = gcd(c, n). Proof. By hypothesis, we can write c(a - b) = ca - cb = kn
for some integer k. Knowing that gcd(c, n) = d, there exist relatively prime integers r ands satisfying c = dr, n = ds. When these values are substituted in the displayed equation and the common factor d canceled, the net result is
r(a - b) =ks
Hence, s I r(a - b) and gcd(r, s) = 1. Euclid's lemma yields s I a - b, which may be recast as a = b (mods); in other words, a = b (mod n/d).
For video lec link is below.
https://youtu.be/dopXp7SyKNo