Exercício 3. (2,0 pts) Seja
Calcule o resto da divisão de
por 13 .
Passo 1
O que o enunciado pede: calcular o resto da divisão de
por
.
Informações dadas:
Observação útil (contagem dos termos): os expoentes vão de
até
de
em
, logo há
termos. Podemos escrever
Passo 2
Conceito básico que vamos usar (explicação didática): trabalhar com restos significa trabalhar em aritmética modular. Dizemos que
é congruente a
módulo
e escrevemos
quando
é múltiplo de
. Importante para manipular potências:
- Se
então (multiplicação preserva congruência). - Em particular, se conhecemos
para alguns , podemos reduzir expoentes grandes usando a periodicidade das potências de módulo .
Vamos descobrir essa periodicidade calculando potências pequenas de
módulo
.
Passo 3
Calculemos as potências de
módulo
uma a uma (faço as contas e explico cada subtração):
Conclusão importante (aulasinha rápida): encontramos
. Isso significa que as potências de
repetem em ciclos de comprimento
(a ordem de
módulo
divide
— aqui é exatamente
). Assim, para qualquer inteiro
,
e podemos reduzir expoentes módulo
.
Passo 4
Aplicando essa redução aos termos de
. Para cada
temos
Como
, temos
. Logo
Usamos os valores já calculados:
(lembrando que expoentes equivalentes módulo
usam esses valores).
Vamos listar os
termos
reduzidos modulo
para
:
-
. -
. -
. -
. -
. -
. -
. -
. -
. -
.
Note que o padrão
se repete a cada
termos porque
módulo
passa por
.
Passo 5
Somamos os restos dos
termos:
três repetições completas de mais o último termo
:
três repetições completas de
Agora reduzimos
módulo
:
Portanto o resto da divisão de
por
é
.