Solve the congruence $3x^2+x+8\equiv 0 \pmod{11}$ 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.
 A: 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}$$
A: $$
\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

A: 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.
