Decidir si un quártico univariado tiene una solución mod p

Question

Tengo una ecuación en la $x$ y me gustaría saber si tiene alguna solución modulo un gran primer $p$. Supongamos $p$ es suficientemente grande como para que yo pueda factor de números de hasta el $p$, pero no puedo probar todos los valores de a $p$. (En realidad, hasta ahora, he estado haciendo solo eso, pero me gustaría evitar esto, ya que lleva mucho tiempo. Si usted puede evitar el factoring, mejor que mejor.)

El particular de la ecuación que tengo es $$ x^4-x^2\equiv4\pmod p $$ pero yo estaría interesado en

1. Las soluciones a este problema en particular, o de manera más general
2. Soluciones a otros cuadráticas$\pmod p$ $x^2$ o, más en general
3. Soluciones para cuárticas$\pmod p$.

Estoy familiarizado con la reciprocidad cuadrática, pero no con cúbicos o biquadratic. (No me queda claro si esto puede ser transformado para que puedan ser utilizados; si es así, la demostración de la transformación y dando un puntero a una buena fuente de mayor reciprocidad sería suficiente como respuesta.)

Answer 1

El producto de los lineales de los factores de un polinomio $f(x) \in \mathbb{F}_p[x]$ está dado por

$$\gcd(x^p - x, f(x))$$

más de $\mathbb{F}_p[x]$, que se puede calcular rápidamente para pequeñas $p$ por el algoritmo de Euclides. Para mayor $p$, se puede calcular $x^p \bmod f(x)$ (pensamiento de $f(x)$ como un elemento de $\mathbb{F}_p[x]$) por exponenciación binaria, con cuidado para reducir el $\bmod f(x)$ a cada paso.

El problema de describir explícitamente el conjunto de los números primos $p$ por lo que algunos polinomio tiene una raíz $\bmod p$ requiere una mayor reciprocidad de las leyes. Cuando el grupo de Galois del polinomio es abelian, a mi entender, es que estos pueden ser deducidas a partir de los resultados generales en el campo clase de teoría. Cuando el grupo de Galois es nonabelian, mi entendimiento es que la mayor reciprocidad de las leyes son problemas abiertos, estrechamente relacionado con el programa de Langlands. Una muy explícita ejemplo es el siguiente: vamos a

$$f(x) = x^3 - x - 1.$$

A continuación, la división de comportamiento de $f(x) \bmod p$ está determinado por la $p^{th}$ coeficiente de forma modular

$$q \prod_{n=1}^{\infty} (1 - q^n) (1 - q^{23n}).$$

Ver este MO pregunta para algunos detalles.

Edit: en este caso en particular, el grupo de Galois es el Klein cuatro grupo de $C_2 \times C_2$, que es abelian. Por el Kronecker-Weber teorema, entonces sabemos que la división de campo de la $f(x) = x^4 - x^2 = 4$ incrusta en algunos cyclotomic campo $\mathbb{Q}(\zeta_n)$, lo que implica que con un número finito de excepciones de los números primos $p$ tal que $f$ tiene una raíz $\bmod p$ son precisamente los números primos en algunos colección finita de progresiones aritméticas con diferencia común $n$. Para averiguar exactamente lo que estas progresiones aritméticas son lo que uno podría necesitar información más específica acerca de la integración en un cyclotomic campo.

Answer 2

Qiaochu da una buena respuesta general. Para este problema en particular, podemos ensuciarnos las manos para determinar si hay una solución.

Como$p>2$, puedes aplicar la fórmula cuadrática para ver que$x^2 = \frac{1}{2}(1 \pm \sqrt{17})$. Ahora, si está trabajando con una gran prima específica$p$, puede usar la reciprocidad cuadrática para determinar si existe$\sqrt{17}$, y luego usar la reciprocidad cuadrática nuevamente para ver si existe una solución$x$.