Solución a $x^2+x-1\equiv 0$ mod $p$

Question

Necesito ayuda en la comprensión de las soluciones a

$x^2+x-1\equiv 0 \mod p.$

He corrido algunas pruebas y se encontró que para los que no hay soluciones para p=13,17,23,37,43,47 y hay exactamente 2 soluciones para p=11,19,29,31,41.

Supongo que el primer paso sería que muestra que los primos de hacer/no tienen solución y que muestra que aquellos que sólo tienen 2 soluciones, y si es posible la búsqueda de soluciones.

Gracias. Cualquier ayuda será apreciada.

Answer 1

Las soluciones están dadas por la fórmula habitual: $x_{1,2}=\frac{-1\pm\sqrt{5}}{2}$. El problema es sólo para hacer sentido de las operaciones involucradas. La división por $2$ es posible sólo si $p\ne 2$ (y de forma explícita que compruebe que no hay ninguna solución $\pmod 2$). Y una raíz cuadrada de $5$ sólo existe el modulo certanin $p$ (por ejemplo,$4^2=16\equiv 5\pmod{11}$). La ley de la reciprocidad cuadrática nos dice que $5$ es un cuadrado de $\pmod p$ fib $p$ es un cuadrado de $\pmod 5$, que es el fib $p\equiv \pm1\pmod 5$ o $p=5$. Así que por estas $p$ hay soluciones (una única solución para $p=5$ donde $\sqrt 5=0$, dos soluciones distintas de otra manera), mientras que para $p\equiv \pm2$ no hay solución.

Answer 2

Primero entender que $4$ es invertible $\mod p,$, por lo que tenemos $x^2+x-1 = 0 \mod p $ si y sólo si $4x^2+4x-4=0 \mod p.$ La idea es completar el cuadrado, podemos escribir la ecuación anterior como $(2x+1)^2 = 5 \mod p.$ Así que ahora usted puede resolver la ecuación siempre se puede solucionar $y^2 = 5 \mod p.$ Poner el problema en este formulario debe recordar que de la reciprocidad cuadrática.