¿Cuál es el resto cuando 17 ^ 17 ^ 17 ^ 17 se divide por 100?
La exponenciación es “asociativa a la derecha”, lo que significa 17 ^ 17 ^ 17 ^ 17 significa 17 ^ (17 ^ (17 ^ 17)). ¡Ese es un número realmente grande! Más sobre cómo lidiar con eso más tarde …
Pero primero, me gustaría contarles sobre la función totient , generalmente denotada por la letra griega phi, [math] \ varphi [/ math]. Puedes considerarlo como el número de coprimos adecuados para un número dado; la cantidad de números más pequeños que no comparten ningún factor primo con ese número. Por ejemplo, [math] \ varphi (100) = 40 [/ math] porque hay 40 números positivos menores que 100 que no comparten ningún factor primo con 100, es decir, 1, 3, 7, 9, 11, 13, 17, 19, etc. Esto es realmente importante porque las potencias de 17 (mod 100) se alternan entre estos coprimos a 100. Cuando observa la secuencia de potencias de 17 (mod 100), puede encontrar que las 40 coprimas a 100 aparecen en esa secuencia, o puede encontrar que la mitad de ellos aparecen, pero lo importante es que 17 ^ 40 será equivalente a 17 ^ 0 (mod 100) porque se quedará sin coprimes y tendrá que comenzar de nuevo .
Entonces eso significa que si quieres saber qué es 17 ^ x (mod 100) yx es un número realmente enorme, solo tienes que averiguar x mod 40, llámalo y, y luego 17 ^ x es equivalente a 17 ^ y (mod 100).
- ¿Es posible explicar la conjetura de Riemann a un laico?
- Dos enteros positivos a y b son tales que a + b = a / b + b / a. ¿Cuál es el valor de a ^ 2 + b ^ 2?
- ¿Cómo pruebo que la suma de todos los números que son menores que ‘n’ y son primos para ‘n’, son iguales a ‘n’? ‘n’ es cualquier número natural.
- ¿9 + 10 = 21?
- ¿Cuál es la relación entre la geometría algebraica y la teoría de números?
Entonces, para recapitular lo que hemos visto hasta ahora …
17 ^ (gran número) (mod 100) es un problema realmente difícil, pero es más fácil si comprende que es equivalente a 17 ^ (gran número mod 40) (mod 100).
Y en nuestro caso, ese gran número es 17 ^ (17 ^ 17). Entonces necesitamos encontrar 17 ^ (17 ^ 17) (mod 40). ¿Como hacemos eso? El mismo método [math] \ varphi (40) [/ math] = 16, porque los números positivos más pequeños y coprimos a 40 son el mismo grupo de números que antes, solo los primeros 16 de ellos. El hecho de que [math] \ varphi (40) [/ math] sea 16 es un verdadero golpe de suerte, porque significa que 17 ^ 17 (mod 40) es equivalente a 17 ^ 1 (mod 40), y entonces 17 ^ ( 17 ^ 17) es equivalente a 17 ^ 17 es equivalente a 17 (mod 40).
Ahora, ¿recuerdas nuestro problema realmente difícil, 17 ^ (gran número) (mod 100)? Necesitábamos encontrar el equivalente de ese gran número, mod 40, y ahora lo tenemos. 17 ^ (17 ^ 17) es equivalente a 17 (mod 40), entonces 17 ^ (gran número) (mod 100) es equivalente a 17 ^ 17 (mod 100), y eso lo podemos hacer a mano …
Le mostraré cómo encontrar [matemáticas] 17 ^ {17} [/ matemáticas] [matemáticas] (\ rm mod ~ 100) [/ matemáticas] utilizando el método de “cuadratura sucesiva”.
Primero, convierta el exponente, [math] 17 [/ math], a binario. El resultado es [math] \ bbox [# CFC, 2px] {10001} [/ math].
Pondremos el número [math] \ bbox [# FCC, 2px] {1} [/ math] en nuestra “calculadora” (se muestra en [math] \ bbox [# FCC, 2px] {\ rm pink} [/ matemáticas]). En este proceso, seguiremos cuadrando el número en nuestra calculadora y posiblemente multiplicando el número por nuestra base, [matemática] 17 [/ matemática], (o no, dependiendo de los bits de nuestro exponente) hasta que tengamos el resultado final .
Verá, usaremos nuestro exponente binario (que se muestra en [math] \ bbox [# CFC, 2px] {\ rm green} [/ math]) como un programa de computadora. Lo leeremos de izquierda a derecha, y para cada bit “1”, elevaremos al cuadrado el número en nuestra calculadora y luego lo multiplicaremos por [matemáticas] 17 [/ matemáticas]. Para cada bit “0”, simplemente elevaremos al cuadrado el número en nuestra calculadora.
Comenzando con [math] \ bbox [# FCC, 2px] {1} [/ math] en nuestra calculadora, y leyendo nuestra cadena de bits como un programa de computadora …
El primer bit es [math] \ bbox [# CFC, 2px] {1} [/ math] bit, así que cuadrátelo, luego multiplíquelo por [math] 17 [/ math] [math] (\ rm mod ~ 100) [/ matemática], que resulta en [matemática] \ bbox [# FCC, 2px] {17} [/ matemática].
El segundo bit es [matemático] \ bbox [# CFC, 2px] {0} [/ matemático] bit, así que cuadrátelo [matemático] (\ rm mod ~ 100) [/ matemático], resultando en [matemático] \ bbox [# FCC, 2px] {- 11} [/ matemáticas].
El siguiente bit es [math] \ bbox [# CFC, 2px] {0} [/ math] bit, así que cuadre [math] (\ rm mod ~ 100) [/ math], lo que resulta en [math] \ bbox [# FCC, 2px] {21} [/ matemáticas].
El siguiente es [math] \ bbox [# CFC, 2px] {0} [/ math] bit, así que cuadre [math] (\ rm mod ~ 100) [/ math], lo que resulta en [math] \ bbox [#FCC , 2px] {41} [/ matemáticas].
… Luego [math] \ bbox [# CFC, 2px] {1} [/ math] bit, así que cuadra, luego multiplica por [math] 17 [/ math] [math] (\ rm mod ~ 100) [/ math ], lo que resulta en [math] \ bbox [# FCC, 2px] {- 23} [/ math], que es equivalente a [math] \ bbox [# FCC, 2px] {77} [/ math].
Entonces el resultado final es: [matemáticas] \ boxed {17 ^ {17 ^ {17 ^ {17}}} \ equiv 17 ^ {17} \ equiv 77 ~ (\ rm mod ~ 100)} [/ math].