Encontre o menor inteiro positivo congruente com:
2^130(bmod 263)

Passo 1

O enunciado pede o menor inteiro positivo congruente a 2^130 módulo 263. O conteúdo é aritmética modular e potências de inteiros, e vamos usar quadratura sucessiva e o Pequeno Teorema de Fermat.

Passo 2

Como 263 é primo, varphi(263)=262 e pelo Pequeno Teorema de Fermat temos
2^262equiv 1pmod263
O expoente 130 já é menor que 262, então não precisamos reduzir mais.

Passo 3

Calculamos potências de 2 por quadratura sucessiva, sempre reduzindo módulo 263:
2^2 = 4
2^4 = 4^2 = 16
2^8 = 16^2 = 256 equiv 256 pmod263
2^16 = 256^2 = 65536 equiv 49 pmod263
2^32 = 49^2 = 2401 equiv 34 pmod263
2^64 = 34^2 = 1156 equiv 104 pmod263

Passo 4

Observe que 130 = 128 + 2. Então
2^128 = (2^64)^2 = 104^2 = 10816 equiv 33 pmod263,
e
2^130 = 2^128cdot 2^2 = 33 cdot 4 = 132 pmod263

Resposta

132

Exercícios relacionados