Debe aplicar el teorema de Fermat “pequeño”, que dice que si p es primo, entonces x ^ p y x tienen el mismo resto cuando se divide por p (y 19 es primo). Por lo tanto, dado que 100 = 19 × 5 + 5, 10 ^ 100 tiene el mismo resto que 10 ^ 10
Ahora aplico otro truco. Tomo la representación binaria del exponente 10, 1010 y reemplazo 1 con SM, 0 con S: SM S SM S.
S significa cuadrado, M significa multiplicar por 10; y cada vez tomo el resto de la división por 19. Comienzo con 1 y hago: SMSSMS
1 S = 1
- Cómo encontrar el resto cuando [matemática] 17 ^ {17} [/ matemática] se divide por [matemática] 29 [/ matemática]
- ¿Por qué los matemáticos hacen ilegalmente una solución raíz real para esta ecuación diofantina no solucionable [matemática] (n ^ 5 – m ^ 5 = nm ^ 4) [/ matemática], donde (n, m) son enteros coprimos positivos?
- ¿Cuántos pares de enteros positivos satisfacen la ecuación 5 / y + 1 / x = 1/15?
- Asumiendo que la conjetura de Goldbach es cierta, ¿cuáles son las implicaciones metafísicas de que los números primos son los bloques de construcción de los enteros?
- ¿Cuál es la menor [matemática] n [/ matemática] de modo que la expansión decimal de [matemática] \ frac {m} {n} [/ matemática] tenga un período superior a 100 para enteros positivos [matemática] m [/ matemática] y [matemáticas] n [/ matemáticas]?
1 M = 10
10 S = 100 = 5
5 S = 25 = 6
6 M = 60 = 3
3 S = 9
Entonces el resultado es 9 (como han dicho otros).
¿Por qué funciona el truco S / M? El procedimiento puede explicarse recursivamente de la siguiente manera:
- si n es par, n = 2m, entonces x ^ n = (x ^ m) ^ 2
- si n es impar, n = 2m + 1, entonces x ^ n = (x ^ m) ^ 2 × x
- ¿Cómo calculo la representación binaria? Si n es par, apilo un 0 y divido n entre 2; si n es impar, apilo un 1 y divido n-1 entre 2. Hasta que obtenga 0. Entonces, con la expansión binaria del exponente, simplemente transformo una llamada recursiva en una operación en línea.
(Reconozco que la explicación puede ser un poco difícil, y no proporcioné una prueba del pequeño teorema de Femat, que sin embargo es fácil, por ejemplo, por inducción, usando la expansión binomial).