Question

Show that if ac = bc (mod m), where a,b,cand mare integers with m > 2and d = gcd (m,c) , then a = bmodm/d .

Short answer

a=b mod m/d

Step-by-step solution

Step 1

$d=\gcd (c,m)\Rightarrow \gcd (c/d,m/d)=1$

We are given $ac\equiv bcmodm\text{, that is}c(a-b)=km$for some integer k.

Divide both sides by d. We have $\frac{c}{d}(a-b)=k\frac{m}{d}$ .

Since $\gcd (c/d,m/d)=1$, no prime factor of m / d divides c / d , and hence they should divide

Thus m/d divides (a-b) or in other words a = b mod m/d .