Arytmetyka modularna

03.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Arytmetyka modularna jest kolejnym narzędziem matematycznym ułatwiającym infomatykom rozwiązywanie problemów algorytmicznych.

Rozważmy następujące zadania:


Problem 1. Czy 13 dzieli 16971461287794?


Problem 2. Jasio kupił w sklepie dużą paczkę cukierków. Teraz zastanawia się kogo zaprosić na swoje urodziny. Jeśli zaproszę tylko Tomka i Bartka to po podzieleniu cukierków na nas troje pozostanie jeden cukierek. Jeśli przyjdzie jeszcze Kasia, to zostaną dwa cukierki. O! Ale jeśli zaproszę jeszcze Marcina, to cukierki będzie można równo podzilić. Ile cukierków było w paczce Jasia?


Problem 3. Jakie są trzy ostatnie cyfry liczby $ 3^{14404} $?

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ści

Niech $ a, b $ będą liczbami całkowitymi, a $ n $ liczbą całkowitą dodatnią. Definiujemy kongruencje w następujący sposób:

$ a \equiv b \pmod n \stackrel{def.}{\Longleftrightarrow} n | (a-b) $

Czytamy a przystaje do b modulo n, albo a kongruentne z b.

Ciekawa i ważna własność kongruencji to taka, że $ a \equiv b \pmod n  $ wtedy i tylko wtedy, gdy liczby $ a $ oraz $ b $ przy dzieleniu przez $ n $ daje tą samą resztę. Na przykład $ 53 $ oraz $ 73 $ dają tą samą resztę (mianowicie $ 3 $) przy dzieleniu przez $ 10 $. Faktycznie zachodzi $ 10 | (53-73) $ bo $ 53 - 73 = -20 $ a $ 10 $ dzieli $ -20 $. Zatem zachodzi $ 53 \equiv 73 (mod 10) $. Kolejne ważne własności kongruencji to:

  • Zwrotność kongruencji $ a \equiv a \pmod n $
  • Symetryczność kongruencji $ a \equiv b \pmod n \Rightarrow b \equiv a \pmod n $
  • Przechodność kongrunecji $ a \equiv b \pmod n \wedge b \equiv c \pmod n \Rightarrow a \equiv c \pmod n  $

Ponadto jeśli:  $ a \equiv b \pmod n $ oraz $ c \equiv d \pmod n $ to zachodzi:

  • $ a + c \equiv b + d \pmod n $
  • $ a - c \equiv b - d \pmod n $
  • $ a \times c \equiv b \times d \pmod n $

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 $ kn = a - b $ analogicznie istnieje takie l, że $ ln = c - d $. Dodając oba równania do siebie stronami otrzymujemy, że $ (k + l)n = (a + c) - (b + d) $. Zatem $ a + c \equiv b + d \pmod n $. Teraz mnożenie. Mam podobnie jak ostatnio: $ kn = a - b $ oraz $ ln = c - d $ przerzućmy b oraz d na drugą stronę. Otrzymamy: $ kn + b = a $ oraz $ ln + d = c $. Mnożąc stronami obie równości otrzymamy: $ n(kln + bl + kd) + bd = ac $. Przerzucając $ b $ 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:

$ 2\times5 \equiv 2\times2 \pmod 6 $

Faktycznie $ 10 $ przystaje do $ 4 $ modulo $ 6 $, bo $ 10 - 4 = 6 $. Gdy jednak podzielimy obustronnie przez $ 2 $ otrzymamy:

$ 5 \equiv 2 \pmod 6 $

Co już nie jest prawdą, bo $ 5 - 2 = 3 $, a $ 3 $ nie dzieli się przez $ 6 $. Okazuję się, że równanie $ a \equiv b \pmod $ możemy obustronnie bezpiecznie podzielić przez $ k $ wtedy gdy liczba $ k $ jest względnie pierwsza z $ n $. Czyli gdy $ gcd(k, n) = 1 $. 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 $ a\times k \equiv b\times k \pmod \left(n \times k\right) $ to $  a \equiv b \pmod n $.

Z faktu, że możemy dodawać, odejmować i mnożyć wynika następujący wniosek: Jeśli $ a \equiv b \pmod n $ to dla dowolnego wielomianu $ w(x) $ o współczynnikach całkowitych: $ w(a) \equiv w(b) \pmod n $.

Dla przykładu niech $ w(x) = 3x^3  + 5x^2 - 2x + 17 $. Skoro wiemy, że $ 11 \equiv 3 \pmod 4  $ to musi zachodzić $ w(11) \equiv w(3) \pmod 4 $. Faktycznie! Przecież:

$ w(11) = 3 \times 11^3 + 5 \times 11^2 - 2 \times 11 + 17 = 3 \times 1331 + 5 \times 121 - 2 \times 11 + 17 = 3993 + 605 - 22 + 17 = 4593 $

natomiast $ w(3) = 3 \times 3^3 + 5 \times 3^2 - 2 \times 3 + 17 = 81 + 45 - 6 + 17 = 137 $, a $ 4593 \equiv 137 \pmod 4 $ bo $ 4593 - 137 = 4456 $, a przecież $ 4 $ dzieli $ 4456 $ bo $ 4456 = 4 \times 1114 $.

3.5
Twoja ocena: Brak Ocena: 3.5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com