Reszta z dzielenia potęgi

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Reszta z dzielenia potęgi

Post autor: Bran »

Jaka jest reszta z dzielenia liczby \(\displaystyle{ 17^{17^{17}}}\) przez \(\displaystyle{ 11}\)?


Łatwo zauważyć, że \(\displaystyle{ 17 \equiv 6 (\mbox{mod }11)}\)

Więc \(\displaystyle{ 17^{2} \equiv 6^2 (\mbox{mod }11)}\)

\(\displaystyle{ 36}\) modulo \(\displaystyle{ 11}\), to \(\displaystyle{ 3}\), więc:

\(\displaystyle{ 17^{2} \equiv 3 (\mbox{mod }11)}\)

Podniesiemy teraz kongruencje obustronnie do potęgi \(\displaystyle{ 4}\)

\(\displaystyle{ 17^{8} \equiv 3^4 (\mbox{mod }11)}\)

\(\displaystyle{ 81}\) modulo \(\displaystyle{ 11}\), to \(\displaystyle{ 4}\), zatem:

\(\displaystyle{ 17^{16} \equiv 4^2 (\mbox{mod }11)}\) więc:
\(\displaystyle{ 17^{16} \equiv 5 (\mbox{mod }11)}\), obie strony razy \(\displaystyle{ 17}\)

\(\displaystyle{ 17^{17} \equiv 85 (\mbox{mod }11)}\), czyli:
\(\displaystyle{ 17^{17} \equiv 8 (\mbox{mod }11)}\)

Zauważmy również, że \(\displaystyle{ 17^{17^{17}} = \left( 17^{17}\right)^{17^{16}}}\)

\(\displaystyle{ 17^{17} \equiv 8 (\mbox{mod }11)}\)
\(\displaystyle{ \left( 17^{17}\right)^{17^{16}} \equiv 8^5 (\mbox{mod }11)}\)

Z innej strony:
\(\displaystyle{ 8 \equiv -3 (\mbox{mod }11)}\)
\(\displaystyle{ 8^5 \equiv -243 (\mbox{mod }11)}\)

\(\displaystyle{ 11 \cdot 23 = 253}\)
\(\displaystyle{ -243 + 253 = 10}\)

\(\displaystyle{ 8^5 \equiv 10 (\mbox{mod }11)}\)

Zatem resztą z dzielenia \(\displaystyle{ 17^{17^{17}}}\) przez \(\displaystyle{ 11}\) jest liczba \(\displaystyle{ 10}\).


Najmniej jasne dla mnie jest, to przejście:
\(\displaystyle{ 17^{17} \equiv 8 (\mbox{mod }11)}\)
\(\displaystyle{ \left( 17^{17}\right)^{17^{16}} \equiv 8^5 (\mbox{mod }11)}\)

Nie wiem czy mogę zrobić tak, że jeśli:
\(\displaystyle{ a \equiv b (\mbox{mod }c)}\) i \(\displaystyle{ d \equiv e (\mbox{mod }c)}\), to \(\displaystyle{ a^d \equiv b^e (\mbox{mod }c)}\)?

Ale ogólnie całe zadanie jest dla mnie trudne, myślę, że to nie jest jedyny problem mojej próby rozwiązania.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Reszta z dzielenia potęgi

Post autor: Janusz Tracz »

Bran pisze: 10 kwie 2020, o 15:11 Nie wiem czy mogę zrobić tak, że jeśli:
\(\displaystyle{ a \equiv b (\mbox{mod }c)}\) i \(\displaystyle{ d \equiv e (\mbox{mod }c)}\), to \(\displaystyle{ a^d \equiv b^e (\mbox{mod }c)}\)?
To twierdzenie nie jest prawdziwe, łatwo znaleźć jakiś kontrprzykład, \(\displaystyle{ 2 \equiv 9 (\mbox{mod }7)}\) i \(\displaystyle{ 2 \equiv 9 (\mbox{mod }7)}\) przykładowo. Ale \(\displaystyle{ 2^2 \not \equiv 9^9 (\mbox{mod }7)}\). Co do zadania to zauważył bym najpierw ogólniej, że:

\(\displaystyle{ 17^{10}\equiv 1(\mbox{mod }11) }\)

Zatem

\(\displaystyle{ 17^{10n}\equiv 1(\mbox{mod }11) }\)

zatem

\(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)

Zatem problem uprościł się do wyliczenia \(\displaystyle{ 17^{17} (\mbox{mod }10)}\) (potem tylko podniesiemy do potęgi i już) co można zrobić następująco:

Zauważamy, że

\(\displaystyle{ 17^{4} \equiv 1 (\mbox{mod }10)}\)

zatem

\(\displaystyle{ 17^{4n} \equiv 1 (\mbox{mod }10)}\)

czyli

\(\displaystyle{ 17^{17} \equiv 17^{ (17 \mbox{mod }4)} \equiv 17 \equiv 7 (\mbox{mod }10)}\)

Zatem uaktualniamy nasze rozwiązanie do

\(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } \equiv 17^7 \equiv 6^7 \equiv 8 (\mbox{mod }11) }\)
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Reszta z dzielenia potęgi

Post autor: Bran »

Janusz Tracz pisze: 10 kwie 2020, o 17:08 \(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)
Nie rozumiem tego zapisu.
Janusz Tracz pisze: 10 kwie 2020, o 17:08 \(\displaystyle{ 17^{10n}\equiv 1(\mbox{mod }11) }\)

zatem

\(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)
i mam wrażenie, że mimo wszystko nie bardzo będę kumał tej implikacji (nawet jak wyjaśnisz powyższy zapis).
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Reszta z dzielenia potęgi

Post autor: Janusz Tracz »

Bran pisze: 10 kwie 2020, o 21:02
Janusz Tracz pisze: 10 kwie 2020, o 17:08 \(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)
Nie rozumiem tego zapisu.
Ten zapis jest standardowy i oznacza, że liczba \(\displaystyle{ 17^{17^{17}}}\) daje taką samą liczbę z dzielenia przez \(\displaystyle{ 11}\) jak liczba \(\displaystyle{ 17^{17^{17} (\mbox{mod }10) } }\). By uniknąć nierozumień oznaczmy liczbę \(\displaystyle{ 17^{17} (\mbox{mod }10)}\) przez \(\displaystyle{ r}\) wtedy mamy \(\displaystyle{ 17^{17^{17}} \equiv 17^{r} (\mbox{mod }11) }\)
Bran pisze: 10 kwie 2020, o 21:02
Janusz Tracz pisze: 10 kwie 2020, o 17:08 \(\displaystyle{ 17^{10n}\equiv 1(\mbox{mod }11) }\)
zatem
\(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)
i mam wrażenie, że mimo wszystko nie bardzo będę kumał tej implikacji (nawet jak wyjaśnisz powyższy zapis).
Grunt to pozytywne nastawienie... żeby zrozumieć tą implikacje musisz zrozumieć następujące rzeczy:

\(\displaystyle{ \bullet}\) Z małego twierdzenia Fermata wynika \(\displaystyle{ 17^{10}\equiv 1(\mbox{mod }11) }\) zatem \(\displaystyle{ 17^{10n}\equiv 1(\mbox{mod }11) }\)
\(\displaystyle{ \bullet}\) Rozważmy dowolne \(\displaystyle{ k\in\NN}\) (możesz myśleć, że jest duże) wtedy ów \(\displaystyle{ k}\) można zapisać jako \(\displaystyle{ k=10n+r}\) przy czym \(\displaystyle{ r\in\left\{ 0,1,2,3,...,9\right\} }\). Oczywiście \(\displaystyle{ k\equiv r(\mbox{mod }10)}\)

Posumujmy powyższe spostrzeżenia w rozważaniach nad \(\displaystyle{ 17^k(\mbox{mod }11)}\). Jak już mówiłem \(\displaystyle{ k=10n+r}\) zatem \(\displaystyle{ 17^k =17^{10n+r} =17^{10n} \cdot 17^{r} (\mbox{mod }11)}\) ale wcześniej mówiłem też, że \(\displaystyle{ 17^{10n}\equiv 1(\mbox{mod }11) }\) zatem \(\displaystyle{ 17^k \equiv17^{r} (\mbox{mod }11)}\). Teraz przypominam czym było \(\displaystyle{ r= k(\mbox{mod }10) }\) zatem ostatecznie \(\displaystyle{ 17^k \equiv17^{k(\mbox{mod }10)} (\mbox{mod }11)}\). Kładąc \(\displaystyle{ k=17^{17}}\) dostajesz szczególny przypadek tych rozważań. Analogiczne rozumowanie przeprowadziłem pokazując \(\displaystyle{ 17^{17} \equiv 17^{ (17 \mbox{mod }4)} \equiv 17 \equiv 7 (\mbox{mod }10)}\).
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Reszta z dzielenia potęgi

Post autor: Bran »

Janusz Tracz pisze: 11 kwie 2020, o 09:47
Bran pisze: 10 kwie 2020, o 21:02
Janusz Tracz pisze: 10 kwie 2020, o 17:08 \(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)
Nie rozumiem tego zapisu.
Ten zapis jest standardowy i oznacza, że liczba \(\displaystyle{ 17^{17^{17}}}\) daje taką samą liczbę z dzielenia przez \(\displaystyle{ 11}\) jak liczba \(\displaystyle{ 17^{17^{17} (\mbox{mod }10) } }\). By uniknąć nierozumień oznaczmy liczbę \(\displaystyle{ 17^{17} (\mbox{mod }10)}\) przez \(\displaystyle{ r}\) wtedy mamy \(\displaystyle{ 17^{17^{17}} \equiv 17^{r} (\mbox{mod }11) }\)
Może faktycznie wyraziłem się nieprecyzyjnie, chodziło mi konkretnie o zapis \(\displaystyle{ 17^{17^{17} (\mbox{mod }10) }}\). Ten zapis nie jest dla mnie do końca zrozumiały.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Reszta z dzielenia potęgi

Post autor: Janusz Tracz »

Bran pisze: 11 kwie 2020, o 15:38 Może faktycznie wyraziłem się nieprecyzyjnie, chodziło mi konkretnie o zapis \(\displaystyle{ \blue{17}^{\red{17^{17}} (\mbox{mod }10) }}\). Ten zapis nie jest dla mnie do końca zrozumiały.
Poprzez zapis \(\displaystyle{ a (\mbox{mod }n) }\) rozumiem resztę z dzielenia liczby \(\displaystyle{ a}\) przez \(\displaystyle{ n}\). Zakładam* przy tym, że jest to liczba ze zbioru \(\displaystyle{ \left\{ 0,1,2,...,n-1\right\} }\). Czyli po prostu \(\displaystyle{ a (\mbox{mod }n) \in \left\{ 0,1,2,...,n-1\right\} }\). Tak samo tu, mamy \(\displaystyle{ \red{17^{17}}}\) a ja rozważam resztę z dzielenia tej liczby przez \(\displaystyle{ 10}\) czyli właśnie w konwencji zapisu powyżej jest to \(\displaystyle{ \red{17^{17}} (\mbox{mod }10) }\). Jest to zatem jakaś liczba ze \(\displaystyle{ \green{\left\{ 0,1,2,...,9\right\}} }\). Udało się nawet ja wyznaczyć:
ja pisze:\(\displaystyle{ 17^{17} \equiv 17^{ 17 (\mbox{mod }4)} \equiv 17 \equiv \green{7} (\mbox{mod }10)}\)
A potem pokazałem\rozważałem

\(\displaystyle{ \blue{17}^{\red{\text{właśnie ta reszta}}}}\)

czyli gdy wiemy już, że \(\displaystyle{ \red{\text{właśnie ta reszta}}=\green{7}}\) to piszemy

\(\displaystyle{ \blue{17}^{\red{17^{17}}} \equiv \blue{17}^{\red{17^{17}} (\mbox{mod }10) } \equiv \blue{17}^{\green{7}} (\mbox{mod }11)}\)

* To formalnie nie jest założenie tylko własność reszty z dzielenia ale tu lepiej brzmi zakładam wszak chcę to podkreślić.
PS Kolory nie są tu przypadkowe. Trzymaj się kolorów gdybyś się zgubił skąd co pochodzi.

Dodano po 46 minutach 19 sekundach:
Tak mi przyszło do głowy, że może warta poruszenia tu jest jeszcze jedna sprawa terminologii. Ogólnie zapis:

\(\displaystyle{ a\equiv b (\mbox{mod }n)}\)

oznacza, że \(\displaystyle{ a}\) daje taką samą resztę z dzielenia jak \(\displaystyle{ b}\) przy dzieleniu przez \(\displaystyle{ n}\). Oczywiście można to powiedzieć na dużo innych równoważnych* sposobów takich jak: \(\displaystyle{ a-b}\) jest podzielne przez \(\displaystyle{ n}\), czy poprzez wprowadzanie relacji... ale ten pierwszy jest moim zdaniem w zupełności wystarczający jak na nasze potrzeby. Można ten zapis zapisywać na wiele innych równoważnych** sposobów takich jak:
przykłady:    
Czym innym jednak jest zapis:

\(\displaystyle{ a (\mbox{mod }n)}\)

który można spotkać w postaci \(\displaystyle{ \left[ a\right]_n }\) lub \(\displaystyle{ a \ \ \mbox{mod }n}\) i oznacza on

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Twierdzenie_o_dzieleniu_z_reszt%C4%85
\(\displaystyle{ a}\) przez \(\displaystyle{ n}\). Resztę wyznaczoną jednoznaczne ze zbioru \(\displaystyle{ \left\{ 0,1,2,...,n-1\right\} }\). Tu też można nadać temu napisowi bardzo ładną interpretację jako funkcja \(\displaystyle{ \text{mod} :\ZZ \times \NN_{>0} \rightarrow \ZZ}\) dana wzorem \(\displaystyle{ a \text{ mod} n= a-n \cdot \left\lfloor \frac{a}{n} \right\rfloor }\) ale pozostańmy, przy reszcie z dzielenia \(\displaystyle{ a}\) przez \(\displaystyle{ n}\). Mimo, że są to dwie różne rzeczy to są mocno spokrewnione niemniej jednak by używać ich swobodnie trzeba wiedzieć co rozumiemy pisząc znaczek \(\displaystyle{ \text{mod}}\). I być może nie podkreśliłem tego zbyt dobitnie w rozwiązaniu ale na swoją obronę mam to, że nikt tego nie podkreśla (po prostu wynika to z kontekstu i trzeba o tym wiedzieć).

* Równoważnych w sensie definicji.
** Równoważnych w sensie znaczenia znaczków.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Reszta z dzielenia potęgi

Post autor: Bran »

Janusz Tracz pisze: 11 kwie 2020, o 09:47 \(\displaystyle{ 17^k =17^{10n+r} =17^{10n} \cdot 17^{r} (\mbox{mod }11)}\)
W poprzednim Twoim wyjaśnieniu pojawił się taki zapis, domyślam się, że to również jakiś skrót, w którym powinienem się połapać z kontekstu, ale mimo wszystko nie jestem pewny o co chodziło...
Mógłbyś jeszcze to wyjaśnić?

Zacytuję kontekst
Janusz Tracz pisze: 11 kwie 2020, o 09:47 Posumujmy powyższe spostrzeżenia w rozważaniach nad \(\displaystyle{ 17^k(\mbox{mod }11)}\). Jak już mówiłem \(\displaystyle{ k=10n+r}\) zatem \(\displaystyle{ 17^k =17^{10n+r} =17^{10n} \cdot 17^{r} (\mbox{mod }11)}\) ale wcześniej mówiłem też, że \(\displaystyle{ 17^{10n}\equiv 1(\mbox{mod }11) }\) zatem \(\displaystyle{ 17^k \equiv17^{r} (\mbox{mod }11)}\). Teraz przypominam czym było \(\displaystyle{ r= k(\mbox{mod }10) }\) zatem ostatecznie \(\displaystyle{ 17^k \equiv17^{k(\mbox{mod }10)} (\mbox{mod }11)}\). Kładąc \(\displaystyle{ k=17^{17}}\) dostajesz szczególny przypadek tych rozważań. Analogiczne rozumowanie przeprowadziłem pokazując \(\displaystyle{ 17^{17} \equiv 17^{ (17 \mbox{mod }4)} \equiv 17 \equiv 7 (\mbox{mod }10)}\).
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Reszta z dzielenia potęgi

Post autor: Janusz Tracz »

Bran pisze: 13 kwie 2020, o 14:39
Janusz Tracz pisze: 11 kwie 2020, o 09:47 \(\displaystyle{ 17^k =17^{10n+r} =17^{10n} \cdot 17^{r} (\mbox{mod }11)}\)
W poprzednim Twoim wyjaśnieniu pojawił się taki zapis, domyślam się, że to również jakiś skrót, w którym powinienem się połapać z kontekstu, ale mimo wszystko nie jestem pewny o co chodziło...
Nie to nie jest skrót. To było tylko bardziej szczegółowe wyjaśnienie dlaczego zachodzi \(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11)}\). Pokazałem, że \(\displaystyle{ 17^{k} \equiv17^{k(\mbox{mod }10) } (\mbox{mod }11)}\) rozrabiając \(\displaystyle{ k}\) na tyle dziesiątek ile się tylko da i ewentualną resztę czyli zapisałem \(\displaystyle{ k}\) w postaci \(\displaystyle{ 10n+r}\) gdzie \(\displaystyle{ r\in\left\{ 0,1,2,...,9\right\} }\). A ponieważ \(\displaystyle{ 17^{10n}\equiv 1(\mbox{mod }11)}\) to \(\displaystyle{ 17^k =17^{10n+r} =17^{10n} \cdot 17^{r} \equiv 17^{r} \equiv 17^{k \text{ mod} 10} (\mbox{mod }11)}\).
Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 340
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 42 razy
Pomógł: 60 razy

Re: Reszta z dzielenia potęgi

Post autor: Gosda »

Zapis \(\displaystyle{ a \bmod b}\) jako reszta z dzielenia \(\displaystyle{ a}\) przez \(\displaystyle{ b}\) nie jest standardowy, mam wrażenie, ale często używany przez ludzi związanych z informatyką :D

W teorii liczb stosuje się notację \(\displaystyle{ a \equiv b \mod c}\) jako skrót od \(\displaystyle{ c \mid b - a}\) jeżeli \(\displaystyle{ a, b, c}\) są liczbami naturalnymi. Ogólniej, jeżeli \(\displaystyle{ I}\) jest ideałem w pierścieniu \(\displaystyle{ R}\), kiedy piszemy \(\displaystyle{ x \equiv y \mod I}\), myślimy \(\displaystyle{ x - y \in I}\). Znak \(\displaystyle{ {} \bmod {}}\) bez \(\displaystyle{ \equiv}\) nie ma w tym znaczeniu sensu.
ODPOWIEDZ