Arytmetyka modularna
03.12.2009 - Krzysztof Piecuch
Arytmetyka modularna jest kolejnym narzędziem matematycznym ułatwiającym infomatykom rozwiązywanie problemów algorytmicznych. Rozważmy następujące zadania:
Powyższe problemy mogą wydawać się trudne, ale wkrótce je rozwiążemy używając jedynie ołówka, kartki i... arytmetyki modularnej. Definicja i podstawowe własnościNiech będą liczbami całkowitymi, a liczbą całkowitą dodatnią. Definiujemy kongruencje w następujący sposób: Czytamy a przystaje do b modulo n, albo a kongruentne z b. Ciekawa i ważna własność kongruencji to taka, że wtedy i tylko wtedy, gdy liczby oraz przy dzieleniu przez daje tą samą resztę. Na przykład oraz dają tą samą resztę (mianowicie ) przy dzieleniu przez . Faktycznie zachodzi bo a dzieli . Zatem zachodzi . Kolejne ważne własności kongruencji to:
Ponadto jeśli: oraz to zachodzi: Spróbujmy udowodnić jedną z tych własności. Na przykład dodawanie i mnożenie. Resztę pozostawiam czytelnikowi do samodzielnego udowodnienia. Jeśli a jest kongruentne z b to istnieje taka liczba k, że analogicznie istnieje takie l, że . Dodając oba równania do siebie stronami otrzymujemy, że . Zatem . Teraz mnożenie. Mam podobnie jak ostatnio: oraz przerzućmy b oraz d na drugą stronę. Otrzymamy: oraz . Mnożąc stronami obie równości otrzymamy: . Przerzucając na drugą stronę otrzymamy żądaną równość. Z powyższych równań oraz ze zwrotności kongruencji wynika, że do obu stron kongruencji możemy dodać, odjąć jakąś liczbę całkowitą, lub pomnożyć obie strony przez dowolną liczbę całkowitą. Okazuje się, że nie zawsze można dzielić obustronnie przez dowolną liczbę. Weźmy na przykład równanie: Faktycznie przystaje do modulo , bo . Gdy jednak podzielimy obustronnie przez otrzymamy: Co już nie jest prawdą, bo , a nie dzieli się przez . Okazuję się, że równanie możemy obustronnie bezpiecznie podzielić przez wtedy gdy liczba jest względnie pierwsza z . Czyli gdy . O tym dlaczego tak jest dowiemy się w następnym rozdziale. A teraz dowiemy się jeszcze, że możemy dowolnie dzielić wszystkie trzy liczby w kongruencji: Jeśli to . Z faktu, że możemy dodawać, odejmować i mnożyć wynika następujący wniosek: Jeśli to dla dowolnego wielomianu o współczynnikach całkowitych: . Dla przykładu niech . Skoro wiemy, że to musi zachodzić . Faktycznie! Przecież:
natomiast , a bo , a przecież dzieli bo .
(4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com