I finally understand simple congruences. Now how to solve a quadratic congruence?

Now that I have plain old congruences, $19x\equiv 4 \pmod {141}$ for example, I am trying to wrap my brain around quadratic ones. My textbook shows how to tackle the aforementioned congruences, but not quadratic.

$$15x^2 + 19x\equiv 5 \pmod {11}$$

The book hints to show that would be equivalent to

$$15x^2 + 19x + 6\equiv 0 \pmod{11}$$

I have no idea how they got that. I've looked at previous answers, but I need a dumbed down version.

Solution 1:

$$15x^2+19x\equiv 5 \mod 11$$ is equivalent to $$15x^2+19x +6 \equiv 0 \mod 11$$ by the fact that we can subtract $5$ from both sides of the congruence (and $-5\equiv 6 \mod 11$).

From here, we factor $15x^2+19x+6$ to give $(3x+2)(5x+3)$. This means that our original quadratic congruence is equivalent to $$(3x+2)(5x+3)\equiv 0 \mod 11.$$ This will only hold true if $$3x+2 \equiv 0 \mod 11 \quad \text{or} \quad 5x+3 \equiv 0 \mod 11,$$ or equivalently $$3x\equiv 9 \mod 11 \quad \text{or} \quad 5x\equiv 8 \mod 11.$$

Since you're familiar with solving linear congruences, you should be able to solve these.

Solution 2:

$0\equiv 4x^2\!+\!8x\!-\!5\equiv \overbrace{(2x)^2\!+\!4(2x)\!-\!5}^{\large X^2\ +\,\ 4\,X\,\ -\,\ 5\!\!\! }\equiv\overbrace{(2x\!+\!5)(2x\!-\!1)}^{\large (X\ +\ 5)\ (X\ -\ 1)}\,$ so $\,\begin{align} &2x\equiv\color{#c00}{-5}\equiv6\\ &2x\equiv\,\color{#c00} 1\,\equiv 12\end{align}\ $ so $\ x\equiv \ldots$

Or, complete the square $\,0\equiv 4x^2\!+\!8x\!-\!5\equiv (2x\!+\!2)^2\!-\!3^2$ so $\,2x\!+\!2\equiv \pm3\,$ so $\,2x\equiv\color{#c00}{ -5,1}\dots$

Or, apply the quadratic formula. First we make the lead coef $=1$ by scaling by $1/4\equiv 12/4\equiv3\,$ to get $\ 3(4x^2 + 8x - 5)\equiv x^2 + \color{#0a0}2\,x-4\equiv 0.\,$ It has discriminant $\, 2^2\!-4(-4)\equiv 20\equiv 9\equiv \color{#a0f}3^2,\,$ therefore the roots are $\,x\equiv(-\color{#0a0}2\pm\color{#a0f} 3)/2\equiv \{\color{#c00}{-5,1}\}/2\equiv \{6,12\}/2\equiv \{3,6\}$

Solution 3:

Here is how to solve it generally. Every $\equiv$ here refers to equivalence $\!\bmod {p}$.

If $a\not\equiv 0$ with $p$ odd prime, then $$ax^2+bx+c\equiv 0\Leftrightarrow 4a^2x^2+4abx+4ac\equiv 0\Leftrightarrow (2ax+b)^2\equiv b^2-4ac$$

So for the congruence to have solutions, necessarily $b^2-4ac\equiv z^2$ for some $z\in\mathbb Z_p$.

$$\Leftrightarrow 2ax+b\equiv \pm z\Leftrightarrow x\equiv \frac{-b\pm z}{2a}$$

If $a\not\equiv 0$ with $p$ odd prime and $b^2-4ac\equiv z^2$ for some $z\in\mathbb Z_p$, then $$ax^2+bx+c\equiv 0\Leftrightarrow x\equiv \frac{-b\pm z}{2a}$$

If $a\equiv 0$ or $p=2$, the congruence is trivial, and if $\left(\frac{b^2-4ac}{p}\right)=-1$ (Legendre symbol, meaning $b^2-4ac$ is not a square $\!\bmod p$), $a\not\equiv 0,$ $p$ odd prime, it has no solutions.

In your case, $a\not\equiv 0$ with $p$ odd prime ($p=11, a\equiv 15, b\equiv 19, c\equiv 6$) and $b^2-4ac\equiv 1^2$, so we can use the theorem above:

$$15x^2+19x+6\equiv 0\Leftrightarrow x\equiv \frac{-19\pm 1}{2\cdot 15}\equiv\frac{3\pm 1}{-3}\equiv \{-4\cdot 3^{-1}, -2\cdot 3^{-1}\}\equiv \{6,3\}$$

Here I used $3(3^{-1})\equiv 1\equiv 12\Leftrightarrow 3^{-1}\equiv 4$.