Finding roots of a polynomial using quadratic reciprocity

Question

Does the polynomial $X^2− X + 19$ have a root in $\mathbb Z/61\mathbb Z$? I am unsure of how to go about this problem but I outlined the way I have been approaching these problems in the problem below.

Does the quadratic $X^2 -59$ have a root in $\mathbb Z/61\mathbb Z$?

What I have done so far is ask myself if $59$ is a quadratic residue. In other words what is $59/61$? By reciprocity we have $59/61 = 61/51 = 10/51$ since $61 ≡ 10\bmod51$. $10$ is not prime so we will factor it as $(2/51)*(5/51).$ But $2/51$ is $-1$ since $3 ≡ 51\bmod8$. So we can rewrite it as $-1 * (5/51)$, and by reciprocity $5/51 = 51/5 = 1/5$ since $1 ≡ 51\bmod5$. So $-1*(5/51) = - (1/5) = -1 (1) = -1$, so $x^2 - 59$ does not have a root.

Answer 1

$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ Can you end it now?

Answer 2

Complete the square.

$X^2-X+19\equiv0\bmod61\iff 4X^2-4X+76\equiv0\bmod61$

$\iff (2X-1)^2\equiv-75\equiv47\equiv169=13^2\bmod61$

$2X-1\equiv\pm13\bmod61$

$2X\equiv 14$ or $-12\bmod 61$

$X\equiv7$ or $-6\bmod 61$

Answer 3

The general way to solve quadratics is to complete the square. If you have $ax^2+bx+c \equiv 0 \pmod{p}$ then completing the square will give you $y^2\equiv d \pmod{p},$ where $y = 2ax+b$ and $d=b^2-4ac.$

The nice bit is that $y$ is the derivative of the original left-hand side and $d$ is the usual discriminant of the quadratic. So for your problem:

$y = 2x+1$ and $d=1^2-4\cdot 19 = -75$.

So if $-75$ is a quadratic residue, you can solve for $y$ and then in turn solve for $x$.