Exercício 2. (
) Determine os três últimos dígitos de
.
Passo 1
O enunciado pede: determinar os três últimos dígitos de
.
Informações dadas e relevantes: é a potência a avaliar; “três últimos dígitos” significa equivalência módulo
. Também é útil notar que
. Não há mais informações no enunciado.
Informações dadas e relevantes:
Passo 2
Escolha do caminho (explicado de forma curta antes de começar a conta): trabalhar módulo
diretamente é difícil; por isso vamos usar que
se fatora em
e
que são coprimos. Calcularemos
módulo
e módulo
separadamente e depois combinamos os resultados usando o Teorema Chinês dos Restos (CRT). Vou explicar cada conceito quando aparecer.
Breve explicação do CRT (útil para a prova): se temos
e
com
, existe uma única solução
modulo
. Então achar o número módulo
reduz-se a achar as congruências módulo
e
.
Passo 3
Cálculo de
módulo
.
Primeiro, simplificamos a base módulo :
porque
é múltiplo de
.
Se então, para qualquer inteiro positivo
,
.
Portanto
Primeiro, simplificamos a base módulo
Se
Portanto
Passo 4
Cálculo de
módulo
.
Motivação: e
, então podemos usar o Teorema de Euler para reduzir o expoente. Vou explicar o Teorema de Euler de forma simples: se
, então
, onde
é a função totiente de Euler (número de inteiros entre
e
coprimos com
).
Motivação:
Calculamos
. Para
,
Pelo Teorema de Euler:
Logo podemos reduzir o expoente
módulo
. Calculamos
:
Assim
Agora precisamos calcular
módulo
.
Passo 5
Cálculo explícito de
, passo a passo (cada multiplicação reduzida para caber sem calculadora):
Começamos com potências pequenas e reduzimos módulo em cada passo.
Começamos com potências pequenas e reduzimos módulo
Reduzindo
módulo
:
,
. Logo
Reduzindo
:
,
. Logo
Reduzindo
:
,
. Logo
Agora podemos usar essas potências para alcançar
. Uma estratégia rápida é obter
, depois
e multiplicar por
.
Calcule
:
Reduzindo
módulo
:
,
. Então
Calcule
:
Reduzindo
:
,
. Logo
Finalmente,
:
Reduzindo
módulo
:
,
. Assim
Portanto
Passo 6
Resumo das duas congruências obtidas:
Agora precisamos combinar essas duas informações com CRT para obter o valor módulo
.
Passo 7
Aplicando o Teorema Chinês dos Restos (CRT) para achar
tal que
Escrevemos
para algum inteiro
. Impomos a segunda condição módulo
. Primeiro reduzimos coeficientes módulo
:
Então a condição
vira
Subtraindo
:
. Como
, temos
Agora precisamos do inverso de
módulo
. Observamos que
, então o inverso de
é
. Multiplicando ambos os lados por
:
Logo
. A menor escolha é
. Tomando
,
Verificação rápida:
e
. Como a solução é única módulo
, concluímos que