Congruences, elementary number theory

Question

If $gcd(c,m)=1$ and if $ca≡cb \space (mod \space m)$ for some $a$ and $b$, argue that $a≡b \space (mod \space m)$. Note that this claim says that there are situations where we can "cancel" $c \space modulo\space m$.

Answer 1

Hint $\ $ Put $\rm\:d = a\!-\!b\ $ in: $\ $ if $\rm\ gcd(m,c)=1\:$ then $\rm\: m\:|\:c\,d\:\Rightarrow\: m\:|\:d\ $ (Euclid's Lemma)

Alternatively, congruentially, an element $\rm\:c\:$ coprime to the modulus is a unit (invertible) mod $\rm\,m\,$ by Bezout's identity, so it can be cancelled from equations (congruences), i.e.

$$\rm (c,m)=1\ \Rightarrow\ c^{-1}\ exists,\ thus\ \ c^{-1}\ times\ \ ca\equiv cb\ \ yields \ \ a\equiv b$$

Generally, in any ring, scaling an equation by a unit yields an equivalent equation, because, as above, invertible elements are cancellable.

Answer 2

As $\operatorname{gcd}(c,m) = 1$, we have $\alpha c + \beta m = 1$ for some integers $\alpha, \beta$. Now $(a-b)c = km$ for some integer $k$. Multiplying by $\alpha$ gives $(a-b)\alpha c = \alpha km$, hence \[ (a-b)(1 - \beta m) = \alpha km \iff (a-b) = \bigl((\alpha k + (a-b)\beta\bigr)m \] So $a \equiv b \pmod m$.

Answer 3

So we know that m|(ca-cb) $\Leftrightarrow$ m|(c)(a-b) and so either m|c or m|(a-b). The fact that gcd(c,m)=1 tells us that c and m are relatively prime, so m $\nmid$ c. This implies that m|(a-b).