Ache o resto da divisão
de 2^1000000 por 77 .

Passo 1

O enunciado pede o resto da divisão de 2^1000000 por 77. Aqui vamos usar aritmética modular e, em particular, o Teorema de Euler, que diz que se gcd(a,n)=1, então
a^varphi(n) equiv 1 pmodn

Passo 2

Calculamos varphi(77). Como 77=7cdot11 com 7 e 11 primos, temos
varphi(77)=varphi(7),varphi(11)=6cdot10=60
Além disso, gcd(2,77)=1, logo
2^60equiv1pmod77

Passo 3

Podemos escrever
2^1000000=(2^60)^16666cdot2^40equiv1^16666cdot2^40equiv2^40pmod77
Assim basta calcular 2^40bmod77.

Passo 4

Note que 2^40=(2^10)^4. Primeiro achamos
2^10=1024equiv1024-77cdot13=1024-1001=23pmod77,
ou seja, 2^10equiv23pmod77.

Passo 5

Agora
2^20=(2^10)^2equiv23^2=529pmod77,
e
529-77cdot6=529-462=67,
logo 2^20equiv67pmod77.

Passo 6

Finalmente
2^40=(2^20)^2equiv67^2=4489pmod77,
e
4489-77cdot58=4489-4466=23
Assim 2^40equiv23pmod77.

Resposta

O resto da divisão de 2^1000000 por 77 é 23.

Exercícios relacionados