Matematyka.pl

Witam, mógłby ktoś pomóc rozwiązać zadanie, które polega na obliczeniu reszty z dzielenia liczby \(\displaystyle{ 731^{512}}\) przez \(\displaystyle{ 56}\) za pomocą kongruencji? Byłabym bardzo wdzięczna za wyjaśnienie krok po kroku.

Sposobów jest tu przynajmniej kilka.

Zacząć można od wyznaczenia reszty \(r\) z dzielenia \(731\) przez \(56\). Wtedy mamy przystawanie:
\(731\equiv r \pmod{56}\)
Po podniesieniu do kwadratu otrzymujemy:
\(731^2\equiv \ldots \pmod{56}\)
Po kolejnym podniesieniu do kwadratu:
\(731^4\equiv \ldots \pmod{56}\)
I tak dalej, aż dojdziemy do \(731^{512}\). Dość szybko się okaże, że obliczane reszty będą się powtarzać, dlatego to nie będzie dużo obliczeń.

Inny sposób, to wyznaczenie reszt z dzielenia \(731^{512}\) przez \(7\) i przez \(8\), a potem na tej podstawie obliczenie reszty z dzielenia przez \(56\).

Bardzo dziękuje

Dodano po 48 minutach 41 sekundach:
A jest jakiś jeszcze szybszy lub inny sposób pozwalający uniknąć tego potęgowania? Jest mnóstwo liczenia bo reszty w tym przypadku zaczynają się powtarzać dopiero przy 7 potędze, co przy liczbie 731 już daję ogromne liczby?

Bez tw. Eulera (i w zasadzie w pamięci) można to policzyć tak:

Ponieważ \(\displaystyle{ 731\equiv 3\pmod{56}, }\) więc \(\displaystyle{ 731^{512}\equiv 3^{512}=9^{256}\pmod{56}. }\) Ponadto \(\displaystyle{ 9^2\equiv 25\pmod{56}}\) i \(\displaystyle{ 25^2\equiv 9\pmod{56}}\). Stąd

\(\displaystyle{ 9^{256}\equiv 25^{128}\equiv 9^{64}\equiv 25^{32}\equiv 9^{16}\equiv 25^{8}\equiv 9^4\equiv 25^2\equiv 9.}\)

JK

Matemalove pisze: ↑21 sie 2022, o 12:38 .. Jest mnóstwo liczenia bo reszty w tym przypadku zaczynają się powtarzać dopiero przy 7 potędze, co przy liczbie 731 już daję ogromne liczby?

Nie przesadzaj:
\(731\equiv 3 \pmod{56}\\
731^2\equiv 3^2\equiv 9 \pmod{56}\\
731^4\equiv 9^2\equiv 81\equiv 25 \pmod{56}\\
731^8\equiv 25^2\equiv 625\equiv 9 \pmod{56}\\ \ldots \)

Pozdrawiam

Matemalove pisze: ↑21 sie 2022, o 12:38 co przy liczbie 731 już daję ogromne liczby?

Akurat wielkość tej liczby nie ma dużego znaczenia, bo wykonujemy na niej tylko jedno dzielenie z resztą, a potem już możemy o niej zapomnieć. Nie ma potrzeby obliczania \(731^2\) ani niczego podobnego. Gdyby zamiast \(731\) było \(11256565656731\), wynik zadania byłby dokładnie ten sam.