Qual o resto da divisão de 2^124512 por 31 ?

Passo 1

O enunciado pede o resto da divisão de 2^124512 por 31. Isso é um problema de aritmética modular, em que vamos usar o Pequeno Teorema de Fermat, já que 31 é primo e 2 não é múltiplo de 31.

Passo 2

Pelo Pequeno Teorema de Fermat, se p é primo e gcd(a,p)=1, então
a^,p-1equiv1pmod p
Aqui p=31 e a=2, logo
2^30equiv1pmod31

Passo 3

Para aproveitar essa periodicidade, reduzimos o expoente 124512 módulo 30:
124512 = 30 times 4150 + 12
Assim
2^124512 = (2^30)^4150cdot 2^12 equiv 1^4150cdot 2^12 equiv 2^12pmod31

Passo 4

Basta agora calcular 2^12 e reduzir módulo 31:
2^12=4096,
e dividindo 4096 por 31 temos 4096 = 31times132 + 4. Logo o resto é 4.

Resposta

4

Exercícios relacionados