Obliczanie reszt

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
caballo795
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 12 sty 2019, o 15:32
Płeć: Mężczyzna
Lokalizacja: Poznań

Obliczanie reszt

Post autor: caballo795 »

Poszukuje materiałów, zależności, wzorów które pozwoliłyby mi rozwiązać zadania podobne do poniższego.

Wykorzystujac algorytm Euklidesa oblicz.
\(\displaystyle{
20^{128}\mod 1323 \\
55^{5}\mod 504
}\)
Ostatnio zmieniony 15 sty 2020, o 21:00 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: \mod. Więcej szacunku dla Euklidesa.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Obliczanie reszt

Post autor: Premislav »

Nie widzę, by algorytm Euklidesa miał tu coś do rzeczy, być może jest to jakaś metoda rozwiązania za pomocą algorytmu Euklidesa (rozszerzonego?), której w tej chwili nie kojarzę.
Mamy
\(\displaystyle{ 1323=27\cdot 49 }\) i \(\displaystyle{ \NWD(27, 49)=1}\), można od tego zacząć.
Obliczymy wartość funkcji Eulera dla \(\displaystyle{ 27}\) i \(\displaystyle{ 49}\) zgodnie ze znanymi wzorkami:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Funkcja_%CF%86

\(\displaystyle{ \varphi(27)=\varphi\left(3^{3}\right)=(3-1)\cdot 3^{3-1}=18, \varphi(49)=\varphi\left(7^{2}\right)=(7-1)\cdot 7^{2-1}=42}\)
Na mocy twierdzenia Eulera mamy więc
\(\displaystyle{ 20^{18}\equiv 1\pmod{27}}\) oraz \(\displaystyle{ 20^{42}\equiv 1\pmod{49}}\), stąd przez banalną indukcję dostajemy, że dla dowolnego \(\displaystyle{ k\in \NN^{+}, \ 20^{18k}\equiv 1\pmod{27}, \ 20^{42k}\equiv 1\pmod{49}}\).
Odnotujmy teraz, że \(\displaystyle{ 128=126+2}\), a dzielnikami liczby \(\displaystyle{ 126=2\cdot 3^{2}\cdot 7}\) są zarówno \(\displaystyle{ 18}\), jak i \(\displaystyle{ 42}\).
Otrzymujemy zatem (tak naprawdę przemyca się tu w pewnej formie chińskie twierdzenie o resztach)
\(\displaystyle{ 20^{126}\equiv 1\pmod{1323}\\20^{128}=20^{126}\cdot 20^{2}\equiv 20^{2}\pmod{1323}}\)
czyli podsumowując, \(\displaystyle{ 20^{128}\equiv 400\pmod{1323}}\).

Dodano po 16 minutach :
W tym drugim można po prostu podnieść do potęgi na pałę (na przykład korzystając ze wzorów skróconego mnożenia) i obliczyć na chama pod kreską. :D Jeśli jednak myślisz o bardziej kształcącym sposobie, to można zauważyć, że \(\displaystyle{ 504=7\cdot 8\cdot 9}\), a ponadto:
\(\displaystyle{ 55\equiv 1\pmod{9}, \ 55^{5}\equiv 1\pmod{9}\\55\equiv -1\pmod{7}, \ 55^{5}\equiv (-1)^{5}\pmod{7}, \ 55^{5}\equiv 6\pmod{7}\\55\equiv -1\pmod{8}, \ 55^{5}\equiv (-1)^{5}\pmod{8}, \ 55^{5}\equiv 7\pmod{8}}\)
czyli szukamy rozwiązania układu kongruencji:
\(\displaystyle{ \begin{cases} x\equiv 6\pmod{7}\\x\equiv 7\pmod{8}\\x\equiv 1\pmod{9}\end{cases}}\)
w \(\displaystyle{ \ZZ_{504}}\). Takie rozwiązanie będzie jedyne na mocy chińskiego twierdzenia o resztach i możesz skorzystać teraz z metody generowania rozwiązania tu opisanej:

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Existence_%28direct_construction%29


Dodano po 1 minucie 35 sekundach:
Ogólnie przydatne zagadnienia w takich zadaniach to twierdzenie Eulera (i jego szczególny przypadek, czyli małe twierdzenie Fermata), chińskie twierdzenie o resztach, wzory skróconego mnożenia, cechy podzielności przez małe liczby.
caballo795
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 12 sty 2019, o 15:32
Płeć: Mężczyzna
Lokalizacja: Poznań

Re: Obliczanie reszt

Post autor: caballo795 »

Prowadzący podał takie rozwiązanie pierwszego zadania.
\(\displaystyle{
1323 = 3^2\cdot 7^2\\
\varphi(1323)=\varphi(3^3)\varphi(7^2)=2\cdot 3^2\cdot 6\cdot 7=756 \\
\lambda(1323)=NWW(\lambda(3^3),\lambda(7^2)) = NWW(2\cdot 3^2,6\cdot 7 )= 126 \\
20^{128} \mod 1323 = 20^{128\mod 126}\mod 1323 = 20^2 \mod 1323 = 400
}\)

Jesteś w stanie to wytłumaczyć, bo twoje rozwiazanie jest dosc obszerne i trudne.
Ostatnio zmieniony 16 sty 2020, o 15:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8567
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Obliczanie reszt

Post autor: kerajs »

2)

\(\displaystyle{ 55^5 \mod 504 =(55^2)^2 \cdot 55 \mod 504 =(6 \cdot 504+1)^2 \cdot 55 \mod 504 \equiv 1 \cdot 55 \mod 504 =55}\)
Ostatnio zmieniony 16 sty 2020, o 19:07 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Obliczanie reszt

Post autor: Premislav »

caballo795 pisze:Jesteś w stanie to wytłumaczyć, bo twoje rozwiazanie jest dosc obszerne i trudne.
Wybacz, ale z tego śmiechłem hardo (bez złośliwości). Przecież to jest praktycznie to samo, co ja napisałem, tylko bez użycia języka polskiego, a jedynie symboli. Obszerność bierze się z tego, że używam zdań w języku polskim, a co do trudności, to nie wiem, skąd taka opinia, z tego, co patrzę, to prowadzący tez używa funkcji Eulera i twierdzenia Eulera.
ODPOWIEDZ