Problema 4.22. Sabendo que 2^4=16 equiv-1 bmod 17, ache o resto da divisão de 2^30 por 17 .

Passo 1

O enunciado nos dá que ,2^4=16equiv -1bmod 17 e pede o resto da divisão de ,2^30 por 17. O conteúdo é aritmética modular e propriedades de potência; vamos explorar a relação entre expoentes e a periodicidade em bmod 17.

Passo 2

Da relação ,2^4equiv -1bmod 17, elevamos ao quadrado para obter
2^8 = (2^4)^2 equiv (-1)^2 = 1 bmod 17
Isso mostra que a sequência de potências de 2 se repete com período que divide 8.

Passo 3

Como 2^8equiv1bmod17, podemos reduzir o expoente de 2^30 módulo 8. Escrevemos
2^30 = 2^8cdot3 + 6 = (2^8)^3cdot 2^6
e, usando (2^8)^3equiv1^3=1, segue que
2^30equiv 2^6 bmod 17

Passo 4

Basta agora calcular
2^6 = 64
Dividindo 64 por 17 temos 17cdot3=51 e resto 64-51=13. Logo
2^6equiv13bmod17
e, consequentemente,
2^30equiv13bmod17

Resposta

O resto da divisão de 2^30 por 17 é 13.

Exercícios relacionados