Ensino Superior ⇒ Teorema Chinês do Resto Tópico resolvido

[rodBR]

Usando o Teorema Chinês do Resto (TCR) calcule: [tex3]97^{77}(mod \ 77)[/tex3]

[undefinied3]

Como [tex3]77=7.11[/tex3], podemos pensar em duas congruências

[tex3]97^{77} \ (mod \ 11)[/tex3]
[tex3]97^{77} \ (mod \ 7)[/tex3]

Resolvendo a primeira:
[tex3]97 \equiv (-2) \ (mod \ 11)[/tex3], [tex3]\phi(11)=10 \rightarrow \therefore (-2)^{10} \equiv 1 \ (mod \ 11)[/tex3]
[tex3]97^{77} \equiv (-2)^{7.10+7}\equiv (-2)^7 \equiv -128 \equiv 4 \ (mod \ 11)[/tex3]

Resolvendo a segunda:
[tex3]97 \equiv (-1) \ (mod \ 7)[/tex3]
[tex3]97^{77} \equiv (-1)^{77} \equiv -1 \equiv 6 \ (mod \ 7)[/tex3]

Pelo TCR, precisamos calcular os inversos multiplicativos de 7 módulo 11 e de 11 módulo 7
[tex3]7x \equiv 1 \rightarrow x \equiv 8 \ (mod \ 11)[/tex3]
[tex3]11y \equiv 1 \rightarrow y \equiv 2 \ (mod \ 7)[/tex3]

Assim, temos:
[tex3]97^{77} \equiv 6.11.2+4.7.8 \equiv 48 \ (mod 77)[/tex3]
Lembrando que esse [tex3]6.11.2+4.7.8[/tex3] é tal que:
[tex3]\begin{cases}
x \equiv a \ (mod \ p) \\
x \equiv b \ (mod \ q) \\
u=p^{-1} \ (mod \ q) \\
v=q^{-1} \ (mod \ p) \\
x = aqv+bpu \ (mod \ pq)
\end{cases}[/tex3]

Tudo isso valendo apenas se p e q forem primos entre si.

[rodBR]

Obrigado undefinied3.