How could I find $x$ in this equation $x^2-x+6 \equiv 0 \pmod {9}$

Question

This equation is like this: $$x^2-x+6 \equiv 0 \pmod{9}$$

I want to find x by using modular arithmetic. How I could do that?

My solution was:

$$\begin{align*} x(x-1) &\equiv -6 \pmod{9}\\ x(x-1) &\equiv 3 \pmod{9} \end{align*}$$

So $x$ is either: $$ x \equiv 3\pmod{9}$$

or

$$x - 1 \equiv 3 \pmod{9}$$

Which is $x \equiv 4 \pmod{9}$

I know what I have done is very dumb. So what is the correct solution? Give me the instructions also please.

Answer 1

$x^2-x+6\equiv0\bmod9$,

$4x^2-4x+24\equiv0\bmod9$,

$4x^2-4x+1\equiv-23\equiv4\bmod9$,

$(2x-1)^2\equiv4\bmod9$.

Can you take it from there?

Answer 2

It'll help to factorize $x^2-x+6$ modulo $9$, using the fact that $x^2-x+6-9n$ has discriminant $36n-23$. This is $7^2$ when $n=2$. Since $9|(x-4)(x+3)=(x^2-x+6)-2\times9$, the two factors not differing by a multiple of the prime number $3=\sqrt{9}$, the solutions are $9|x-4,\,9|x+3$ (or, if you prefer, you can write the latter as $9|x-6$).

Answer 3

Complete the square, noting $4^{-1}\equiv7$ and $2^{-1}\equiv5\pmod9$:

$x^2-x+4^{-1}\equiv x^2-x+7\equiv1\pmod9$ $\iff$

$(x-2^{-1})^2\equiv1\pmod9$ $\iff$

$x\equiv2^{-1}\pm1\equiv4 $ or $6\pmod9$,

because $9|y^2-1=(y+1)(y-1)$ means $9|y+1$ or $9|y-1$,

since $3|y+1$ and $3|y-1$ means $3|(y+1)-(y-1)=2,$

which is clearly not so.

Answer 4

If $x\equiv2\pmod3$, there are no solutions because $(3k+2)^2-3k-2=9k^2+3k+2\not\equiv0\pmod3$.

If $x\equiv0\pmod3$, then $x^2\equiv0\pmod9$, so the solutions are given by $-x+6\equiv\pmod9$, i.e. $x=9k+6$.

If $x\equiv1\pmod3$, then $x^2-x+6=9k^2+6k+1-3k-1+6\equiv3k+6\pmod9$, so $k+2\equiv0\pmod3$, and the solutions are $k=3j+1$, or $x=9j+4$.

So the solutions are $4,6\pmod9$.

Answer 5

Let me address what you did, rather than how to do it correctly, as others have answered with sundry ways of finding the answer correctly.

The very wrong thing you did was go from $$x(x-1)\equiv 3\pmod{9}$$ to $$x\equiv 3 \pmod{9}\quad\text{or}\quad x-1\equiv 3\pmod{9}.$$

That's an error that I often see in basic algebra, and it is compounded here.

In usual algebra, working in the integers, rationals, reals, or complex numbers, we have a very important property:

$$\text{if }ab=0,\text{ then }a=0\text{ or }b=0.$$

So if you were working in the real numbers, from something like $x(x-1)=0$ you would be able to conclude that either $x=0$ or $x-1=0$.

However, this is not true when the product does not equal $0$. For example, from $xy=6$ we cannot conclude that $x=6$ or $y=6$! Yet students who have seen the "trick" for solving quadratics by factoring try to extend this argument to that situation. For example, they know that they can solve $x^2-5x+6=0$ by saying:

$$\begin{align*} x^2-5x+6&=0\\ (x-3)(x-2) &= 0 \end{align*}$$ therefore either $x-3=0$ or $x-2=0$, so $x=3$ or $x=2$.

This is correct. It's correct because the only way a product in $\mathbb{R}$ can equal $0$ is if at least one factor is equal to $0$.

But then students think they can do something like the following:

$$\begin{align*} x^2-5x-6 &=0\\ x^2-5x &= 6\\ x(x-5)&=6 \end{align*}$$ and therefore $x=6$ or $x-5=6$; so $x=6$ or $x=11$.

That's wrong. You can't do that because whereas the only way to get $0$ when you multiply two reals is if one of them is $0$; getting a $6$ as the result of a product does not mean that one of the factors has to be $6$.

Now, your argument would have been wrong in the reals; the further problem here is that it would have been wrong modulo $9$ even if you had obtained the congruence $x(x-1)\equiv 0\pmod{9}$. The reason is that when you are working modulo $9$, it is possible for a product to be $0$, yet neither factor to be $0$: indeed, $(3)(3)\equiv 0\pmod{9}$, for example. So when you are working modulo $9$, you can't even use this type of argument when the product equals $0$, let alone when it doesn't equal $0$.

So you are taking an incorrect argument from another setting, already a problem, and compounding that problem by trying to use it in a setting where even the correct argument would not have worked.

Answer 6

A general method: lift easy roots $\!\bmod 3\,$ to $\!\bmod 3^2$ (by Hensel's Lemma = Newton's method)

$\!\bmod 3\!:\ 0\equiv f(x) = x^2\!-\!x\!+\!6\equiv x(x\!-\!1)\!$ $\iff\! x\equiv\color{#c00}{0,1 =: r},\ $ so $\ x = \color{#c00}r\color{#0a0}{ + 3j}$

$\!\bmod 9\!:\ 0\equiv {f(\color{#c00}r\!\color{#0a0}{+\!3j})}\overset{{\color{#90f}{\rm TT}_{\phantom |}\!}}\equiv\, \overbrace{f(\color{#c00}r)}^{\large 6}+\smash{\overbrace{(2r\!-\!1)}^{ f'(r)}}\,\color{#0a0}{3j}\iff\! (2r\!-\!1)3j\equiv 3$
$\overset{\large \div\ 3}\iff\! \bmod 3\!:\ j\equiv \dfrac{1}{2r\!-\!1}\ $ so $\,\ \bbox[5px,border:1px solid #c00]{ \begin{align} &\color{#c00}{r \equiv 0}\Rightarrow\, j \equiv -1\Rightarrow\, x\equiv r\!+\!3j \equiv -3\!\!\!\pmod{\!9}^{}\!\! \!\!\\[.1em] &\color{#c00}{r \equiv 1}\Rightarrow\, j\ \:\!\equiv\:\!\ 1\, \Rightarrow\, x\equiv r\!+\!3j \ \equiv\:\!\ 4\!\!\pmod{\!9}\end{align}}^{\phantom{|^|}}\!\!$

We used $\,\color{#90f}{\rm TT_{\phantom |}\!}\!\!:\ \color{0af}{f(r\!+\!x)} \equiv f(r) + f'(r)\, x\, \pmod{\!x^2},\,$ for $\, x = 3j,\,$ i.e. we employed $\rm\color{#90f}{Taylor's\ Theorem}$ for a polynomial $\,f(x)\,$ [or, w/o TT, simply expand $\,f(r\!+\!x)$].

Answer 7

$9$ is odd, so every value is divisible by $2 \mod 9$ but adding (or subtracting) $9$ if it is odd.

So completing the square is always attemptable.

But not every number will have square roots and not all quadratics will be solvable. If $n= 3k \pm i$ where $i=1$ or $0$ then $n^2=(9k^2 \pm 6ki +i^2)\equiv \mp 3ki + i^2$ so the squares in $\pmod 9$ will be if $i=0$ then $0 \equiv 0^2, 3^2, 6^2$; other wise $i\equiv 1$ and if $k=0$ then $1\equiv 1^2, 8^2$ and if $k=1$ then $4\equiv 2^2,7^2$ and if $k=2$ then $7\equiv 4^2, 5^2$.

Completing the square:

$x^2 -x + 6 \equiv 0 \pmod 9$

$x^2 +8x + 6\equiv 0\pmod 9$

$x^2+ 8x + 16-10\equiv 0\pmod 9$

$(x+4)^2 \equiv 10\equiv 1\pmod 9$

So $x+4 \equiv 1,8\pmod 9$

$x\equiv 6,4\pmod 9$.

However $x^2 -x + 4\equiv 0\pmod 9$ would have no solutions as

$x^2 -x +4\equiv 0\pmod 9\implies$

$x^2 + 8x+ 16 -12\equiv 0\pmod 9\implies$

$(x+4)^2 \equiv 3\pmod 9$ and there is no $a^2 \equiv 3\pmod 9$ solutions.

Answer 8

Update: I just noticed that this answer is in the same vein as the answer given by JMP, but the step-by-step instructions(method) follows a predetermined pedagogical flow.

---

Solve

$\tag 1 x^2 - x + 6 \equiv 0 \pmod9$

Let $T = \{0,1,2\}$ and recall that every integer $n$ satisfying $0 \le n \lt 9$ has a representation

$\tag 2 n = 3q + r \quad \text{where } r,q \in T$

Using simple algebra,

$\tag 3 n^2 -n + 6 = 9 q^2 + 6 q r - 3 q + r^2 - r + 6$

Setting $r = 0$ on the rhs of $\text{(3)}$,

$\quad 9 q^2 - 3 q + 6 \equiv 0 \pmod9 \; \text{ implies } \; 3q \equiv 6 \pmod9$

and we see that $[x] = [3\cdot2 + 0] = [6]$ is a solution to $\text{(1)}$

Setting $r = 1 $on the rhs of $\text{(3)}$,

$\quad 9q^2 + 3q + 6 \equiv 0 \pmod9 \; \text{ implies } \; 3q + 6 \equiv 0 \pmod9$

and we see that $[x] = [3\cdot1 + 1] = [4]$ is a solution to $\text{(1)}$

Setting $r = 2$ on the rhs of $\text{(3)}$,

$\quad 9 q^2 + 9 q + 8 \equiv 0 \pmod9 \; \text{ implies } \; 8 \equiv 0 \pmod9$

We conclude that $[4]$ and $[6]$ are all the solutions to $\text{(1)}$.