Reszta z dzielenia potęgi
-
- 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
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.
Ł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.
- Janusz Tracz
- 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
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) }\)
-
- 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
Nie rozumiem tego zapisu.Janusz Tracz pisze: ↑10 kwie 2020, o 17:08 \(\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).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) }\)
- Janusz Tracz
- 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
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:02Nie rozumiem tego zapisu.Janusz Tracz pisze: ↑10 kwie 2020, o 17:08 \(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)
Grunt to pozytywne nastawienie... żeby zrozumieć tą implikacje musisz zrozumieć następujące rzeczy:Bran pisze: ↑10 kwie 2020, o 21:02i mam wrażenie, że mimo wszystko nie bardzo będę kumał tej implikacji (nawet jak wyjaśnisz powyższy zapis).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) }\)
\(\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)}\).
-
- 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
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.Janusz Tracz pisze: ↑11 kwie 2020, o 09:47Ten 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:02Nie rozumiem tego zapisu.Janusz Tracz pisze: ↑10 kwie 2020, o 17:08 \(\displaystyle{ 17^{17^{17}} \equiv 17^{17^{17} (\mbox{mod }10) } (\mbox{mod }11) }\)
- Janusz Tracz
- 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
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ć:
A potem pokazałem\rozważałemja pisze:\(\displaystyle{ 17^{17} \equiv 17^{ 17 (\mbox{mod }4)} \equiv 17 \equiv \green{7} (\mbox{mod }10)}\)
\(\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:
\(\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
* Równoważnych w sensie definicji.
** Równoważnych w sensie znaczenia znaczków.
-
- 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
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...Janusz Tracz pisze: ↑11 kwie 2020, o 09:47 \(\displaystyle{ 17^k =17^{10n+r} =17^{10n} \cdot 17^{r} (\mbox{mod }11)}\)
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)}\).
- Janusz Tracz
- 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
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)}\).Bran pisze: ↑13 kwie 2020, o 14:39W 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...Janusz Tracz pisze: ↑11 kwie 2020, o 09:47 \(\displaystyle{ 17^k =17^{10n+r} =17^{10n} \cdot 17^{r} (\mbox{mod }11)}\)
- Gosda
- 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
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ą
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.
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.