¿Cuál es el resto cuando [matemáticas] 2 ^ {2016} [/ matemáticas] se divide por [matemáticas] 13 [/ matemáticas]?

Creo que una estrategia general sería de gran utilidad aquí ya que la base (= 2), el módulo (= 13) y el exponente (= 2016) se pueden cambiar y los atajos tienden a no funcionar en todos los casos. Lo que necesita saber es la exponenciación rápida con un módulo también conocido como exponenciación por cuadratura.

La fórmula general es:

Usando esta fórmula, cualquier pregunta puede resolverse en tiempo O ([math] \ log (n) [/ math]).

Aquí hay un tutorial sobre la multiplicación rápida de módulos (cuadratura exponencial).

Para leer más: Exponenciación por cuadratura

En cuanto a la respuesta numérica a la pregunta, es:

[matemáticas] 2 ^ {2016} \ hspace {1cm} MOD \ hspace {1cm} 13 \ hspace {1cm} = \ hspace {1cm} 1 [/ math]

¡Espero que esto ayude! 🙂

Arpit Gupta

El pequeño teorema de Fermat:

Si [math] a \ in \ Z [/ math] y [math] p [/ math] es primo, entonces [math] a ^ {p-1} \ equiv 1 \ mod p [/ math]

[matemáticas] \ implica 2 ^ {12} \ equiv 1 \ mod 13 [/ matemáticas]

[matemáticas] \ implica (2 ^ {12}) ^ {168} \ equiv 1 ^ {168} \ mod 13 [/ matemáticas]

[matemáticas] \ implica 2 ^ {2016} \ equiv \ boxed {1} \ mod 13 [/ matemáticas]

Podemos resolver de esta manera,

[matemáticas] 2 ^ 6 \ equiv -1 mod (13) [/ matemáticas]

[matemática] \ Rightarrow [/ matemática] [matemática] (2 ^ {6}) ^ {336} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] (-1) ^ {336} [/ matemática ] [matemáticas] mod [/ matemáticas] [matemáticas] (13) [/ matemáticas]

[matemática] \ Rightarrow [/ matemática] [matemática] 2 ^ {2016} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 1 mod (13) [/ matemática]

Entonces, el recordatorio es [matemáticas] 1. [/ matemáticas]

Como [math] 2 ^ {12} = 1 [/ math] módulo 13, y como 2016 es divisible por 12, podemos reescribir

[matemáticas] 2 ^ {2016} = 2 ^ {12} \ cdot 2 ^ {12} \ cdot 2 ^ {12} \ cdot \ ldots \ cdot 2 ^ {12} = 1 [/ matemáticas].

Aburrido pero cierto.

En general, si desea resolver este tipo de cosas, simplemente comience a resolver [matemáticas] 2 ^ 0 [/ matemáticas] módulo 13, luego [matemáticas] 2 ^ 1 [/ matemáticas], [matemáticas] 2 ^ 2 [/ matemáticas], y así sucesivamente, hasta que vea un patrón. Esa es la mejor manera de aprender. Haz el trabajo duro un par de veces.

[matemáticas] \ displaystyle R \ left ({\ frac {{{2 ^ {2016}}}} {{13}}} \ right) = R \ left ({\ frac {{{\ \ left ({{2 ^ {12}}} \ right)} ^ {168}}}} {{13}}} \ right) = R \ left ({\ frac {{{1 ^ {168}}}} {{13}} } \ right) = R \ left ({\ frac {1} {{13}}} \ right) = 1 [/ math]

Por lo tanto, el resto es 1.