Reszta z dzielenia

[Podroznik]

Jakie wartości może przyjąć reszta z dzielenia:
\(\displaystyle{ 423^{342}+2^{32n+1}}\) przez \(\displaystyle{ 17}\) gdy \(\displaystyle{ n\in {N}}\)
Jedynie wiem, że zacząć należy od tego, że całe wyrażenie modulo 17 równa się tej reszcie.

[musialmi]

Jak poprawisz literówki, to pogadamy ;p

[Podroznik]

Pogadajmy więc.

[musialmi]

Na dobry początek: \(\displaystyle{ 425=17\cdot 25}\), \(\displaystyle{ 16=2^4}\). Przypomnę też tożsamość: \(\displaystyle{ x-1 \equiv -1 \mod x}\).
A, nie wiem jak zrobić to zadanie, ale tymi wskazówkami powinniśmy dojść do czegoś łatwego.

[AndrzejK]

Z małego twierdzenia Fermata:
\(\displaystyle{ 2^{32} \equiv 1 \pmod{17}}\)
Stąd:
\(\displaystyle{ 2^{32n} \equiv 1^n \equiv 1 \pmod{17}}\)
A więc:
\(\displaystyle{ 2^{32n+1} \equiv 1 \cdot 2 \equiv 2 \pmod{17}}\) niezależnie od \(\displaystyle{ n}\).
Pozostaje nam pierwszy składnik (pierwszy krok też z MTF):
\(\displaystyle{ 423^{342} \equiv 423^{6} \equiv (-2)^6 \equiv 13 \pmod{17}}\)
Zatem:
\(\displaystyle{ 2^{32n+1}+423^{342} \equiv 2+13 \equiv 15 \pmod{17}}\)

[musialmi]

O proszę, a mi wyszedł wynik \(\displaystyle{ 1}\). Jak ty to MTF zastosowałeś w ukryty sposób dla 423? Dla dwójki w sumie też nie czaję, ale przynajmniej wynik się zgadza.
EDIT: Dobra, widzę swój błąd, ale o MTF opowiedz i tak

[AndrzejK]

Ogólnie (lekko zmodyfikowana wersja MTF):
\(\displaystyle{ a^{p-1} \equiv 1 \pmod{p}}\)
Zatem mamy dla dwójki:
\(\displaystyle{ 2^{16} \equiv 1 \pmod{17}}\)
Podnosimy obustronnie do kwadratu:
\(\displaystyle{ 2^{32} \equiv 1^2 \equiv 1 \pmod{17}}\)

Analogicznie:
\(\displaystyle{ 423^{16} \equiv 1 \pmod{17}}\)
Podnosimy obustronnie do potęgi \(\displaystyle{ 21}\):
\(\displaystyle{ 423^{336} \equiv 1^{21} \equiv 1 \pmod{17}}\)
Zatem \(\displaystyle{ 423^{342} \equiv 423^{336} \cdot 423^{6} \equiv 1 \cdot 423^{6} \equiv 423^{6} \pmod{17}}\)