Wykład 7
Kongruencje
7.1 Relacja przystawania modulo m
Definicja 7.1. Niech m " N. Wprowadzmy w zbiorze liczb całkowitych relację kongru-
encji (przystawania) liczb modulo m, oznaczaną symbolem a" (mod m) , następują-
co:
"a, b"Z a a" b (mod m) Ð!Ò! (a MOD m) = (b MOD m).
Twierdzenie 7.1. Relacja przystawania modulo m jest relacją równoważności. Klasy
abstrakcji tej relacji sÄ… reprezentowane jednoznacznie przez elementy zbioru Zm.
Twierdzenie 7.2. Niech m, n będą dowolnymi liczbami naturalnymi oraz a, b, c, d
dowolnymi liczbami całkowitymi. Wówczas
(a) Jeżeli a a" b (mod m) i c a" d (mod m), to a + c a" b + d (mod m) i ac a" bd
(mod m).
(b) Jeżeli a a" b (mod m) oraz d|m i d " N, to a a" b (mod d).
(c) Jeżeli a a" b (mod m), a a" b (mod n) i NWD(m, n) = 1, to a a" b (mod mn).
7.2 Kongruencje liniowe
Zadanie: Dla danych liczb całkowitych a, b oraz liczby naturalnej m znalezć wszystkie
liczby całkowite x, dla których zachodzi
ax a" b (mod m). (7.1)
Zadanie takie będziemy nazywać liniowym równaniem kongruencyjnym lub, krótko, kon-
gruencjÄ… liniowÄ….
22
Uwaga 7.1. Dla dowolnych liczb a, b " Z oznaczmy a0 = a MOD m i b0 = b MOD m.
Wówczas kongruencja
ax a" b (mod m)
ma taki sam zbiór rozwiązań, jak kongruencja
a0x a" b0 (mod m). (7.2)
Uwaga 7.2. Jeżeli a0 = 0 (czyli: a a" 0 (mod m)), to kongruencja (7.2) ma rozwiązanie
wtedy i tylko wtedy, gdy również b0 = 0 i wówczas rozwiązaniem jest każda liczba
całkowita.
Uwaga 7.3. Jeżeli m = 1, to rozwiązaniem kongruencji (7.2) jest każda liczba całkowita.
Uwaga 7.4. Poszukiwanie rozwiązania kongruencji (7.2) w zbiorze Zm jest równoważne
szukaniu rozwiÄ…zaÅ„ równania a0 · x = b0 w pierÅ›cieniu Zm.
m
Twierdzenie 7.3. Niech m " N i a " Z+ , b " Zm będą dowolnymi liczbami. Wówczas:
m
10. Jeżeli NWD(a, m) = 1, to istnieje dokładnie jedno rozwiązanie x0 " Zm kongruencji
(7.1). Każde inne rozwiązanie x tej kongruencji ma postać
x = x0 + km
dla pewnego k " Z.
20. Jeżeli NWD(a, m) = d > 1, to rozwiązanie kongruencji (7.1) istnieje wtedy i tylko
wtedy, gdy d|b. Jeżeli d|b, to kongruencja (7.1) jest równoważna kongruencji
a2 x a" b2 (mod m2 ), (7.3)
gdzie a2 = a/d, b2 = b/d oraz m2 = m/d.
7.3 Układy kongruencji
Twierdzenie 7.4 (Chińskie twierdzenie o resztach). Niech m1, m2, . . . , mk " N
bÄ™dÄ… liczbami parami wzglÄ™dnie pierwszymi i m = m1m2·. . .·mk. Wówczas dla dowolnych
liczb całkowitych a1, a2, . . . , ak układ kongruencji
Å„Å‚
ôÅ‚
ôÅ‚
ôÅ‚
x a" a1 (mod m1),
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
x a" a2 (mod m2),
(7.4)
ôÅ‚
ôÅ‚
ôÅ‚
· · · · · ·
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ół
x a" ak (mod mk)
ma dokładnie jedno rozwiązanie x0 " Zm. Każde inne rozwiązanie x układu (7.4) ma
postać x = x0 + lm dla pewnego l " Z.
23
Wyszukiwarka
Podobne podstrony:
Kryptografia wykladKryptografia WykladKryptografia wykladKryptografia Wykład z podstaw klasycznej kryptografii z elementami kryptografii kwantowej(1)Kryptologia Wyklad 1Kryptologia Wyklad 4Kryptologia Wyklad 3Kryptografia wykladKryptografia wykladKryptografia wykladKryptologia Wyklad 2Kryptologia Wyklad 7aKryptografia wykladKryptografia wykladKryptologia Wyklad 6Kryptografia wykladKryptografia wykladKryptologia Wyklad 5Wyklad (Kryptografia) Pdfwięcej podobnych podstron