solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$

Question

I need to solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$

I saw the same problem here -

Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$

but didn't understand how he got to the conclusion

$x(x+2) \equiv 6 \pmod {19}$

and anyway im trying to solve it how we learned in class -

multiply both sides and the modulo by $4a$ then solve the two equations

$y^2 \equiv b^2 -4ac \pmod {4an}$

$2ax + b \equiv y \pmod {4an}$

so I tried multiplying the hole thing by $4a$ , that is $4 \times 3$

and got to $(2 \times 3x + 6)^2 \equiv 36 -4 \times 3 \pmod {19 \times 4 \times 3}$

now I am stuck . any help will be appreciated

Answer 1

In general, you can always complete the square after multiplying both sides by $4a$:

$$ax^2+bx+c\equiv 0\stackrel{\cdot 4a}\iff (2ax+b)^2\equiv b^2-4ac\pmod{\! p}$$

$$3x^2+6x+1\equiv 0\stackrel{\cdot 4\cdot 3}\iff (6x+6)^2\equiv 24\equiv 5\pmod{\! 19}$$

$$\left(\frac{5}{19}\right)=\left(\frac{19}{5}\right)=\left(\frac{2^2}{5}\right)=1$$

Squaring $\pm 1,\pm 2,\ldots, \pm 9$ is straightforward and quick, to find a square root of $5$ mod $19$.

As Jack explained, $\pm a^{(p+1)/4}$ are the square roots (if they exist) of $a$ mod $p$ ($p=4k-1$).

$$\pm 5^{(19+1)/4}\equiv \pm5^5\equiv\pm 9\pmod{\! 19}$$

So $6x+6\equiv \pm 9\pmod{\! 19}$, i.e. $x\equiv \{7,10\}\pmod{\! 19}$.

Quadratic formula exists for congruences too, and is straightforward to prove (multiply by $4a$, like above):

If $a\not\equiv 0$ with $p$ odd prime and $b^2-4ac\equiv z^2\pmod{\! p}$, then

$$ax^2+bx+c\equiv 0\iff x\equiv \frac{-b\pm z}{2a}\pmod{\! p}$$

When solving quadratic congruences, the biggest problem is finding such $z$. You can either use brute-force by squaring $\pm 1,\pm 2,\ldots, \pm \frac{p-1}{2}$ (only nine squarings in this case) or use more advanced methods, such as Tonelli-Shanks algorithm (as used in the above simple case of $p\equiv 3\pmod{\! 4}$) or Cipolla's algorithm.

Answer 2

That is equivalent to: $$ 3x^2+6x+39\equiv 0\pmod{19} $$ or to: $$ x^2+2x+13\equiv 0\pmod{19} $$ or to: $$ (x+1)^2 \equiv 7\pmod{19}. $$ Since $\left(\frac{7}{19}\right)=-\left(\frac{5}{7}\right)=-\left(\frac{2}{5}\right)=+1$ and $19$ is a prime of the form $4k-1$, a square root of $7$ is given by $$ 7^{\frac{19+1}{4}}\equiv 7^{5}\equiv 11\pmod{19} $$ and the solutions are $x+1\equiv \pm 11\pmod{19}$, or $x\in\{7,10\}\pmod{19}$.