0

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$
Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908

4 Answers4

2

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

Hagen von Eitzen
  • 1
  • 30
  • 346
  • 631
1

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

Mark Bennet
  • 98,199
  • 12
  • 113
  • 218
1

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 $\,a\,$ then $\,bx\equiv c\,\smash[t]{\underset{\color{#c00}{\ \times\ a^{-1}}}{\color{#c00}{\Longleftarrow}}\!\!\color{#0a0}{\overset{\times\ a}\Longrightarrow}} \ abx\equiv ac,\,$ since the direction $\,(\color{#c00}{\Longleftarrow})$ follows by multiplying the RHS by $\,\color{#c00}{a^{-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, i.e. the scaled congruence is equivalent to the original congruence.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
0

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