Solve the congruence $3x^2+x+8\equiv 0 \pmod{11}$

Question

How to find the solutions of this congruence? $$3x^2+x+8\equiv 0 \pmod{11}$$ I need to find the inverse of $3$, and there I have a problem.

Answer 1

One method is to form the square on the LHS :

$$12 \cdot(3x^2+x+8) \equiv 0 \pmod{11}$$

$$36x^2+12x+1+95 \equiv 0 \pmod{11}$$

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

This means that $$6x+1 \equiv \pm 2 \pmod{11}$$

When $6x+1 \equiv 2 \pmod{11}$ multiply by $2$ so :

$$12x \equiv 2\pmod{11}$$

$$x \equiv 2 \pmod{11}$$

Doing the same for the other leads to the other solution :

$$ x \equiv 5 \pmod{11}$$

Answer 2

$$ \begin{split} 3x^2 + x + 8 = 0 [11] &\iff 3^{-1}(3x^2 + x + 8) = 0 [11] \iff x^2 + 4x + 10 = 0 [11] \\ &\iff (x + 2)^2 = -6 = 5 = 4^2 [11] \iff x + 2 = \pm 4[11]\\ & \iff x = 2,5[11]. \end{split} $$

This completing-the-square can be generalized to any modulus $p$, provided you know how to

• detect squares modulo $p$ (Hint: use the Jacobi symbol), and
• compute square roots modulo $p$, say using something like Tonelli-Shanks.

---

BTW, a brute-force algorithm for your problem has linear complexity in the modulus $p$, and this constitutes and "effective way" of solving the problem for small $p$ :). For example, in Python, you'd do:

for x in range(11):
    if (3 * x ** 2 + x + 8) % 11 == 0:
        print x

and get the output

2
5

Answer 3

In general, if $p$ is an odd prime and $p\nmid a$, then $$ax^2+bx+c\equiv 0\pmod{p}\iff 4a\left(ax^2+bx+c\right)\equiv 0\pmod{p}$$

$$\iff (2ax+b)^2\equiv b^2-4ac\pmod{p}$$

At this point, you're just left with finding the square roots of $b^2-4ac$ mod $p$.

---

In your case, $$3x^2+x+8\equiv 0\pmod{11}\iff (6x+1)^2\equiv 4\pmod{11}$$

In this case, the square roots of $4$ mod $p$ are simply $\pm 2$, so:

$$\iff 6x+1\equiv \pm 2\pmod{11}$$

$$\iff x\equiv \left\{\frac{2-1}{6},\frac{-2-1}{6}\right\}\equiv \left\{\frac{1}{6},\frac{-3}{6}\right\}\pmod{11}$$

$$\iff x\equiv \left\{\frac{12}{6}, -\frac{1}{2}\right\}\equiv \left\{2,-\frac{12}{2}\right\}\equiv \{2,-6\}\equiv \{2,5\}\pmod{11}$$

---

I'll explain about the general solution.

As I said, you're just left with finding the square roots of $b^2-4ac$ mod $p$ (after that it's simple).

So you're left with solving $X^2\equiv A\pmod{p}$ to find $X$,

where $X\equiv 2ax+b\pmod{p}$ and $A\equiv b^2-4ac\pmod{p}$.

A solution exists if and only if $\left(\frac{A}{p}\right)\in\{0,1\}$. This denotes the Legendre Symbol. Finding it might require Quadratic Reciprocity.

If a solution exists, then see this paper and Wikipedia for how to find the solutions.

If $p\equiv 3\pmod{4}$, then $X\equiv \pm A^{\frac{p+1}{4}}\pmod{p}$.

If $p\equiv 5\pmod{8}$, then either $X\equiv \pm A^{\frac{p+3}{8}}\pmod{p}$ or $X\equiv \pm 2^{\frac{p-1}{4}}A^{\frac{p+3}{8}}\pmod{p}$.

If $p\equiv 1\pmod{8}$, then it's complicated. You may need to apply either Cipolla's Algorithm or Tonelli-Shanks algorithm, or see the paper I linked.