How many solutions does $x^2 + 3x +1 \equiv 0\, \pmod{101}$ have? $x^2 + 3x +1 \equiv 0 \pmod{101}$. To solve this I found the determinant $D = 5 \pmod{101}$). Using the Legendre symbol,
$$\left(\frac{5}{101}\right) = \left(\frac{101}{5}\right) \equiv \left(\frac{1}{5}\right) \equiv 1,$$
$\therefore$ The equations have a solution.
My question is how I can find out how many solutions it has?
 A: Since
$$
(x-49)^2-77\equiv x^2+3x+1\pmod{101}
$$
we are looking for solutions to $(x-49)^2\equiv77\pmod{101}$. You have verified that there is a root, so $77$ is a quadratic residue mod $101$, thus, there are two solutions for
$$
(x-49)^2\equiv77\pmod{101}
$$
Alternatively, working mod $101$, by squaring and multiplying
$$
77^2\equiv71\\
77^3\equiv13\\
77^6\equiv68\\
77^{12}\equiv79\\
77^{24}\equiv80\\
77^{25}\equiv100\\
77^{50}\equiv1
$$
Therefore, $77$ is a quadratic residue mod $101$. Thus, there are two solutions to $x^2+3x+1\pmod{101}$.
A: An idea to tackle this and similar questions using as small numbers and multiples of $\;101\;$ as possible (when possible, of course...). 
Observe that $\;5=-96\pmod {101}\;$ , and $\;96=2^5\cdot3\;$ , so we can try to deal with these apparently easier numbers. Since we have $\;96=16\cdot6\;$, we have:
$$4^2=16=2^4\;,\;\;101\cdot2=202-6=196=14^2$$
and thus we have: 
$$\;\sqrt{16}=4\;,\;\;\sqrt{-6}=14\implies \sqrt{16\cdot(-6)=-96}=4\cdot14=56$$
and thus also $\;\sqrt{-96}=-56=45\;$ , so $\;x^2=5\pmod{101}\implies x=\pm56=56,\,45\;$ 
Finally, your quadratic's solutions are ($\pmod{101}$ ):
$$x_{1,2}=\frac{-3\pm56}2=\begin{cases}\frac{98+56}2=77\\{}\\\frac{98-56}2=21\end{cases}$$
A: If the discriminant of a quadratic is a nonzero square modulo odd prime $p$, then the quadratic has exactly two roots mod $p$.
A: For prime  $p$: If $A$ is a square modulo $p,$ take any B such that $A\equiv B^2\pmod p.$ Then $$x^2\equiv A \pmod p\iff (x-B)(x+B)\equiv x^2-B^2\equiv 0 \pmod p\iff$$ $$\iff (\;p|(x-B)\lor p|(x+B)\;)\iff x\equiv \pm B \pmod p.$$  If $A\not \equiv 0 \pmod p,$ then $B\not \equiv 0\pmod p.$  If $p\ne 2,$ and $B\not \equiv 0 \pmod p$ then $B\not \equiv -B \pmod p.$ So for $p\ne 2$ and $A\not \equiv 0\pmod p$  there are, modulo $p,$ exactly $2$ solutions to $x^2\equiv A \pmod p,$ which  are $x\equiv \pm B \pmod p.$
In your Q you are looking for solutions to $(2x+3)^2\equiv 5 \pmod {101}.$  Take any $B$ such that $B^2\equiv 5 \pmod {101}.$ Then $(2x+3)^2\equiv B^2 \iff 2x+3\equiv \pm B \pmod {101},$ which implies there exactly $2$ values, modulo $101$, for $x$.
