« poprzedni punkt |
Zdefiniujemy teraz ważną relację równoważności w zbiorze liczb całkowitych.
Niech m będzie ustaloną liczbą naturalną większą od 1.
Definicja
Liczby a i b są w relacji kongruencji 'modulo m', co oznaczamy: a º b (mod m), wtedy i tylko wtedy gdy m|(b - a).
Inaczej mówimy, że liczba a przystaje do b modulo m, lub że przystają do siebie modulo m.
Zauważmy, że z definicji relacji kongruencji wynika, że a º b (mod m), wtedy i tylko wtedy gdy reszta z dzielenia a przez m jest równa reszcie z dzielenia b przez m.
Przykład
"
(a, b Î
Z) a º
b (mod 1)
Relacja "º" jest relacją równoważności, tzn. jest:
Ponieważ relacja przystawania jest relacją równoważności, zbiór liczb całkowitych
rozkłada się na rozłączne klasy równoważności tej relacji. Zauważmy, że
klas równoważności jest dokładnie m, tyle ile możliwych różnych
reszt z dzielenia przez m. Klasy równoważności, które
oznaczymy przez Ai, gdzie
i=0,...,m-1; mogą być zapisane jako:
Ai = { p Î Z: reszta z dzielenia p przez m równa się i },
i zachodzi:
Z = .
Przykład
Dla m = 7 zbiór reszt z dzielenia przez 7 jest postaci {0, 1, 2, 3, 4, 5, 6}.
Wyodrębniamy kolejno zbiory A1, ...., A6:
A0 = { pÎ
Z: reszta z dzielenia p przez 7 równa się 0} = {0, 7, 14, 21, 28, 35, .......}
A1 = { pÎ
Z: reszta z dzielenia p przez 7 równa się 1} = {1, 8, 15, 22, 29, 36, .......}
A2 = { pÎ
Z: reszta z dzielenia p przez 7 równa się 2} = {2, 9, 16, 23, 30, 37, .......}
A3 = { pÎ
Z: reszta z dzielenia p przez 7 równa się 3 } = {3, 10, 17, 24, 31, 38, .......}
A4 = { pÎ
Z: reszta z dzielenia p przez 7 równa się 4} = {4, 11, 18, 25, 32, 39, .......}
A5 = { pÎ
Z: reszta z dzielenia p przez 7 równa się 5} = {12, 19, 26, 33, 40, .......}
A6 = { pÎ
Z: reszta z dzielenia p przez 7 równa się 6} = {5, 13, 20, 27, 34, 41, .......}
Twierdzenie
Jeśli a º b (mod m) oraz c º d (mod m), wówczas:
Dowód:
Relacja kongruencji modulo m służy do zdefiniowania działań dodawania i mnożenia liczb modulo m, które często wykorzystuje się w informatyce.
Określimy dla danej liczby naturalnej m > 1 działanie dodawania i mnożenia w Z tak, by wyniki tych działań należały do zbioru reszt z dzielenia przez m:
{ 0, 1, ..., m - 1}
np.: dla m = 6, zbiór reszt z dzielenia przez 6 jest postaci: {0, 1, 2, 3, 4, 5}.
Definicja
Dla liczb całkowitych p, q przyjmiemy:
(p + q) (mod m) = reszta z dzielenia p + q przez m,
(p ×
q) (mod m) = reszta z dzielenia p ×
q przez m.
(p + q) (mod m) - suma p i q modulo m,
(p ×
q) (mod m) - iloczyn p i q modulo m.
Przykład
(5 + 2)(mod 3) = 1
(6 ×
5)(mod 4) = 2
Zbiór reszt { 0,1,.., m -1} oznaczamy Zm.
Działania + (mod m) i × (mod m) są określone w Zm.
Tabelki działań w Z2.
+ (mod 2) | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 0 |
× (mod 2) | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Przykład
Do generacji liczb pseudolosowych używa się często generatorów kongruencyjnych. W ich przypadku każda następna wygenerowana liczba xn+1 jest resztą z dzielenia iloczynu poprzednio wygenerowanej liczby xn i liczby A przez B. Liczby A i B są specjalnie dobranymi liczbami mającymi zapewnić pseudolosowość generatora. Na przykład, zadawalający generator uzyskuje się przyjmując:
B = 2147483647 i A = 16807.
Mamy zatem:
Twierdzenie chińskie o resztach
Jeżeli liczby całkowite p1, p2, ..., pn są parami względnie pierwsze, tzn. NWD(pi, pj)=1 dla i ¹ j, to dla każdego układu liczb całkowitych q1, q2, ...,qn istnieje liczba całkowita q o tej własności, że:
q º qi (mod pi).
Przykład
Znaleźć liczbę q, która podzielona przez liczbę pi da resztę qi gdzie:
p1 = 4, p2 = 5, p3 = 7,
q1 = 0, q2 = 4, q3 = 3.
Z warunków wynika, że 4 dzieli liczbę q - 0 = q, zatem q = 4a.
Podobnie:
5| (q - 4) Þ
q = 5b + 4
7| (q - 3) Þ
q = 7c + 3.
Powyższy układ równań jest niejednoznaczny i jest spełniony np. dla a = 6, b = 4, c = 3. Stąd jednym z możliwych rozwiazań jest liczba q = 24.
Przykład
Zadanie to przytacza matematyk chiński Cin-Kin-Czang w dziele "Su-szou-kin-czang", co znaczy "Dziewięć działów sztuki liczbowej".
Do trzech beczek wsypano jednakowe ilości ryżu. Do składu zakradli się złodzieje i z każdej beczki ukradli część jej zawartości. Nie wiadomo ile było ryżu uprzednio. Wiadomo natomiast, że pozostało:
Gdy złodziei pochwycono, jeden z nich zeznał, że czerpał z pierwszej beczki czerpakiem, drugi z drugiej beczki - drewnianym chodakiem, trzeci zaś z trzeciej beczki - miseczką.
Przekonano się, że:
czerpak mieści 11 ho;
chodak mieści 17 ho;
miseczka mieści 13 ho.
Każda z beczek mieści najwyżej 300 ho.
Ile ryżu było w każdej z beczek?
Rozwiązanie:
Niech q będzie ilością ryżu w każdej z beczek.
Problem nasz możemy przeformułować w sposób następujący:
q º
1 (mod 11), co oznacza, że czerpano po 11 ho (czerpak) z I beczki;
q º
11 (mod 17), co oznacza, że czerpano po 17 ho (chodak) z II beczki;
q º
1 (mod 13), co oznacza, że czerpano po 13 ho (miseczka) z III beczki.
Z chińskiego twierdzenia o resztach wiemy, że istnieje rozwiązanie tego problemu.
Metody rozwiązania mogą być różne. Najprostsza, choć nie zawsze najszybsza, polega na wypisaniu kolejnych liczb przystających do 1 modulo 11, tzn. 1, 12, 23,... i podobnych ciągów dla drugiej i trzeciej równości. Następnie szukamy liczby, która pojawia się w trzech ciągach jednocześnie.
1, 12, 23, 34, 45, 56, 67, 78, 89, 100, 111, ..., 2278, 2289
11, 28, 45, 62, 79, 96, 113, 130, 147, 164, ..., 2272, 2289
1, 14, 27, 40, 53, 66, 79, 92, 105, 118, ..., 2276, 2289.
Liczba 2289 pojawia się we wszystkich trzech ciągach, a zatem w beczkach było 2289 ho ryżu.
Algorytm szyfrowania:
RSA - Ronald Rivest, Adi Shamir, Leonard Adleman.
Metoda polega na wybraniu trzech liczb:
Dla uproszczenia nasze n, e, d będą małe.
Przykład
n = 85 = 5 × 17; e = 5; d = 13
Chcemy zaszyfrować wiadomość, dla uproszczenia literę x = 24
(x jest 24 - tą literą alfabetu).
245 (mod 85) = 24 ×
24 ×
24 ×
24 ×
24 (mod 85) = 7962624 (mod 85) = 79 (mod 85)
Rozszyfrowanie (przy użyciu klucza d = 13):
7913 (mod 85) = 24 (mod 85).
Czyli otrzymaliśmy z powrotem naszą wiadomość x.
Sprawdźmy tę równość w łatwy sposób, mając do dyspozycji tylko zwykły kalkulator i pewną wiedzę z tego wykładu:
79 ×
79 = 6241 º
36 (mod 85),
79 ×
79 ×
79 ×
79 º
36 ×
36 º
21 (mod 85),
798 º
21 ×
21 º
16 (mod 85),
7912 º
21 ×
16 º
81 (mod 85),
7913 º
81 ×
79 º
24 (mod 85).
« poprzedni punkt |