Ensino Médio ⇒ CONGRUÊNCIA MODULAR

[francotorres]

Olá.
Queria entender por que 41³⁷⁴deixa resto 4 na divisão por 13 e por que 2³² + 1 deixa resto 0 na divisão por 641.
Utilize os conceitos de congruência modular para responder.
a ≡ b (mod m)

As duas afirmações são verdadeiras. Mas não entendo como chegar no resultado.

[goncalves3718]

Primeira parte

---

[tex3]41 \equiv 2\,(\mod 13) \implies 41^4 \equiv 3 \, (\mod 13) \implies 41^{12} \equiv 1 \,( \mod 13)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]41 \equiv 2\,(\mod 13) \implies 41^4 \equiv 3 \, (\mod 13) \implies 41^{12} \equiv 1 \,( \mod 13)[/tex3]

Daí:

[tex3]\left(41^{12}\right)^{31} = 41^{372} \equiv 1 \, (\mod 13) \implies 41^{372} \cdot 41 \cdot 41 \equiv 1 \cdot 2 \cdot 2 \, (\mod 13) \implies [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\left(41^{12}\right)^{31} = 41^{372} \equiv 1 \, (\mod 13) \implies 41^{372} \cdot 41 \cdot 41 \equiv 1 \cdot 2 \cdot 2 \, (\mod 13) \implies [/tex3]

[tex3]\boxed{\boxed{41^{374} \equiv 4 \,(\mod 13)}}[/tex3]

Segunda parte

---

[tex3]2 \equiv 2 \, (\mod 641) \implies2^{13} \equiv 141 \, (\mod 641) \implies 2^{13} \cdot 2^3 \equiv -154\ \implies \left( 2^{16} \right)^2 \equiv 23716
\, (\mod 641)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]2 \equiv 2 \, (\mod 641) \implies2^{13} \equiv 141 \, (\mod 641) \implies 2^{13} \cdot 2^3 \equiv -154\ \implies \left( 2^{16} \right)^2 \equiv 23716
\, (\mod 641)[/tex3]

Daí é só notar que [tex3]641 \cdot 37 = 23717[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]641 \cdot 37 = 23717[/tex3]

. Logo:

[tex3]2^{32} \equiv -1 \, (\mod 641) [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]2^{32} \equiv -1 \, (\mod 641) [/tex3]

Somando 1 nos dois lados:


[tex3]\boxed{\boxed{2^{32}+1 \equiv 0 \, (\mod 641)}}[/tex3]

Esse é mais trabalhoso devido aos cálculos que você deve realizar, como [tex3](-154)^2[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](-154)^2[/tex3]