Mejor respuesta
Primero, debemos observar el módulo (o el número por el que estamos tratando de dividir). En este caso, es 1818. Luego, inserta 1818 en la función totient de Euler , para obtener ϕ (18) ϕ (18). En particular, para todos los enteros nn, tenemos
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
donde el producto pasa por todos los factores primos únicos de nn. Por lo tanto, en este caso,
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Ok, entonces el siguiente paso es el teorema de Euler , que dice que para cualquier otro entero aa que sea primo relativo a nn, tenemos que aa a la potencia ϕ (n) ϕ (n) deja un resto de 11 cuando se divide por nn. Es decir,
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Dado que 1717 es relativamente primo con respecto a 1818, sabemos que 176176 hojas un recordatorio de 1. Esto significa que podemos seguir dividiendo 176176 de 1720017200 sin cambiar el resto. Otra forma de decir esto es que 17 elevado a cualquier potencia que sea múltiplo de 6 dejará un resto de 1. Así que al final, dado que 200 es 2 más que un múltiplo de 6, sabemos que
17200≡172 (mod18) .17200≡172 (mod18).
Esto hace que el problema sea mucho más simple: ¡casi hemos terminado! Un atajo aquí para terminar el problema es darse cuenta de que 1717 deja un resto de −1−1 cuando se divide por 1818 (es decir, 17≡ − 1 (mod18) 17≡ − 1 (mod18)), por lo que 172172 deja un resto de (- 1) 2 = 1. (- 1) 2 = 1.
Entonces, nuestra respuesta es 1 . La próxima vez que tenga un problema relacionado con el resto de una gran potencia, puede utilizar esta agradable solución generalizada y sonar inteligente al mismo tiempo :). Si no ha visto la notación modmod antes, consulte Aritmética modular .
PD Es posible que haya oído hablar de un caso especial de este teorema llamado pequeño teorema de Fermat , que funciona cuando tienes un módulo que «es un número primo (no es el caso aquí). El teorema dice que para cualquier primo pp y un entero aa que no es un múltiplo de pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Este es un truco interesante pero es básicamente lo mismo que lo anterior, ya que ϕ (p) = p − 1ϕ (p) = p − 1 para cualquier pp primo. Este tipo de preguntas se vuelven realmente simples si comprendes el concepto de residuos negativos . Siempre intente reducir el dividendo a 1 o -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Respuesta
Se necesitan antecedentes importantes para resolver el problema :
Sabemos que el resto obtenido cuando r divide pq es producto de los restos obtenidos cuando r divide py q por separado. Esto se llama lema sobre residuos. Puedes probarlo mediante el teorema de la división de Euclides.
La solución
17 cuando se divide por 18 deja el resto -1 (es conveniente trabajar con -1 que con 17)
Aplicando el lema del resto a 17 × 17 × 17 … × 17 (2000 veces) cuando se divide por 18 se obtendrá el resto cuando el los restos individuales se multiplican, es decir, -1 × -1 .. × -1 (2000 veces), el resto es 1 \ blacksquare
Si fuera 17 elevado a algún número impar, el resto sería -1 o 17 .