Arytmetyka modularna

Arytmetyka modularna

Wstęp:
W tym opracowaniu poznasz podstawy arytmetyki modularnej, a także dowiesz się jakie są jej cechy charakterystyczne.

Arytmetyka modularna – definicja:
Arytmetyka modularna (zwana również arytmetyką reszt) to rodzaj systemu liczbowego, który jest ściśle związany z cyklicznością i okresowością. Występują tu wyłącznie liczby całkowite, które po osiągnięciu określonej wartości (nazywanej modułem) „zataczają koło” i zaczynają się powtarzać (w tej samej kolejności). Lepiej zobrazuje to poniższy przykład:
Załóżmy, że i reszty r, oraz a, b, c, r Z (liczby całkowite), czyli w wyniku podzielenia liczby „a” przez liczbę „b” powstaje nam liczba „c” i pewna reszta „r” (w takim zapisie od reszty „r” ważniejsza jest liczba „c”). Wtedy zapis postaci: „a mod b” (co czytamy jako: a modulo b), będzie oznaczał, że interesuje nas jedynie reszta z dzielenia liczby „a” przez liczbę „b”, więc: a mod b = r.
Czyli gdy: i reszty r to zawsze prawdziwa jest również równość: a mod b = r (gdzie liczba „b” nazywana jest modułem).
A teraz kilka przykładów:
3 mod 2 = 1 (bo i 1 reszty)
10 mod 3 = 1 (bo i 1 reszty)
17 mod 5 = 2 (bo i 2 reszty)
6 mod 6 = 0 (bo i 0 reszty)

Arytmetyka modularna – własności:
Zobaczmy co się stanie gdy będziemy dzielić kolejne liczby przez 4:
= 0 i 0 reszty (czyli 0 mod 4 = 0)
= 0 i 1 reszty (czyli 1 mod 4 = 1)
= 0 i 2 reszty (czyli 2 mod 4 = 2)
= 0 i 3 reszty (czyli 3 mod 4 = 3)
= 1 i 0 reszty (czyli 4 mod 4 = 0)
= 1 i 1 reszty (czyli 5 mod 4 = 1)
= 1 i 2 reszty (czyli 6 mod 4 = 2)
= 1 i 3 reszty (czyli 7 mod 4 = 3)

Reszty z dzielenia zaczynają rosnąć od 0 do 3. Po „przekroczeniu” 3 cała sekwencja się powtarza i „ciągnie się” w nieskończoność. Ogólnie można to zapisać tak:
a mod b = r, gdzie r <0, b - 1> (oraz r Z)
A zatem nasza reszta może przyjmować wartości całkowite od 0 do liczby o jeden mniejszej od modułu (do liczby „b – 1”).
Można również zauważyć, że wartości reszty powtarzają się co wielokrotność modułu (w przypadku powyżej, gdy moduł = 4, wartości reszty powtarzają się co 4 (czyli 1 mod 4 = 5 mod 4). Z tego można wysnuć następujący wniosek:
a mod b = (a + b) mod b = (a + 2b) mod b = ……… , czyli:
(a + k b) mod b = a mod b (dla a, b, r, k Z)

Podsumowanie:
W tym opracowaniu mogłeś poznać podstawy arytmetyki modularnej, a także dowiedziałeś się jakie są jej cechy charakterystyczne.