Arytmetyka modularna
03.12.2009 - Krzysztof Piecuch
Zajmijmy się teraz sytuacją w której mamy więcej równań. Rozwiązywanie układu modularnych równań liniowychZadanie z cukierkami możemy zapisać za pomocą trzech liniowych równań modularnych: Układ taki rozwiązujemy rozwiązując pierw pierwsze równanie, a następnie wynik wstawiając do kolejnego. Równanie jest trywialne. Jego rozwiązanie to . Wynik ten wstawiamy do drugiego równania: Stąd zatem . Wstawiamy ten wynik do ostatniego równania: Ostatecznie czyli . Ponieważ w treści mowa jest o dużej paczce cukierków, możemy wnioskować, że jest ich raczej a nie . Odpowiadamy zatem: W paczce Jasia było cukierków. Metoda ta jest dobra do rozwiązywania ręcznego małych układów równań z małymi liczbami całkowitymi. Poznamy teraz twierdzenie, które ułatwi nam rozwiązywanie większych układów równań. Chińskie twierdzenie o resztachPowiedzmy, że mamy dany układ k liniowych równań modularnych: Przy czym wszystkie są parami względnie pierwsze. Wtedy: gdzie oraz . Zobaczmy jak to działa. Weźmy dobrze nam znany układ liniowych równań modularnych: Obliczamy kolejno poszczególne parametry. Zaczniemy od . Teraz kolejne : , oraz . Stąd . Stąd czyli . Uzyskaliśmy zatem ten sam wynik, gdy liczyliśmy ten układ "na piechotę". Więcej o chińskim twierdzeniu o resztach można przeczytać tutaj w artykule Agaty Murawskiej. Funkcja EuleraFunkcją Eulera definiujemy na liczbach naturalnych w następujący sposób. jest równa liczbie liczb naturalnych mniejszych od , które są względnie pierwsze z . Rozważmy przykład: . Liczby mniejsze od 6 to 1, 2, 3, 4 oraz 5. Liczby 2, 3 oraz 4 nie są liczbami względnie pierwszymi z 6; natomiast 1 oraz 5 są. Zatem mamy dwie liczby naturalne mniejsze od 6, które są z 6 względnie pierwsze. Zatem . Natomiast ponieważ 11 jest liczbą pierwszą czyli jest względnie pierwsza z wszystkimi liczbami: . Zadania Na następnej stronie znajdują się zadania programistyczne. Wszystkich chętnych zapraszam do rozwiązywania!$ (4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com