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

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

• $3x^2+6x+1\equiv 3x^2+6x-18\equiv 0\stackrel{:3}\iff x(x+2)\equiv 6\pmod{\! 19}$ – user26486 Jun 23 '15 at 18:15

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.

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}$.

• can you please explain how you got from 19 is a prime of the form 4k-1 to $7^{(19+1)\4}$ as the square root? – user2993422 Jun 23 '15 at 21:24
• @user2993422: It is a well-known result. If $p\equiv -1\pmod{4}$ and $a$ is a quadratic residue $\pmod{p}$, then: $$\left(a^{\frac{p+1}{4}}\right)^2 = a^{\frac{p+1}{2}} = a\cdot\left(\frac{a}{p}\right)=a,$$ proving that $a^{\frac{p+1}{4}}$ is a square root of $a$. – Jack D'Aurizio Jun 23 '15 at 21:26
• It is a basic case of the Tonelli-Shanks algorithm for square root extraction in finite fields. – Jack D'Aurizio Jun 23 '15 at 21:29