$$\begin{align*} x^n\equiv1&\pmod p\quad(1)\\ x^n\equiv-1&\pmod p\quad(2)\end{align*}$$
Donde $n\in\mathbb{N}$ , $\quad p\in\text{Primes}$ y $x\in \{0,1,2\dots,p-1\}$ .
¿Cómo podemos encontrar las soluciones para x sin calcular todos los números (de 0 a p-1) de alta potencia n?
O, en otras palabras, ¿cómo encontrar la raíz n-ésima de la unidad (y el negativo de la unidad) utilizando la aritmética modular sin hacer toda la tabla de cálculo?
Dejemos que $p$ sea un primo impar. Para la congruencia $x^n \equiv 1 \pmod{p}$ , dejemos que $g$ sea una raíz primitiva de $p$ . Existen muy buenos algoritmos probabilísticos para encontrar una raíz primitiva de $p$ . Después, todo es fácil.
Dejemos que $d=\gcd(n,p-1)$ . Entonces nuestra congruencia tiene $d$ soluciones incongruentes modulo $p$ . Una solución es $h$ , donde $h \equiv g^{(p-1)/d}\pmod{p}$ . Para conseguirlos todos, miramos $h^t$ , donde $t$ oscila entre $0$ a $d-1$ .
Para la congruencia $x^n \equiv -1\pmod{p}$ En primer lugar, debemos determinar si existe una solución. Hay una solución si y sólo si $(p-1)/d$ está en paz. Una solución es entonces $g^{(p-1)/2d}$ . Las otras soluciones se pueden obtener multiplicando por $n$ -raíces de $1$ .
La primera ecuación es más fácil. La solución se basa en el conocimiento de que $G=\mathbb{Z}/p\mathbb{Z}^*$ es un grupo cíclico de orden $p-1$ . Sea $d=\gcd(n,p-1)$ . En un grupo cíclico de orden $p-1$ el número de soluciones de $x^n=1$ es igual a $d$ . Podemos encontrar estos $d$ soluciones, al menos en teoría, de la siguiente manera. Sea $g$ sea un elemento primitivo es decir, un generador de $G$ Así que $$G=\{g^0=1,g^1,g^2,\ldots,g^{p-2}\}.$$ La solución se basa en que $g^j\equiv 1$ si y sólo si $(p-1)\mid j$ . Así que $x=g^j$ es una solución de la ecuación $x^n=1$ si y sólo si $(p-1)\mid jn$ . Aquí siempre $d\mid n$ por lo que esto se cumple si y sólo si $(p-1)/d \mid j$ . Así, todas las soluciones distintas son $$ g^{j(p-1)/d},\ \text{for}\ j=0,1,\ldots,d-1. $$
La otra ecuación es un poco más complicada. Necesitamos la parte que $-1\equiv g^{(p-1)/2}$ . Esto se deduce de la parte anterior en el sentido de que las soluciones de $x^2=1$ son $x=\pm1$ . Por lo tanto, $x=g^j$ es una solución de $x^n=-1$ si y sólo si $$ nj\equiv (p-1)/2 \pmod{p-1}. $$ Aquí $nj$ es siempre divisible por $d$ que también es un factor del módulo $(p-1)$ . Así que si $d$ no es un factor de $(p-1)/2$ no habrá soluciones. Pero si $d\mid(p-1)/2$ entonces $j=j_0=(p-1)/2d$ es una solución, y, como en el caso de la primera ecuación obtenemos las otras $j_k$ a partir de la fórmula $j_k=j_0+kd$ , $k=1,2,\ldots, d-1.$
Creo que se puede hacer esto utilizando raíces primitivas, pero sólo mencionaré algunos puntos explícitos:
1) Sólo hay que tener en cuenta $n$ para estar entre $1$ y $p-2$ inclusive por el pequeño teorema de Fermat.
2) Los enteros no nulos mod $p$ forman un grupo multiplicativo de orden $p-1$ . El teorema de Lagrange se aplica y nos dice que ningún "no $1$ El número "puede satisfacer $x^n \equiv 1 \bmod p$ para cualquier $n$ coprima a $p-1$ . Así que sólo hay que resolver el problema para las potencias que comparten un factor propio con $p-1$ .
3) El número $1$ resolverá todas las congruencias.
4) La congruencia $x^2 \equiv 1 \bmod p$ tiene exactamente $2$ soluciones, $\pm 1$ como era de esperar.
5) Resolver $x^{\frac{p-1}{2}} \equiv 1 \bmod p$ es lo mismo que encontrar los residuos cuadráticos mod $p$ por el criterio de Euler.
6) Las soluciones a $x^m \equiv 1 \bmod p$ serán todas soluciones a $x^{mn} \equiv 1 \bmod p$ para cualquier $n$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
