Arytmetyka modularna
03.12.2009 - Krzysztof Piecuch
Rozwiązywanie liniowych równań modularnychPowiedzmy, że szukamy liczbę , taką która spełnia następujące liniowe równanie modularne: Będziemy przekształcać to równanie, aż go rozwiążemy. Zaczniemy od przerzucenia liczby na prawą stronę równania: Teraz spróbujemy pozbyć się minusa z prawej strony. Możemy to zrobić dodając coś do prawej strony. Jednak jednocześnie nie chcemy psuć lewej strony. Korzystając zatem z tego, że możemy dodać 5 do prawej strony nie dodając nic do lewej. W zwykłej równośli liniowej podzielilibyśmy teraz obie strony przez 3. Czyli innymi słowy pomnożylibyśmy obie strony przez . Zrobimy coś podobnego - jednak ponieważ jest to równanie modularne, przemnożymy obie stron przez , czyli przez 2. Wiemy, że dla dowolnego x zachodzi . aby otrzymać samo z lewej strony, oraz aby otrzymać liczbę z przedziału z prawej. Odejmijmy to równanie od naszego i ostatecznie otrzymamy rozwiązanie naszego zadania: Zatem jest postaci: . Są to jedyne rozwiązania tego równania. Zatem w przedziale istnieje tylko jedno rozwiązanie - . Istnieją jednak równania które mają więcej rozwiązań. Rozważmy na przykład równanie: . To równanie ma aż 3 rozwiązania: . Bo dzieląc wszystkie trzy liczby przez 3 otrzymamy: . Natomiast równanie: w ogóle nie ma rozwiązania. To dlatego, że w tym miejscu chcielibyśmy się pozbyć trójki przy iksie. Nie możemy tego zrobić, bo nie ma odwrotności modulo 6. Nie możemy też przez nic podzielić wszystkich trzech liczb, bo największy wspólny dzielnik tych wszystkich liczb wynosi... 1. Ogólniej mówiąc: ma rozwiązanie wtedy i tylko wtedy gdy . Dowód tego faktu nie jest bardzo skomplikowany, ale pominiemy go. Jeśli równanie ma w ogóle rozwiązanie, to ma ich dokładnie (w przedziale ), a rozwiązania są równooddalone od siebie. Zatem wystarczy znaleźć jedno rozwiązanie i na podstawie jego łatwo otrzymamy pozostałe. Na przykład: Łatwo zgadujemy, że jednym z rozwiązań jest . Wiedząc, że mamy 4 rozwiązania i są one równooddalone wnioskujemy, że kolejne rozwiązania różnią się od siebie o . Zatem rozwiązania to: . Albo inaczej - rozwiązania tego równania są postaci: dla każdego k. Napiszemy teraz prostą procedurę, która wypisuje wszystkie rozwiązania liniowego równania modularnego. void ModularLinearEquationSolver(int a, int b, int n) (4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com