3
$\begingroup$

I am looking into congruences for school and I have trouble understanding on how to prove this (i understand modules, congruences but don't know how to prove it).

I need to prove that if this congruence is true:

$$a c \equiv b c \pmod m$$

then also this holds:

$$a \equiv b \pmod{m/\gcd(c,m)}$$

Can some one please explain or give a hint how I can prove this? I have tried googling but all the proofs I have found are without a good explanation to help me understand it.

Thanks!

$\endgroup$
2
$\begingroup$

Let $d=\operatorname{gcd}(c,m)$, write $m=d\cdot m'$, $c=d\cdot c'$. You are given that $a\cdot c-b\cdot c=k\cdot m$ for some $k\in\mathbb Z$. It follows that $a\cdot d\cdot c'-b\cdot d\cdot c'=k\cdot d\cdot m'$, hence $a\cdot c'-b\cdot c'=k\cdot m'$, so at least $a\cdot c'\equiv b\cdot c'\pmod{m'}$. But now $c'$ and $m'$ are relatively prime! Does that help in showing $a\equiv b\pmod {m'}$?

$\endgroup$
1
  • $\begingroup$ Yes, thank you very much! $\endgroup$
    – blejzz
    Sep 13 '12 at 21:05
3
$\begingroup$

Hint $ $ Let $\rm\ d=(m,c).\, $ $\rm\,m\:|\:c(a\!-\!b)\!\!\iff\! \!\frac{m}d|\frac{c}d(a\!-\!b)\!\!\color{#C00}{\iff}\!\! \frac{m}d|\:a\!-b\,\: $ by $\rm\ (\frac{m}d,\frac{c}d)= \frac{(m,c)}d = 1$

Remark $\ $ The $\rm\color{#C00}{final}\,$ equivalence employs Euclid's Lemma and the distributive law for GCDs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.