# Congruence relation possible typo?

Is the following a typo? If $a \equiv b \pmod{m}$, then for some scalar $c>0$, $ac \equiv bc \pmod{mc}$

Or should it be $\pmod{m}$?

• Both conditions hold, so you really can't say whether this is a typo or not
– Aang
Jun 17, 2013 at 18:12
• More importantly, the relationship goes the other way: if $c\ne 0$, then $a\equiv b\pmod{m}$ if and only if $ac\equiv bc\pmod{mc}$. Jun 17, 2013 at 18:12
• If I were to revise the sentence you quoted, I'd leave "$\pmod{mc}$" alone, but I'd change "some scalar" to "every scalar". Jun 17, 2013 at 18:40

No typo in the congruence equations or implication:

Theorem: $$\text{If}\; a \equiv b \pmod{m},\;\text{ then for any scalar }\;c \neq 0,\; ac \equiv bc \pmod{mc} \tag{\dagger}$$

$$a \equiv b \pmod m \quad\iff (a - b) \equiv 0 \pmod m \quad\iff\; (a - b) = km, \;k\in \mathbb Z.$$

$$(a-b) = km \;\iff\; c(a-b) = c(km),\; (c\neq 0)\quad \iff \;(ac - bc) = k(mc),\;k\in \mathbb Z.$$

$$\iff (ac - bc)\equiv 0\pmod{mc} \quad \iff \;ac\equiv bc \pmod{mc}, mc \in \mathbb Z.$$

For your second question: "should it be $\pmod{m}$?"

That would certainly be true, as well, but is not as strong a statement. But we do indeed have that for $c\neq 0$: $$ac \equiv bc \pmod{mc} \implies ac\equiv bc \pmod m$$ since $$ac \equiv bc \pmod{mc} \iff mc\mid (ac - bc) \implies m\mid (ac - bc) \iff ac\equiv bc \pmod m$$

Recall the definition of $x \equiv y \pmod{z}$:

$$\exists k \in \Bbb Z: x - y = kz$$

Multiplying this equation by $c$, we immediately obtain that:

$$a \equiv b \pmod m \implies ac \equiv bc \pmod {mc}$$

• @amWhy Why did you do that? Modulo $0$ is simply the diagonal equivalence relation; since $0 = 0$, the consequent holds even if $c = 0$. Jun 17, 2013 at 19:34
• apologies. I'llhenceforth leave your posts untouched. Jun 17, 2013 at 19:40

$$a\equiv b\pmod m\iff a=b+n\cdot m$$ for some integer $n$

$$ac-bc=c(a-b)=c\cdot n\cdot m\equiv0\pmod {m\cdot c}$$ as $n$ is an integer

See $a\equiv b \pmod m\implies m\mid (a-b)\implies mc\mid(a-b)c\implies ac\equiv bc \pmod {mc}$