Elementary Number Theory: Solving Quadratic Conguences

Question

If possible solve the following congruence,

$7x^2-4x+1 \equiv 0 \pmod {11}$. I am using the quadratic equation but I am stuck. The following is where I got stuck:

$x \equiv 4(4\pm \sqrt{-12}\pmod {11}$

I have tried adding $11$ repeatively but I cannot get a perfect square root. Please help!

Answer 1

So quadratic formula:

$7x^2 -4x + 1\equiv 0 \mod 11\implies$ (using the standard notation abuse)

$x \equiv \frac {4 \pm \sqrt {16 - 28}}{14}\mod 11$

$\frac 12 \equiv 6$ and $\frac 17 \equiv 8$ so $\frac 1{14}\equiv 48 \equiv 4$.

So $x \equiv {16 \pm \sqrt{-12} } \equiv 5\pm \sqrt{-1}$

Now $x^2 \equiv -1 \mod 11$ has no solutions as $11 \not \equiv 1 \mod 4$.

So no solutions.

Or we could try doing this directly:

$7x^2 -4x + 1\equiv 0$

$-4x^2 - 4x \equiv -1$

$4x^2 - 4x \equiv 1$

$4x^2 + 4x \equiv 1$

$4x(x+1)\equiv 1$

$x(x+1)\equiv -x(-x - 1) \equiv 3 \mod 11$.

We could simply test $6$ cases: $x=0;\pm 1$ are trivial. $\pm 2;3;4;5$ are easy.

Or we can simply list the quadratic residues mod $11$ are $0, 1,4,9,5,3$.

And completing the square:

$7x^2 - 4x + 1\equiv 0$

$\frac 17(7x^2 - 4x + 1) \equiv 0$

$8(7x^2 - 4x +1) \equiv 0$

$x^2 - 32x + 8 \equiv 0$

$x^2 - 32x \equiv -8$

$x^2 -10x + 25 \equiv 17\equiv 6$

$(x-5)^2 \equiv 6 \mod 11$ and $6$ is not a modulo class.

Answer 2

$$0 \equiv 7x^2-4x+1 \equiv -4x^2-4x-1+2 \equiv 2-(2x+1)^2 \pmod {11}$$

so

$$(2x+1)^2 \equiv 2\pmod {11}$$

Since for each $a$ we have $$a^2 \equiv 0,1,4,-2,5,3\pmod {11}$$

there is no solution to this congruence.

Answer 3

There is no solution. Multiply by $8$ and complete the square to get $$(x+5)^2\equiv 6(\mod 11)$$ and $6$ is a quadratic non residue.

Answer 4

$-12\equiv_{11}-1$ is not a square in $\mathbb{Z}_{11}$, so $\sqrt{-12}$ in your expression has no value, and there are therefore no solutions.

There are two ways to see why this is the case:

• $\left (\frac{-1}{p}\right )=(-1)^{\frac{p-1}{2}}$, the Legendre symbol. So $\left (\frac{-1}{11}\right )=(-1)^5=-1$.

• By brute-force: $0^2\equiv_{11}0$, $(\pm 1)^2\equiv_{11}1$, $(\pm 2)^2\equiv_{11}4$, $(\pm 3)^2\equiv_{11}-2$, $(\pm 4)^2\equiv_{11}5$, $(\pm 5)^2\equiv_{11}4$. So $-1$ is not a square.

Answer 5

Note that since $8$ is the inverse of $7 \pmod {11}$ we have

$$7x^2-4x+1 \equiv 0\iff 8\cdot7x^2-8\cdot4x+8\cdot1 \equiv 8\cdot0\iff x^2+12x+8\equiv 0 \pmod {11}$$

and

$$x^2+12x+8\equiv0 \iff (x+6)^2 \equiv6 \pmod {11}$$

whic is impossible.