

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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

share|cite|improve this question
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.

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


