La solución de $x^{17}=17$ modulo 23

Question

Solucionar $x^{17}=17$ modulo 23.

He tratado de fuerza bruta (la única solución es de 10), pero quiero preguntar si hay alguna literatura o el método de resolución de este tipo de pregunta, en particular, como $x^p=a$ modulo $q$.

Answer 1

Supongamos $x^{17} \equiv 17 \mod 23$, $x^{17k} \equiv 17^k \mod 23$ todos los $k \geq 1$. Ahora, elija $k$ tal que $17k \equiv 1 \mod 22$, que se ve fácilmente ser $k= 13$.(Fácilmente, en la que seguimos tratando de $22l+1$ de divisibilidad por $17$, y su fácil seguir sumando $22$ y la comprobación de la divisibilidad, en lugar de ir a por Euclides del método aquí).

De ello se desprende que $x^{17 \times 13} \equiv 17^{13} \mod 22$, pero, a continuación, $x^{17 \times 13} \equiv x^{22 \times 10 + 1} \equiv x \mod 23$ por Fermat poco teorema, por lo que tenemos $x \equiv 17^{13} \mod 23$.

Es una cuestión de cálculo de $17^{13} \mod 23$, a la que habremos de hacer por repetir la cuadratura.

$17^2 = 289 \equiv 13 \mod 23$, $17^4 \equiv 169 \equiv 8 \mod 23$, $17^8 \equiv 64 \equiv 18 \mod 23$.

Así , la respuesta es : desde $13 = 8+4+1$,$18 \times 8 \times 17 \equiv -5 \times -6 \times 8 \equiv 240 \equiv 10 \mod 23$.

EDIT : Si usted desea solucionar $x^3 \equiv 3 \mod 73$, entonces esto tiene una complicación, es que no existe la $k$ tal que $3k \equiv 1 \mod 72$, por lo que no podemos criar a nuestros congruencia a tal poder y obtener un resultado positivo.

Lo que no podemos decir, es que si hay una solución o no, y si es que es único. Afortunadamente, podemos hacer un poco de "pequeño de los múltiplos y los pequeños cubos" de la introspección, y entonces no es difícil ver que $-6$ es realmente una solución, ya que la $(-6)^3 = -216$$71 \times -3 = -213$. Por supuesto, esta es sólo una heurística, porque no todos los problemas tienen una solución pequeña, o incluso una solución para el caso.

No puedo saber si hay otras soluciones sin tener el tiempo suficiente, la verdad.

En general, creo que este problema se denomina el problema del logaritmo discreto.Por lo que sé, este pertenece(en general) a una dura clase de problemas en ciencias de la computación. De hecho, hay algoritmos (generalmente para la fabricación de códigos) que hacen uso del hecho de que este problema es difícil. Así que yo, personalmente, creo que este problema es ser agrietado caso-por-caso : usted tiene que mirar en el problema dado, y ver lo que es especial acerca de los números dados es decir, es el módulo principal, es el exponente co-prime para el módulo de menos uno, etc. Si alguien tiene una solución general a este problema que lleva poco tiempo, espero que sea una gran cosa.

Answer 2

Por Fermat Poco Teorema $x^{22} \equiv 1 \mod 23$

Así que si $17*m \equiv 1 \mod 22$

Por lo $x^{17} \equiv 17 \mod 23 \implies$

$(x^{17m} \equiv x \equiv 17^m \mod 23 $

Así que vamos a solucionar $17*m \equiv 1 \mod 22$.

Utilizamos el Algoritmo de Euclides:

$22 = 17 + 5$

$17 = 3*5 + 2$

$5 = 2*2 + 1$

$1 = 5 - 2*2=$

$(22-17) - 2(17- 3*5) = (22-17) - 2(17 - 3(22 - 17)) = 7*22 - 9*17$

Por lo $7*22 - 9 *17 1$ $-9*17 \equiv 1\mod 22$

Por lo $13*17 \equiv 1 \mod 22$.

Por lo $x^17\equiv 17 \mod 23 \implies$

$(x^{17})^{13} \equiv 17^{13} \mod 23$

$ x\equiv 17^{13} \mod 23$

$17^{22} \equiv 1 \mod 23$$17^{11} \equiv \pm 1 \mod 23$$17^{13} \equiv \pm 17^2 \mod 23$.

$17^2 \equiv (-6)^2 \equiv 36 \equiv 13 \mod 23$

$17^4 \equiv 13^2 \equiv (-10)^2 \equiv 100 \equiv 8 \mod 23$

$17^8 \equiv 8^2 \equiv 64 \equiv 18 \mod 23$

$17^{12} \equiv 8*18 \equiv 144 \equiv 6 \equiv -17 \mod 23$.

Por lo $17^{11} \equiv -1 \mod 23$, después de todo.

Por lo $17^{13}\equiv 17^{11}*17^2 \equiv -13 \equiv 10 \mod 23$.

Por lo $x^17 \equiv 17 \mod 23 \implies x\equiv 10 \mod 23$