Reszta dzielenia liczby

[Vexo]

Dobry wieczór.

Czy byłby ktoś tak miły i pomógł/nakierował na rozwiązanie poniższego zadania? (bardziej zależy mi na zrozumieniu tego zadania niż rozwiązaniu)

Proszę obliczyć: resztę z dzielenia liczby \(\displaystyle{ 2^{113}}\) przez 51?
Czy wystarczy skorzystać z twierdzenia Eulera czy potrzebna jest inna metoda?

Pozdrawiam
Vexo

[Premislav]

Nie wiem, co jest potrzebne, ja bym zapisał, że \(\displaystyle{ 2^{8}=256=5\cdot 51+1\equiv 1\pmod{51}}\)
oraz \(\displaystyle{ 2^{113}=2^{14 \cdot 8+1}=2\cdot (2^{8})^{14}\equiv}\)...

[Vexo]

Dziękuje Ci bardzo za pomoc.
Czy byłaby możliwość byś jakoś wytłumaczył na podanym przykładzie o co w tym chodzi tak +/-?

[Premislav]

To rozwiązanie jest o tyle kiepskie, że jest zgadnięte (więc przy innych liczbach mogłoby tak dobrze się nie ułożyć). Po prostu szybko znalazłem taką potęgę dwójki, że jej reszta z dzielenia przez \(\displaystyle{ 51}\) jest możliwie mała, żeby uprościć obliczenia. Swoją drogą ja jestem głupi i myślałem, że \(\displaystyle{ 51}\) jest pierwsza, ale przecież \(\displaystyle{ 51=3\cdot 17}\), więc (\(\displaystyle{ \phi}\) to funkcja Eulera)
\(\displaystyle{ \phi(51)=\phi(3)\cdot \phi(17)=2\cdot 16=32}\), gdyż \(\displaystyle{ (17,3)=1}\) oraz liczby \(\displaystyle{ 3}\) i \(\displaystyle{ 17}\) są pierwsze (a \(\displaystyle{ \phi(p)=p-1}\) dla każdego \(\displaystyle{ p}\) pierwszego).
Zatem z twierdzenia Eulera \(\displaystyle{ 2^{32}\equiv 1\pmod{51}}\), toteż \(\displaystyle{ 2^{96}\equiv 1\pmod{51}}\) i \(\displaystyle{ 2^{113}=2^{17}\cdot 2^{96}\equiv 2^{17}\pmod{51}}\). Teraz jestem jeszcze głupszy, bo wydawało mi się, że \(\displaystyle{ 4\cdot 32=108}\), lol, dopiero teraz zauważyłem, że to nieprawda. Więc z Eulera idzie gorzej niż zz mojego zgadnięcia, bo jeszcze musimy znać resztę z dzielenia \(\displaystyle{ 2^{17}}\) przez \(\displaystyle{ 51}\). Jeśli wiemy, że \(\displaystyle{ 2^{8}\equiv 1\pmod{51}}\), to rozpisujemy to na \(\displaystyle{ 2\cdot 2^{16}=2\cdot (2^{8})^{2}}\) i skoro \(\displaystyle{ 2^{8}\equiv 1\pmod{51}}\), to też \(\displaystyle{ 2^{16}\equiv 1\pmod{51}}\), no i jeśli liczba \(\displaystyle{ a}\) daje resztę \(\displaystyle{ r_{1}}\) z dzielenia przez \(\displaystyle{ c}\) oraz liczba \(\displaystyle{ b}\) daje resztę \(\displaystyle{ r_{2}}\) z dzielenia przez \(\displaystyle{ c}\), to \(\displaystyle{ a\cdot b}\) daje taką samą resztę z dzielenia przez \(\displaystyle{ c}\), jak \(\displaystyle{ r_{1}\cdot r_{2}}\).

Nie wiem, co wytłumaczyć. Rozumiesz zapis z \(\displaystyle{ \equiv}\)? Liczba \(\displaystyle{ a}\) przystaje do liczby całkowitej \(\displaystyle{ c}\) modulo \(\displaystyle{ b}\), gdzie \(\displaystyle{ b \in \NN, b>1}\), co zapisujemy \(\displaystyle{ a\equiv c \pmod{b}}\), gdy \(\displaystyle{ a}\) i \(\displaystyle{ c}\) dają taką samą resztę z dzielenia przez \(\displaystyle{ b.}\)

[Vexo]

O kurczę !
Na wstępie muszę Ci baaaaardzo podziękować za tak wspaniale wytłumaczone zadanie!
Już wszystko jest jasne i klarowne. Jeszcze przerobię sobie parę podobnych przykładów i nabiorę wprawy.
Jakbym miał jeszcze jakieś wątpliwości czy pytania na pewno napiszę.
Jeszcze raz bardzo dziękuje i pozdrawiam.