Question

usando aritmetica modular qual o resto da divisao de 2^815 por 17?

Answer 1

Observemos o que acontece com as potências de  2:

     •  2¹ = 2

     •  2² = 2 · 2 = 4

     •  2³ = 2 · 2 · 2 = 8

     •  2⁴ = 2 · 2 · 2 · 2 = 16


Note que

     $\mathsf{2^4=16}\\\\ \mathsf{2^4=17-1}\\\\ \mathsf{2^4\equiv (-1)\quad (mod~17)\qquad (i)}$


A congruência acima será útil para resolvermos o problema. Agora, basta calcularmos o quociente da divisão do expoente  815  por  4:

     $\mathsf{815=4\cdot 203+3}$


Então, eleve os dois lados da congruência  (i)  a  203:

     $\mathsf{(2^4)^{203}\equiv (-1)^{203}\quad (mod~17)}\\\\ \mathsf{2^{4\,\cdot\,203}\equiv (-1)^{203}\quad (mod~17)}\\\\ \mathsf{2^{812}\equiv (-1)\quad (mod~17)}$


Como o expoente  203  é ímpar, o resultado da potência no lado direito ficou com o mesmo sinal da base (negativo).

Multiplique os dois lados por  2³:

     $\mathsf{2^{812}\cdot 2^3\equiv (-1)\cdot 2^3\quad (mod~17)}\\\\ \mathsf{2^{812+3}\equiv (-1)\cdot 2^3\quad (mod~17)}\\\\ \mathsf{2^{815}\equiv (-1)\cdot 8\quad (mod~17)}\\\\ \mathsf{2^{815}\equiv -8\quad (mod~17)}$


Podemos somar qualquer múltiplo do módulo  17,  e a congruência é mantida:

     $\mathsf{2^{815}\equiv -8+17\quad (mod~17)}\\\\ \mathsf{2^{815}\equiv 9\quad (mod~17)}$


Como  0 ≤ 9 < 17,  então o resto da divisão de  2⁸¹⁵  por  17  é  9.


Resposta:  9.


Bons estudos! :-)