# What modular arithmetic theorem is being ignored here?

1. Suppose $4x\equiv 6 \pmod {18}$ Then $2x\equiv 3 \pmod 9$ Then $6x\equiv 9 \pmod 9$ Then $6x\equiv 0 \pmod 9$ Then $x\equiv 0 \pmod 9$ Then $x=9k$

vs.

1. Suppose $4x\equiv 6 \pmod {18}$ Then $2x\equiv 3 \pmod 9$ Then $2x\equiv 12 \pmod 9$ Then $x\equiv 6 \pmod 9$ Then $x = 9k+6$
• In (i): $\;6x=0\pmod 9\rlap{\;\;\;\;/}\implies x=0\pmod 9\;$ . For example, $\;6\cdot 3=0\pmod 9\;$ but $\;3\neq 0\pmod 9\;$ – DonAntonio Apr 5 '14 at 18:20
• No theorem is ignored, but there is a "non sequitur" in 1. – Hagen von Eitzen Apr 5 '14 at 18:25

## 4 Answers

$6x\equiv 0\pmod 9$ does not imply $x\equiv 0\pmod 9$. Because $6$ and $9$ are not coprime. What you do get by dividing out one $3$ is that $2x\equiv 0\pmod 3$, though - but you knew that already.

In $1$ the step from $6x\equiv 0$ (mod $9$) to $x\equiv 9$ (mod $9$) is invalid. The conclusion should be $2x\equiv 0$ (mod $3$), because the modulus is divisible by $3$ and then $x\equiv 0$ (mod $3$), because $(2,3)=1$. Or equivalently go all the way in one step because $(6,9)=3$ and if you want to divide by $6$ you must divide the modulus by $(6,9)$.

The problem is that you perform a noninvertible transformation on the equation by scaling it by $$\,3,\,$$ because $$\,3\,$$ is noninvertible mod $$\,9.\,$$ Doing that will generally introduce extraneous roots. Indeed $$\!\bmod 9\!:\ 2x\equiv 3\,\Rightarrow\, 6x\equiv 9\equiv 0,\,$$ and $$\,6x\equiv 0\!\iff\! 9\mid 6x\!\iff\! 3\mid 2x\!\iff\! 3\mid x\,$$ (not $$\,9\mid x).$$ Now $$\,3\mid x\!\iff\! x\equiv \color{#c00}{0,3},6\pmod{\! 9},\,$$ but $$\,x\equiv \color{#c00}{0,3}\,$$ are not roots of $$\,2x\equiv 3\pmod{\! 9},\,$$ even though they are roots of $$\,6x\equiv 9.$$

But if we scale by an invertible $$\,c\,$$ then $$\,ax\equiv b\,\smash[t]{\underset{\color{#c00}{\ \times\ c^{-1}}}{\color{#c00}{\Longleftarrow}}\!\!\color{#0a0}{\overset{\times\ c}\Longrightarrow}} \ acx\equiv bc,\,$$ since the direction $$\,(\color{#c00}{\Longleftarrow})$$ follows by multiplying the RHS by $$\,\color{#c00}{c^{-1}}.\,$$ So the lhs and rhs congruences have exactly the same set of roots. Hence no extraneous roots are introduced by scaling by an invertible element.

It's the multiplication law of modulus arithmetic. For all $a_1,a_2,b_1,b_2,n$ integers, $a_1 a_2 \equiv b_1 b_2 \pmod n.\,$