Del pequeño teorema de Fermat, si [matemática] a, b [/ matemática] son números coprimos, [matemática] a ^ {\ varphi (b)} \ equiv1 \ bmod b [/ matemática], de la cual [matemática] a ^ {q \ cdot \ varphi (b) + r} \ equiv a ^ r \ bmod b [/ math].
También para [math] a, b [/ math] coprime: [math] \ varphi (a \ cdot b) = \ varphi (a) \ cdot \ varphi (b) [/ math], y para [math] p [ / matemáticas] primo: [matemáticas] \ varphi (p ^ k) = (p-1) p ^ {k-1} [/ matemáticas].
Primero, tenemos la factorización prima de [math] 2400 [/ math]:
[matemáticas] 2400 = 2 ^ 5 \ cdot3 \ cdot5 ^ 2 [/ matemáticas]
- ¿Qué pasos debo seguir para estudiar la secuencia de Fibonacci en profundidad?
- ¿Cuál es el conjugado de (a + b) y (b + a)?
- ¿Por qué se requiere el axioma de elección para conjuntos infinitos, pero no finitos?
- Mi ciudad contiene 100 edificios. Están numerados del 1 al 100. ¿Cuántos 6 se usan en estos números?
- ¿Podemos crear un nuevo lenguaje o sistema basado en la lógica además de las matemáticas? ¿Como podríamos hacerlo?
Donde [math] \ varphi (2 ^ 5) = 16 [/ math], [math] \ varphi (3) = 2 [/ math] y [math] \ varphi (5 ^ 2) = 20 [/ math] .
Resolviendo para [matemáticas] 2 ^ 5 [/ matemáticas] :
[matemáticas] 7 ^ {99} = 7 ^ {6 \ cdot16 + 3} \ equiv7 ^ 3 \ bmod2 ^ 5 [/ matemáticas], donde [matemáticas] 7 ^ 3 = 343 = 10 \ cdot32 + 23 [/ matemáticas] , entonces [matemáticas] 7 ^ {99} \ equiv23 \ bmod2 ^ 5 [/ matemáticas].
Esto significa que el recordatorio de [matemáticas] 7 ^ {99} \ bmod2400 [/ matemáticas] está en el conjunto [matemáticas] 23, 55, 87, 119, 151, 183, \ ldots [/ matemáticas] (hay 75 posibles resultados)
(Tenga en cuenta que todos los resultados posibles son impares)
Resolviendo para [matemáticas] 3 [/ matemáticas] :
[matemáticas] 7 ^ {99} = 7 ^ {49 \ cdot2 + 1} \ equiv7 \ bmod3 [/ matemáticas], donde [matemáticas] 7 = 2 \ cdot3 + 1 [/ matemáticas], entonces [matemáticas] 7 ^ { 99} \ equiv1 \ bmod3 [/ math].
Esto significa que el recordatorio de [math] 7 ^ {99} \ bmod2400 [/ math] está en el conjunto [math] 1, 4, 7, 10, 13, 16, \ ldots [/ math] (hay 800 posibles resultados)
Resolviendo para [matemáticas] 5 ^ 2 [/ matemáticas] :
[matemáticas] 7 ^ {99} = 7 ^ {5 \ cdot20-1} [/ matemáticas], donde [matemáticas] 7 ^ {99} \ cdot7 \ equiv1 \ bmod5 ^ 2 [/ matemáticas]. Dado [matemática] 18 \ cdot7 = 126 = 5 \ cdot25 + 1 [/ matemática], esto significa [matemática] 18 \ cdot7 \ equiv1 \ bmod5 ^ 2 [/ matemática], o, en otras palabras: [matemática] 7 ^ {99} \ equiv18 \ bmod5 ^ 2 [/ math].
Esto significa que el recordatorio de [math] 7 ^ {99} \ bmod2400 [/ math] está en el conjunto [math] 18, 43, 68, 93, 118, 143, \ ldots [/ math] (hay [math ] 96 [/ matemáticas] posibles resultados)
(Tenga en cuenta que todos los resultados posibles terminan en [matemáticas] 3 [/ matemáticas] o [matemáticas] 8 [/ matemáticas] )
Si vemos ambas notas, entonces el recordatorio termina en 3. Esto reduce la cantidad de números a comparar: debe terminar en [matemáticas] 43 [/ matemáticas] o [matemáticas] 93 [/ matemáticas].
Entonces, desde el primer conjunto, tenemos [matemática] 23 [/ matemática], [matemática] 183 [/ matemática], y seguimos agregando [matemática] 160 [/ matemática] para obtener: [matemática] 343 [/ matemática] (*), [matemáticas] 503 [/ matemáticas], [matemáticas] 663 [/ matemáticas], [matemáticas] 823 [/ matemáticas], [matemáticas] 983 [/ matemáticas], [matemáticas] 1143 [/ matemáticas] (* ), … y, si somos buenos observadores, podemos saltar a, [matemáticas] 1943 [/ matemáticas] (*)
Sin embargo, [math] 1143 \ equiv0 \ bmod3 [/ math] y [math] 1943 \ equiv2 \ bmod3 [/ math], solo [math] 343 \ equiv1 \ bmod3 [/ math].
Entonces esa es la respuesta.
[matemáticas] 7 ^ {99} \ equiv \ boxed {\ large343} \ bmod2400 [/ math].
Observación: [matemáticas] 343 = 7 ^ 3 [/ matemáticas], entonces [matemáticas] 7 ^ {99} \ equiv7 ^ {3} \ bmod2400 [/ matemáticas]. Esto significa [matemáticas] 7 ^ {96} \ equiv1 \ bmod2400 [/ matemáticas]. Este resultado se espera para [matemáticas] 2 ^ 5 [/ matemáticas] y [matemáticas] 3 [/ matemáticas], ya que 96 es múltiplo de 16 ([matemáticas] \ varphi (2 ^ 5) [/ matemáticas]) y 2 ( [matemáticas] \ varphi (3) [/ matemáticas]).
Entonces, tenemos [matemáticas] 7 ^ {96} \ equiv7 ^ {100} \ bmod5 ^ 2 [/ matemáticas], que significa [matemáticas] 1 \ equiv7 ^ 4 \ bmod5 ^ 2 [/ matemáticas].
De hecho, [matemáticas] 7 ^ 4 = 49 ^ 2 = 2401 \ equiv1 \ bmod25 [/ matemáticas]. Al darse cuenta de esto, la solución del problema habría sido mucho más corta.
