Calcule, usando o teorema de Euler:
7^1015 equiv ?(bmod 31)

Passo 1

O enunciado pede para calcular
7^1015bmod31
usando o teorema de Euler. Para isso vamos usar que, se gcd(a,n)=1, então
a^varphi(n)equiv1pmod n

Passo 2

Como 31 é primo,
varphi(31)=31-1=30,
logo pelo teorema de Euler
7^30equiv1pmod31

Passo 3

Reduzimos o expoente 1015 módulo 30:
1015 = 30cdot33 + 25
portanto
7^1015equiv7^25pmod31

Passo 4

Para calcular 7^25bmod31 note que
7^25 = (7^5)^5
Calculamos primeiro 7^5bmod31:
7^2=49equiv18, 7^4=18^2=324equiv14, 7^5=14cdot7=98equiv5pmod31

Passo 5

Agora
7^25equiv5^5pmod31
Calculemos 5^5bmod31:
5^2=25, 5^4=25^2=625equiv5, 5^5=5cdot5=25pmod31

Resposta

7^1015equiv25pmod31

Exercícios de Livros Relacionados