Exercício 4. Determine o resto da divisão de
por 13 .
Passo 1
O enunciado pede: determinar o resto da divisão de
por
.
Informações relevantes dadas: o número a dividir é e o divisor é
.
Objetivo final: encontrar o inteiro tal que
e
.
Informações relevantes dadas: o número a dividir é
Objetivo final: encontrar o inteiro
Passo 2
Primeiro precisamos entender o que significa trabalhar “resto da divisão” em termos que vamos usar: congruência modular. Vou explicar de forma simples e prática.
Definição: dizemos que dois inteiros e
são congruentes módulo
quando
divide
. Escrevemos isso como
. Isso quer dizer que
e
deixam o mesmo resto na divisão por
.
Propriedade útil: se e
, então podemos somar e multiplicar congruências:
e
. Em particular, podemos reduzir qualquer base ou produto módulo
a um número menor antes de elevar a potências — isso facilita muito os cálculos.
Definição: dizemos que dois inteiros
Propriedade útil: se
Passo 3
Reduzimos a base
módulo
para trabalhar com um número pequeno. Vamos calcular o resto de
na divisão por
.
Observação: . Logo,
Observação:
portanto
Assim podemos substituir
por
quando trabalhamos módulo
:
Passo 4
Agora vamos reduzir a potência
. Uma ferramenta muito útil aqui é o Pequeno Teorema de Fermat. Vou explicar e mostrar por que ele serve.
Enunciado do Pequeno Teorema de Fermat (forma prática): se é primo e
não é múltiplo de
, então
Enunciado do Pequeno Teorema de Fermat (forma prática): se
No nosso caso
(que é primo) e
(não múltiplo de
). Então vale
Isso nos permite reduzir expoentes grandes módulo
, porque potências de
repetem com período divisível por
.
Passo 5
Usamos a decomposição do expoente
em relação a
. Dividindo
por
:
Portanto
Aplicando a congruência de Fermat:
logo
Então só precisamos calcular
.
Passo 6
Vamos calcular
reduzindo passo a passo e simplificando módulo
a cada multiplicação (isso evita números grandes).
Calculemos potências menores:
Calculemos potências menores:
Reduzindo
módulo
:
,
. Logo
Reduzindo
módulo
:
,
. Assim
Passo 7
Portanto, voltando ao que precisamos:
Ou seja, o resto da divisão de
por
é
.
Resposta
10