¿Cómo decidir qué módulos comprobar al resolver una congruencia "polinómica"?

Question

Considere el siguiente problema:

Encontrar todas las soluciones enteras de $y^2 = x^5 - 4$ .

La solución es algo así como - comprobar el módulo 11, donde $x^5 \equiv 0, \pm 1$ y luego comprobar los casos para llegar a la conclusión de que no existe ninguna solución. He pensado en comprobar el mod 11 a partir de El pequeño teorema de Fermat obtenemos $x^{10} \equiv 1 \pmod{11}$ pero realmente fue un golpe de suerte.

Mi pregunta es: ¿cómo se puede decidir qué módulos comprobar cuando hay que enfrentarse a una congruencia "polinómica"?

Answer 1

Deberías comprobar el módulo $p=\text{lcm}(a_1,a_2,\ldots,a_n)+1$ si es primo (aquí $a_1,a_2,\ldots,a_n$ son los grados de las variables). La razón por la que esto puede funcionar fácilmente es: por FLT (si $p\nmid x$ ) $$x^{\text{lcm}(a_1,a_2,\ldots,a_n)}\equiv 1\pmod {\!p}$$

y $a_ik_i=\text{lcm}(a_1,a_2,\ldots,a_n)$ para algunos pequeños $k_i$ ( $\forall i\in\{1,\ldots,n\}$ ) (Digo "pequeño" porque estamos tomando $\text{lcm}$ en lugar de, por ejemplo, multiplicarlas todas).

$(x^{a_i})^{k_i}\equiv 1\pmod{\!p}$ tiene como máximo $k_i$ soluciones en términos de $x^{a_i}$ (véase el teorema siguiente). $k_i$ es pequeño, por lo que $x^{a_i}$ sólo puede ganar una pequeña cantidad ( $\le k_i+1$ cuando $p\nmid x$ se elimina la restricción) de restos $\bmod p$ .

Teorema: un polinomio de grado $n$ tiene como máximo $n$ ceros $\bmod p$ .

Prueba: $ax\equiv b\pmod {\!p}$ tiene una solución. Supongamos que cualquier polinomio de grado $n-1$ tiene como máximo $n-1$ raíces. Consideremos un polinomio arbitrario $f$ de grado $n$ . Si no tiene ceros, hemos terminado. En caso contrario (que la raíz sea $a$ ) podemos escribir $f$ como $f(x)=(x-a)g(x)$ , donde $g$ es un polinomio de grado $n-1$ . $f$ entonces debe tener como máximo $1+(n-1)=n$ ceros. $\ \ \ \square$

Ejemplo: (Baltic Way 2012) Resuelve en números enteros: $2x^6+y^7=11$ .

Solución: $2x^6\equiv\{2,8,22,27,32,39,42\}$ ( WA ), $y^7\equiv\{1,6,7,36,37,42\} \pmod{\!43}$ ( WA ).

Así que $2x^6+y^7\not\equiv 11\pmod {\!43}$ y la igualdad no puede ser satisfecha. $\ \ \ \square$

Answer 2

Obsérvese que por las propiedades de los símbolos de Legendre tenemos $$ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \equiv x \pmod p $$ donde $x$ sólo puede ser $-1$ , $0$ o $1$ . Por eso, si tienes un $n$ -en una ecuación diofantina y $2n+1$ es primordial, entonces tienes mucha suerte, aunque no es una suposición extraña xd