# Congruences, elementary number theory

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

-
Is there a question here? –  Rick Decker Aug 27 '13 at 1:31

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.

-

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$.

-
I don't see how you get that last line. $(a-b)=(\alpha k+ \beta)m$ –  Swine.Flu Sep 27 '12 at 0:53
@user42783 Thx, corrected it. –  martini Sep 27 '12 at 5:31