0
$\begingroup$

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

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

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user2993422 Jun 23 '15 at 21:24
  • 1
    $\begingroup$ @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$. $\endgroup$ – Jack D'Aurizio Jun 23 '15 at 21:26
  • 1
    $\begingroup$ It is a basic case of the Tonelli-Shanks algorithm for square root extraction in finite fields. $\endgroup$ – Jack D'Aurizio Jun 23 '15 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.