Achar os restos das seguintes divisões:
\quad 5^{21} por 1274

Passo 1

O problema pede: achar o resto da divisão de 5^{21} por 1274. Ou seja, encontrar o número r tal que
0 \le r < 1274
e
5^{21} \equiv r \pmod{1274}.
Informações relevantes dadas (e que vou usar): 1274 é fatorável. Calculando,
1274 = 2 \cdot 637 = 2 \cdot 49 \cdot 13 = 2 \cdot 7^2 \cdot 13.
Portanto vou trabalhar com as congruências modulares em \bmod 2, \bmod 49 e \bmod 13 e depois combinar os resultados.

Passo 2

Estratégia (explicada de forma simples): se eu sei o resto de 5^{21} em cada um dos módulos 2, 49 e 13, então posso usar o Teorema Chinês dos Resto (CRT) para juntar essas informações e obter o resto único módulo 1274. Vou calcular separadamente
5^{21} \bmod 2,\quad 5^{21} \bmod 49,\quad 5^{21} \bmod 13,
mostrando passo a passo como reduzir potências grandes sem calculadora.

Passo 3

Cálculo de 5^{21} \bmod 13. Primeiro, uma ferramenta útil: para um número primo p e um inteiro a coprimo com p, vale o Pequeno Teorema de Fermat:
a^{p-1} \equiv 1 \pmod{p}.
Aqui p=13 e a=5 são coprimos, então
5^{12} \equiv 1 \pmod{13}.
Escrevo 21 = 12 + 9, logo
5^{21} = 5^{12}\cdot 5^{9} \equiv 1\cdot 5^{9} \equiv 5^{9} \pmod{13}.
Agora faço reduções práticas: 5^2 = 25 \equiv -1 \pmod{13} porque 25-26=-1. Assim
5^4 = (5^2)^2 \equiv (-1)^2 = 1 \pmod{13}.
Então 5^8 \equiv 1 e
5^9 = 5^8\cdot 5 \equiv 1\cdot 5 = 5 \pmod{13}.
Portanto
5^{21} \equiv 5 \pmod{13}.

Passo 4

Cálculo de 5^{21} \bmod 49. Aqui 49=7^2 não é primo, mas podemos usar a função totiente de Euler: \varphi(49)=49\left(1-\tfrac{1}{7}\right)=42. Para a coprimo a 49,
a^{42} \equiv 1 \pmod{49}.
Então 5^{42}\equiv1, e 21 é exatamente a metade de 42, o que significa que 5^{21} é uma raiz quadrada de 1 módulo 49, ou seja, vale 1 ou -1 (mas precisamos descobrir qual). Vou calcular passo a passo potências menores e reduzir módulo 49:
Calculemos:
5^2 = 25.
5^3 = 125 \equiv 125 - 2\cdot 49 = 125 - 98 = 27.
5^6 = (5^3)^2 \equiv 27^2 = 729.
Reduzindo 729 módulo 49: 49\cdot 14 = 686, então 729-686=43. Logo
5^6 \equiv 43 \pmod{49}.
5^7 = 5^6\cdot 5 \equiv 43\cdot 5 = 215.
Reduzindo 215 por 49: 49\cdot 4 =196, 215-196=19. Então
5^7 \equiv 19 \pmod{49}.
Agora
5^{14} = (5^7)^2 \equiv 19^2 = 361.
Reduzindo 361 por 49: 49\cdot 7 =343, 361-343=18. Assim
5^{14} \equiv 18 \pmod{49}.
Finalmente
5^{21} = 5^{14}\cdot 5^7 \equiv 18\cdot 19 = 342.
Reduzindo 342 por 49: 49\cdot 7 =343, então 342-343 = -1. Ou seja
5^{21} \equiv -1 \equiv 48 \pmod{49}.

Passo 5

Cálculo de 5^{21} \bmod 2\). Simples: \(5\equiv 1 \pmod{2}\), então \[5^{21} \equiv 1^{21} = 1 \pmod{2}.
Agora temos o sistema de congruências:
\begin{cases} x \equiv 1 \pmod{2},\\[4pt] x \equiv 48 \pmod{49},\\[4pt] x \equiv 5 \pmod{13}. \end{cases}
Como 2\], \(49 e 13 são coprimos entre si, existe solução única módulo 1274. Vou juntar primeiro as duas congruências módulo 49 e 13 (produto 49\cdot 13=637), e depois ajusto com o módulo 2.]

Passo 6

Resolver
x \equiv 48 \pmod{49},\qquad x \equiv 5 \pmod{13}.
Escrevo x = 48 + 49k e imponho a condição módulo 13:
48 + 49k \equiv 5 \pmod{13}.
Reduzo coeficientes módulo 13: 48 \equiv 48-13\cdot3=48-39=9. Também 49 \equiv 49-13\cdot3=49-39=10. Então a congruência fica
9 + 10k \equiv 5 \pmod{13}.
Subtraindo 9:
10k \equiv 5-9 \equiv -4 \equiv 9 \pmod{13}.
Agora preciso do inverso de 10 módulo 13. Testando pequenos números, 10\cdot 4 = 40 \equiv 1 \pmod{13}, logo 10^{-1}\equiv 4. Multiplicando,
k \equiv 4\cdot 9 = 36 \equiv 36-13\cdot2 = 36-26 = 10 \pmod{13}.
Então k = 10 + 13t e
x = 48 + 49k = 48 + 49(10 + 13t) = 48 + 490 + 637t = 538 + 637t.
Portanto, a solução módulo 637 é
x \equiv 538 \pmod{637}.
Verificação rápida (apenas para ficar seguro): 538 \bmod 49 = 48 e 538 \bmod 13 = 5, OK.

Passo 7

Agora junto com a congruência em \bmod 2: queremos x\equiv 538 \pmod{637} e x\equiv 1 \pmod{2}. Escrevo x = 538 + 637t. Como 637 é ímpar, note que 538 é par ( 538 \bmod 2 = 0). Para ter resto 1 módulo 2 precisamos escolher t tal que 538 + 637t seja ímpar. Como 637t é ímpar quando t é ímpar, basta escolher t=1 (o menor ajuste). Com t=1 obtemos
x = 538 + 637 = 1175.
Esse x está entre 0 e 1273 e satisfaz todas as congruências. Verificações finais rápidas:
1175 \bmod 2 = 1,\quad 1175 \bmod 49 = 48,\quad 1175 \bmod 13 = 5.
Tudo confere, logo o resto pedido é 1175.

Resposta

1175

Exercícios relacionados