Ache o resto da divisão euclidiana de
por
nos seguintes casos:
e
.
Passo 1
O enunciado dá os números
e pede: encontrar o resto da divisão euclidiana de
por
.
Em outras palavras: calcular o resto de na divisão por
, isto é, encontrar
tal que
Em outras palavras: calcular o resto de
Passo 2
Rápida aula sobre o que vamos usar (sem pânico, é direto):
- Dizer que dois inteiros
e são congruentes módulo significa que divide . Escreve-se . - Propriedades úteis:
- Pode reduzir a base de potências módulo
: se então . - Produto e soma preservam congruência: se
e então e (tudo módulo ).
- Pode reduzir a base de potências módulo
- Teorema de Fermat (caso prático): para primo
e inteiro não múltiplo de , Isso facilita calcular potências grandes reduzindo o expoente módulo .
Passo 3
Reduzimos cada base módulo
antes de elevar:
Passo 4
Calcular
. Usamos Fermat: como
, escrevemos
e obtemos
Agora
, e
Logo
Passo 5
Calcular
. Como
, basta achar
módulo
. Note que
(pela mesma ideia), então
Portanto
Passo 6
Multiplicando as partes, temos
E
. Logo a primeira parcela inteira da soma é congruente a
módulo
.
Passo 7
Calcular
. Como
, temos
Passo 8
Somamos as duas contribuições módulo
:
Isso significa que o resto da divisão de
por
é
.
Resposta
4