Achar os restos das seguintes divisões:
por 17
Passo 1
O que o enunciado pede: encontrar o resto da divisão de
por
.\n
Informações dadas e relevantes: a base é , o expoente é
e o divisor (módulo) é
. Note que
é um número primo. Nada mais foi fornecido.
Informações dadas e relevantes: a base é
Passo 2
Escolha do método (explicando por que): como o divisor
é primo e a base
não é múltipla de
, a ferramenta mais direta e econômica aqui é usar o teorema pequeno de Fermat para reduzir potências grandes módulo
. Isso evita calcular potências enormes e é uma técnica que cai direto em provas. Vou explicar o teorema e aplicá-lo passo a passo.
Passo 3
Conceitos básicos de congruência e resto (mini-aula): dizer que “o resto de
por
” é o mesmo que trabalhar com congruência modular. Escrevemos
quando
é múltiplo de
. Exemplo simples:
porque
. Uma propriedade útil: se
então
para qualquer inteiro
. Isso permite reduzir a base antes de elevar à potência.
Passo 4
Verificação de que podemos aplicar Fermat: o teorema pequeno de Fermat diz que, para primo
e inteiro
com
, vale
Aqui
e
. Como
não é múltiplo de
, temos
, logo as hipóteses do teorema são satisfeitas.
Passo 5
Aplicando o teorema: com
o teorema dá
Expliquei acima o que cada símbolo significa:
é a potência de
de ordem
e o
significa que ao dividir
por
o resto é
.
Passo 6
Reduzindo o expoente usando a congruência: como
, potências cuja expoente seja múltiplo de
ficarão fáceis de reduzir. Escrevemos
como múltiplo de
:
Portanto
Passo 7
Usando a congruência para concluir: substituindo a congruência de
na expressão acima, obtemos
Como
, segue que
ou seja, o resto da divisão de
por
é
.