Calcule, usando o teorema de Euler:
3^1000 equiv ?(bmod 7)

Passo 1

Então, a gente precisa achar
3^1000 bmod 7
e para isso vamos usar o teorema de Euler, que envolve calcular a função totiente varphi(n) e reduzir o expoente usando
a^varphi(n) equiv 1 pmod n sempre que gcd(a,n)=1

Passo 2

Como 7 é primo, temos
varphi(7) = 7 - 1 = 6

Passo 3

Verificamos que gcd(3,7)=1, então o teorema de Euler nos dá
3^6 equiv 1 pmod 7
Agora, escrevemos 1000 na forma
1000 = 6 cdot 166 + 4,
logo
3^1000 = (3^6)^166 cdot 3^4 equiv 1^166 cdot 3^4 = 3^4 pmod 7

Passo 4

Basta calcular
3^4 = 81
e notar que
81 = 11 cdot 7 + 4
portanto
3^4 equiv 4 pmod 7

Resposta

4

Exercícios de Livros Relacionados