Chińskie Twierdzenie o Resztach | TEORIA LICZB #3
Вставка
- Опубліковано 1 лип 2024
- 00:00 Chińskie Twierdzenie o Resztach - definicja
03:57 Zadanie: układ kongruencji w którym moduły nie są względnie pierwsze
15:14 Znalezienie rozwiązania - metoda ogólna
26:04 Znalezienie rozwiązania - metoda "na palcach"
Film przygotowany zamiast ćwiczeń z Matematyki Dyskretnej w ramach walki z koronawirusem.
Autor: Oskar Skibski, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego. - Наука та технологія
świetny filmik z fantastyczną oprawą, chce się oglądać
Świetnie wytłumaczony materiał
Człowieku, ratujesz mi dupe
mi też
mi również
Jeżeli a^d = 1 (mod n)
to d | phi(n)
gdzie phi(n) to funkcja Eulera zwracająca liczbę liczb względnie pierwszych z n mniejszych od n
To może się przydać do obliczania odwrotności
ale na ogół wymaga to nieco więcej obliczeń niż rozszerzony algorytm Euklidesa
(Głównie dlatego że nie ma dobrej metody obliczania wartości funkcji Eulera
Mamy do dyspozycji rozkład na czynniki pierwsze albo zliczanie liczb względnie pierwszych z n
Obydwa sposoby nie są zbyt efektywne)
Wobec powyższego rozszerzony algorytm Euklidesa jest preferowany do obliczania odwrotności
To można było całkiem nieźle z rozszerzonego algorytmu Euklidesa rozwiązać
Nawet kiedyś napisałem do tego program jednak w nim założyłem że moduły są parami względnie pierwsze
Przepraszam, ale jaki ostatecznie jest wynik w 26:01? To będzie podane jako kongruencja, i nie ma wyniku całkowitego, czy jakoś inaczej to trzeba doliczyć?
O, i dziękuję bardzo, objaśnił Pan coś, co wyglądało na no nie do objaśnienia!
Rozwiązaniem całego zadania jest x = 5*25*49*1+21*9*49*11+12*9*25*22 (mod 9*25*49), a po uproszczeniu x = 2021 (mod 9*25*49). Tak samo wyszło nam drugą metodą.
@@oskarskibski Dziękuję bardzo!