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}$?
$\begingroup$
$\endgroup$
3
asked Jun 17, 2013 at 18:06
-
$\begingroup$ Both conditions hold, so you really can't say whether this is a typo or not $\endgroup$– AangJun 17, 2013 at 18:12
-
$\begingroup$ 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}$. $\endgroup$– André NicolasJun 17, 2013 at 18:12
-
1$\begingroup$ If I were to revise the sentence you quoted, I'd leave "$\pmod{mc}$" alone, but I'd change "some scalar" to "every scalar". $\endgroup$– Andreas BlassJun 17, 2013 at 18:40
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
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$$
$\begingroup$
$\endgroup$
2
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}$$
answered Jun 17, 2013 at 18:08
-
$\begingroup$ @amWhy Why did you do that? Modulo $0$ is simply the diagonal equivalence relation; since $0 = 0$, the consequent holds even if $c = 0$. $\endgroup$ Jun 17, 2013 at 19:34
-
$\begingroup$ apologies. I'llhenceforth leave your posts untouched. $\endgroup$– amWhyJun 17, 2013 at 19:40
$\begingroup$
$\endgroup$
$$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
$\begingroup$
$\endgroup$
See $a\equiv b \pmod m\implies m\mid (a-b)\implies mc\mid(a-b)c\implies ac\equiv bc \pmod {mc}$
