Calcule o resto da divisão de a por n nos casos abaixo:
a=7^{1001} e n=13.

Passo 1

O enunciado pede o resto da divisão de a por n em que
a = 7^{1001},\quad n = 13.
Vamos usar aritmética modular e o Teorema de Euler para reduzir o expoente e depois calcular a potência módulo 13.

Passo 2

Como \gcd(7,13)=1, vale o Teorema de Euler:
\varphi(13)=12 \quad\text{e}\quad 7^{12}\equiv1\pmod{13}.

Passo 3

Precisamos reduzir o expoente 1001 módulo \varphi(13)=12:
1001 = 12\times83 + 5 \quad\Longrightarrow\quad 7^{1001}\equiv7^5\pmod{13}.

Passo 4

Calculemos 7^5\bmod13 em etapas:
7^2 = 49 \equiv 49 - 39 = 10\pmod{13},
7^4 = (7^2)^2 \equiv 10^2 = 100 \equiv 100 - 91 = 9\pmod{13},
7^5 = 7^4\cdot7 \equiv 9\cdot7 = 63 \equiv 63 - 52 = 11\pmod{13}.

Resposta

O resto da divisão de 7^{1001} por 13 é 11.

Exercícios relacionados