Hay un par de formas de resolver esto. (Por cierto, en caso de que no esté familiarizado con la notación con respecto a la aritmética modular, [math] a \ equiv {b} \ pmod {c} [/ math] solo significa que [math] a = ck + b [/ math] , para algunos [matemática] k [/ matemática], o en otras palabras, que [matemática] a [/ matemática] tiene un resto de [matemática] b [/ matemática] cuando se divide por [matemática] c [/ matemática]. )
Opción 1:
Simplemente observe que [matemáticas] 2 ^ 3 = 8 \ equiv1 \ pmod7 [/ matemáticas]. Podemos utilizar fácilmente este hecho para nuestra ventaja:
[matemáticas] 2 ^ {48} \ equiv (2 ^ 3) ^ {16} \ equiv1 ^ {16} \ equiv1 \ pmod7 [/ matemáticas]
- Hipotéticamente, solo suponiendo ZF (C), ¿cuánto duraría la prueba completa del último teorema de Fermat?
- ¿Cómo se puede demostrar matemáticamente que, si n y k son enteros positivos, entonces [matemática] \ lceil {\ frac {n} {k}} \ rceil = \ lfloor {\ frac {n-1} {k}} \ rfloor +1 [/ matemáticas]?
- ¿Por qué la función de estimación primaria de ejemplo cuenta menos los compuestos?
- ¿Cómo demostró Euler la conexión entre los números primos y la función Zeta de Riemann?
- Cómo comenzar a aprender teoría de números
Así [matemáticas] \ boxed {2 ^ {48} \ equiv \ pmod7} [/ math].
Pero … ¿y si tal vez no te diste cuenta de esto? Bueno, eso nos lleva a
Opcion 2:
Existe un teorema llamado El pequeño teorema de Fermat , y puede sernos de gran utilidad en este problema.
El pequeño teorema de Fermat (o FLT, que no debe confundirse con el último teorema de Fermat) dice que [matemáticas] a ^ p \ equiv {a} \ pmod {p} [/ matemáticas], donde [matemáticas] p [/ matemáticas] es un principal. Si [matemática] a [/ matemática] y [matemática] p [/ matemática] son relativamente primos, entonces podemos “dividir” [matemática] a [/ matemática] en esta congruencia para obtener esa [matemática] a ^ {p -1} \ equiv1 \ pmod {p} [/ math].
Ahora, eso es algo que definitivamente podría ser útil para nosotros, ya que estamos tratando de encontrar el resto de algo cuando se divide por un primo, 7. Entonces, en nuestro caso, [matemáticas] p = 1 [/ matemáticas] y [matemáticas] a = 2 [/ math] (queremos ver solo [math] 2 [/ math], y trataremos los exponentes más adelante). Debido a que [matemáticas] 2 [/ matemáticas] y [matemáticas] 7 [/ matemáticas] son relativamente primos, tenemos que:
[matemáticas] 2 ^ {7-1} \ equiv2 ^ 6 \ equiv1 \ pmod7 [/ matemáticas].
Bueno, esto es inmensamente útil, ya que [matemáticas] 48 [/ matemáticas] es divisible por [matemáticas] 6 [/ matemáticas]. Ahora podemos ver que:
[matemáticas] 2 ^ {48} \ equiv (2 ^ 6) ^ 8 \ equiv1 ^ 8 \ equiv1 \ pmod7 [/ matemáticas].
Y entonces hemos encontrado que [math] \ boxed {2 ^ {48} \ equiv1 \ pmod7} [/ math].
Sin embargo, vayamos un paso más allá en términos de hablar sobre formas de encontrar restos.
Es posible que se haya estado preguntando si existe o no una fórmula de algún tipo similar al Pequeño Teorema de Fermat para cuando estamos dividiendo por números que no son primos. Y resulta que hay, llamado Teorema de Euler . Es esencialmente una forma generalizada de FLT.
El teorema de Euler dice que para algunos [matemática] a [/ matemática] y [matemática] n [/ matemática], tal que [matemática] a [/ matemática] y [matemática] n [/ matemática] son relativamente primos, [matemática] a ^ {\ phi (n)} \ equiv1 \ pmod {n} [/ math].
Esa cosa [math] \ phi (n) [/ math] se llama función phi de Euler , también conocida como función totient de Euler , y genera el número de enteros positivos menores que [math] n [/ math] que son relativamente primos para [ matemáticas] n [/ matemáticas].
Hay una fórmula para calcular [math] \ phi (n) [/ math] (no voy a derivarla en esta respuesta, aunque leas más sobre esto aquí). Deje [math] n = {p_1} ^ {k_1} {p_2} ^ {k_2} \ dots {p_m} ^ {k_m} [/ math] (esto es solo la factorización prima de [math] n [/ math]) . Entonces:
[matemáticas] \ phi (n) = n \ left (1- \ dfrac {1} {p_1} \ right) \ left (1- \ dfrac {1} {p_2} \ right) \ dots \ left (1- \ dfrac {1} {p_m} \ right) [/ math].
Esta fórmula nos permite calcular [math] \ phi (n) [/ math], lo que a su vez nos permite descubrir el exponente en [math] a ^ {\ phi (n)} \ equiv1 \ pmod {n} [ /matemáticas].
Ahora, veamos el caso donde [math] n [/ math] es primo, que llamaremos [math] p [/ math]. Usando la fórmula anterior (y debido a que la factorización prima de [math] p [/ math] es solo [math] p [/ math]), podemos encontrar que:
[matemáticas] \ phi (p) = p \ left (1- \ dfrac {1} {p} \ right) = p \ left (\ dfrac {p-1} {p} \ right) = p-1 [/ matemáticas].
(Alternativamente, podríamos haber notado que debido a que hay [math] p-1 [/ math] enteros positivos menores que [math] p [/ math] y cada entero positivo menor que un primo debe ser relativamente primo para él, [ matemática] \ phi (p) = p-1 [/ matemática].)
¿Qué sucede si conectamos esto con el teorema de Euler? Al hacerlo, encontramos que para [matemática] a [/ matemática] relativamente primo para [matemática] p [/ matemática], [matemática] a ^ {p-1} \ equiv1 \ pmod {p} [/ matemática]. ¡Este es el pequeño teorema de Fermat! Así podemos ver cómo FLT es realmente solo un caso especial del Teorema de Euler.
Pero de todos modos, sí, [matemáticas] 2 ^ {48} [/ matemáticas] tiene un resto de [matemáticas] 1 [/ matemáticas] cuando se divide por [matemáticas] 7 [/ matemáticas].