Ache o resto da divisão euclidiana de
por
nos seguintes casos:
e
.
Passo 1
O enunciado dá
e
e pede: encontrar o resto da divisão euclidiana de
por
.
Isto é, encontrar um inteiro tal que exista um inteiro
com
Isto é, encontrar um inteiro
e
Passo 2
Vamos traduzir isso em linguagem de congruências (útil para potências grandes). Definição e propriedades básicas que usarei:
- Dizemos que dois inteiros
e são congruentes módulo quando é múltiplo de . Escreve-se . - O resto da divisão de
por é justamente o representante com tal que . - Propriedade para potências: se
então para todo inteiro vale . Isso permite reduzir bases ou expoentes quando possível.
Passo 3
Calculo direto dos primeiros poderes de
módulo
para ver se há um padrão:
Como
, a sequência de restos repete a cada
expoentes. Para ver isso, calcule:
e assim por diante. Logo o período (ciclo) dos restos de
módulo
é
.
Passo 4
Agora reduzo o expoente
módulo o período
. Dividindo
por
obtenho
Portanto
Usando
segue
Isto significa que o resto da divisão de
por
é
.
Passo 5
Observação pedagógica rápida: poder-se-ia também aplicar o Teorema Pequeno de Fermat que diz que, para primo
e base
não múltipla de
, tem-se
. Aqui encontramos um período ainda menor (
), o que simplifica o cálculo. Mas o argumento anterior, verificando
, já é suficiente e direto.