Problema 4.9. Determine os restos da divisão por 4, 8, 25 e 125 dos números: 3 254, 12736,54827,33875435,57612510.

Passo 1

O enunciado pede para determinar, para cada um dos números
3^254, 12736, 54827, 33875435, 57612510,
os restos da divisão por 4, por 8, por 25 e por 125.
O que vamos usar:
– Para 3^254, teorema de Euler/Carmichael para reduzir expoente em módulos 25 e 125, e substituições simples em módulos 4 e 8.
– Para os inteiros, basta usar propriedades de divisibilidade em base decimal (últimos dígitos) para obter restos em 4,8,25,125.

Passo 2

Cálculo de 3^254bmod 4 e bmod 8.
Em módulo 4 temos 3equiv -1pmod4, então
3^254equiv(-1)^254equiv 1pmod4
Em módulo 8, como varphi(8)=4 e gcd(3,8)=1,
3^254equiv 3^,254bmod4equiv3^2equiv9equiv1pmod8

Passo 3

Cálculo de 3^254bmod 25 e bmod 125.
Usamos varphi(25)=20 e varphi(125)=100.
Para 25: 254equiv14pmod20, então
3^254equiv3^14pmod25
Como
3^2equiv9, 3^4equiv9^2equiv81equiv6,3^8equiv6^2equiv36equiv11pmod25,
segue
3^14=3^8cdot3^4cdot3^2equiv11cdot6cdot9equiv11cdot54equiv11cdot4equiv44equiv19pmod25
Para 125: 254equiv54pmod100, então
3^254equiv3^54pmod125
Calculamos
3^10equiv49,3^20equiv49^2equiv2401equiv26,3^40equiv26^2equiv676equiv51pmod125,
e assim
3^54=3^40cdot3^10cdot3^4equiv51cdot49cdot81 equiv(51cdot49)cdot81equiv124cdot81equiv10044equiv44pmod125

Passo 4

Cálculo dos restos bmod4 e bmod8 para os inteiros.
Basta olhar os últimos dois dígitos para módulo 4 e os últimos três para 8:
12736 termina em 36, logo
,12736equiv0pmod4,;12736equiv0pmod8
54827 termina em 27, logo
,54827equiv3pmod4,;54827equiv3pmod8
33875435 termina em 35, logo
,33875435equiv3pmod4,;33875435equiv3pmod8
57612510 termina em 10, logo
,57612510equiv2pmod4,;57612510equiv6pmod8

Passo 5

Cálculo dos restos bmod25 e bmod125 para os mesmos inteiros.
Em base decimal basta olhar os últimos dois dígitos para 25 e três para 125:
12736: últimos dois dígitos 36, então
,12736equiv36equiv11pmod25;
últimos três 736, então
,12736equiv736equiv111pmod125
54827: últimos dois 27 dão
,54827equiv2pmod25;
últimos três 827 dão
,54827equiv827equiv77pmod125
33875435: últimos dois 35 dão
,33875435equiv10pmod25;
últimos três 435 dão
,33875435equiv435equiv60pmod125
57612510: últimos dois 10 dão
,57612510equiv10pmod25;
últimos três 510 dão
,57612510equiv510equiv10pmod125

Resposta

3^254: equiv1bmod4,;equiv1bmod8,;equiv19bmod25,;equiv44bmod125 12736: equiv0bmod4,;equiv0bmod8,;equiv11bmod25,;equiv111bmod125 54827: equiv3bmod4,;equiv3bmod8,;equiv2bmod25,;equiv77bmod125 33875435: equiv3bmod4,;equiv3bmod8,;equiv10bmod25,;equiv60bmod125 57612510: equiv2bmod4,;equiv6bmod8,;equiv10bmod25,;equiv10bmod125

Exercícios relacionados