Encontrar raíces de un polinomio usando reciprocidad cuadrática

Question

¿El polinomio $X^2− X + 19$ tener una raíz en $\mathbb Z/61\mathbb Z$? No estoy seguro de cómo abordar este problema, pero describí la forma en que he abordado estos problemas en el problema siguiente.

¿El cuadrático $X^2 -59$ tener una raíz en $\mathbb Z/61\mathbb Z$?

Lo que he hecho hasta ahora es preguntarme si $59$es un residuo cuadrático. En otras palabras, lo que es$59/61$? Por reciprocidad tenemos$59/61 = 61/51 = 10/51$ ya que $61 ≡ 10\bmod51$. $10$ no es primo, por lo que lo factorizaremos como $(2/51)*(5/51).$ Pero $2/51$ es $-1$ ya que $3 ≡ 51\bmod8$. Entonces podemos reescribirlo como$-1 * (5/51)$, y por reciprocidad $5/51 = 51/5 = 1/5$ ya que $1 ≡ 51\bmod5$. Entonces$-1*(5/51) = - (1/5) = -1 (1) = -1$, entonces $x^2 - 59$ no tiene raíz.

Answer 1

$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ ¿Puedes terminarlo ahora?

Answer 2

Completar el cuadrado.

$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$ o $-12\bmod 61$

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

Answer 3

La forma general de resolver cuadráticas es completar el cuadrado. Si usted tiene$ax^2+bx+c \equiv 0 \pmod{p}$ luego completar el cuadrado te dará $y^2\equiv d \pmod{p},$ dónde $y = 2ax+b$ y $d=b^2-4ac.$

Lo bueno es que $y$ es la derivada del lado izquierdo original y $d$es el discriminante habitual de la cuadrática. Entonces, para tu problema:

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

Así que si $-75$ es un residuo cuadrático, puedes resolverlo $y$ y luego a su vez resolver para $x$.