Encontrar todas las soluciones de la congruencia $x^3\equiv 1 {\pmod{77}}$

Question

Encontrar todas las soluciones de la congruencia $x^3\equiv 1 \pmod{77}$

Fui capaz de hacer esto para $x^2 \equiv 1\pmod{77}$ ya que $x$ o ser $1$ o $-1$, en cada uno de los $\bmod 7$ y $\bmod 11$. No sé qué $x$ sería en este caso.

Puedo hacer el Teorema chino del resto para encontrar la respuesta final.

Answer 1

Para primera $p, \mathbb Z_p^\times$ es cíclico un grupo de orden $p-1$

Supongamos, $x^a \equiv 1 \mod p$

Entonces ${x, x^2, \cdots , x^{a-1}}$ forma un subgrupo y la orden del subgrupo debe dividir $(p-1)$

Desde $3$ no divide $10$

La única solución para: $x^3 \equiv 1\pmod {11}$ es el trivial $x \equiv 1\pmod {11}$

Pero dividir a $3$ $6$

tiene de $x^3 \equiv 1 \pmod 7$ $3$ solutions (incluyendo $x = 1$)

Si encuentras una solución no trival entonces $x^2$ es también una solución.

Answer 2

Es de suponer que usted sabe que Fermat poco teorema (FLT) dice que para el primer módulo de $p$ $a$ coprime a $p$ tenemos $a^{p-1}\equiv 1 \bmod p$.

Esto también significa que si tenemos $a^k \equiv 1 \bmod p$, e $k$ es el menor entero positivo para el cual esto es cierto ($k$ es el orden de $a \bmod p$), $k$ divide $p{-}1$ - ya que de lo contrario FLT no.

Esto significa que no podemos tener cualquiera de estos elementos para$p=11$$k=3$, ya que el $3 \nmid 10$. Por lo $x^3\equiv 1 \bmod 11$ tiene una única solución, $x\equiv 1 \bmod 11$, ya que sólo $1$ divide tanto a a$3$$10$.

Por contraste $3\mid (7-1) $, por lo que debe haber tres soluciones (incluyendo $1$), y $7$ es lo suficientemente pequeño como para buscar, caso por caso, incluso si $7+1=8=2^3$ no ocurra. La otra raíz cúbica es $2^2 = 4$, el cual es evidente sin más multiplicando-desde $4^3=2^6\equiv 1^2\equiv 1 \bmod 7$.

Answer 3

Como a menudo en la aritmética modular, la mayoría de enfoque natural es a través del teorema del Resto Chino, que le da un isomorfismo de anillos de $\mathbf Z/77 \cong \mathbf Z/7 \times \mathbf Z/11 $, que a su vez induce un isomorfismo de grupos multiplicativos $(\mathbf Z/77)^* \cong (\mathbf Z/7)^* \times (\mathbf Z/11)^* $ entre los correspondientes grupos de invertible elementos. Para un determinado prime $p$, el grupo de $(\mathbf Z/p)^*$ es clásicamente conocido por ser cíclico de orden $(p-1)$ (esta es la versión exacta de FLT) y, en consecuencia, para un divisor $q$$(p-1)$, los elementos de orden $q$ $(\mathbf Z/p)^*$ constituyen el único subgrupo de orden $q$, la cual es generada por $[y]^\frac {p-1}q$ si $[y]$ es un generador de $(\mathbf Z/p)^*$. Aquí $q=3$ divide $6$ y no divide $10$, lo $x^3\equiv 1$ mod $77$ fib $x\equiv 1$ mod $11$ $x\equiv z^2$ mod $7$, $[z]$ ser un generador de $(\mathbf Z/7)^*$. Usted puede adivinar y comprobar que $[x]=[2]$ va a hacer, pero como un procedimiento general, se podría volver a utilizar la CRT, que le da un isomorfismo de grupos multiplicativos grupos $C_6 \cong C_2 \times C_3 $, por lo tanto ${C_6}^2 \cong C_3 $ porque $2$ $3$ son coprime.

Answer 4

Como una solución a $x^2 \equiv 1 \mod 77$ que debería haber recibido

$x \equiv \pm 1 \mod 7$ $x \equiv \pm 1 \mod 11$ . Como este es de CUATRO sistemas de ecuaciones de cada sistema de ecuaciones debe haber rendido una única solución.

Sistema 1: $x \equiv 1\mod 7$ $x \equiv 1 \mod 11$ rendimientos $x \equiv 1 \mod 77$.

Sistema 2: $x \equiv 1 \mod 7$ $x \equiv -1 \mod 11$ rendimientos $x \equiv 43 \mod 77$. Y $43^2 = 24*77 + 1$.

Sistema 3: $x \equiv -1 \mod 7$ $x \equiv 1 \mod 11$ rendimientos $x \equiv 34 \mod 77$. Y $34^2 = 15*77 + 1$.

Sistema 4: $x \equiv -1 \mod 7$ $x \equiv - 1 \mod 11$ rendimientos $x \equiv 76\equiv -1 \mod 77$.

====

Para $x^3 = 1 \mod 77$.

Para solucionar $x^3 \equiv 1 \mod 7$. Tenga en cuenta que si $x\not \equiv 0$ $x^6 \equiv 1 \mod 7$ $(x^2)^3 \equiv 1 \mod 7$ si $x \equiv (\pm 1)^2,(\pm 2)^2, (\pm 3)^2 \equiv 1, 4, 2 \mod 7$$x^3 \equiv 1 \mod 7$.

Para solucionar $x^3 \equiv 1 \mod 11$, ten en cuenta que $\phi(11) = 10$. $\gcd(3,10) = 1$. Para $x^k \equiv 1 \mod 11$ $x\equiv y^j$ algunos $j$$10|j*k$. Eso sólo puede suceder si $k = 10$ o $k < 10$$j=10$. Por lo $x \equiv 1 \mod 11$ es la única solución a $x^3 \equiv 1 \mod 11$.

Así que tenemos $3$ sistemas de ecuaciones.

$x \equiv 1 \mod 7$ $x\equiv 1 \mod 11$ rendimientos $x \equiv 1 \mod 77$.

$x \equiv 2 \mod 7$ $x \equiv 1 \mod 11$ rendimientos $x\equiv 23 \mod 77$. Y $23^3 = 12167 = 1 + 158*77$.

$x \equiv 4 \mod 7$ $x \equiv 1 \mod 11$ rendimiento $x \equiv 67 \mod 77$. Y $67^3 \equiv (-10)^3 \equiv -1000 + 770 \equiv -230 + 385 \equiv 155 - 154 \equiv 1 \mod 77$.