Wykład 5
Struktury algebraiczne
5.1 Działania modularne
Dla dowolnej liczby naturalnej m > 1 oznaczmy
Zm = {0, 1, . . . , m - 1},
Z+ = {1, . . . , m - 1},
m
ZĄ" = {n " Zm : nĄ"m}.
m
Zauważmy, że
ZÄ„" ‚" Z+ ‚" Zm.
m m
W zbiorze Zm wprowadzamy działania wewnętrzne dodawania modulo m +m i mno-
żenia modulo m · nastÄ™pujÄ…co: dla dowolnych a, b " Zm przyjmujemy
m
a +m b = (a + b) MOD m oraz a · b = (a · b) MOD m.
m
Wewnętrzność tak wprowadzonych działań jest oczywista.
Lemat 5.1. Niech m " N \ {1} i a, b " Z. Wtedy
(a) (a + b) MOD m = [(a MOD m) + (b MOD m)] MOD m,
(b) (a · b) MOD m = [(a MOD m) · (b MOD m)] MOD m.
Korzystając z definicji działań modulo m możemy zapisać równości występujące w
lemacie w poniższej postaci:
(a) (a + b) MOD m = (a MOD m) +m (b MOD m),
(b) (a · b) MOD m = (a MOD m) · (b MOD m).
m
Twierdzenie 5.1. Dla dowolnej liczby naturalnej m para (Zm, +m) jest grupÄ… abelowÄ….
15
Zauważmy, że:
" Działanie +m nie jest wewnętrzne w zbiorach Z+ i ZĄ" dla każdej liczby całkowitej
m m
m > 2.
" DziaÅ‚anie · nie jest wewnÄ™trzne w zbiorach Z+ , jeżeli m jest liczbÄ… zÅ‚ożonÄ….
m
m
" DziaÅ‚anie · jest wewnÄ™trzne w zbiorze ZÄ„" dla każdej liczby caÅ‚kowitej m > 1.
m
m
5.2 Element odwrotny względem mnożenia modulo
m
Definicja 5.1. Niech m > 1 będzie liczbą naturalną i a " Zm. Jeżeli istnieje taka liczba
b " Zm, że a· b = 1, to nazywamy jÄ… elementem odwrotnym do a modulo m i oznaczamy
m
symbolem a-1 mod m.
Twierdzenie 5.2. Niech m > 1 będzie liczbą naturalną i a " Z. Wówczas a posiada
element odwrotny modulo m wtedy i tylko wtedy, gdy NWD(a, m) = 1.
Twierdzenie 5.3. Dla dowolnej liczby naturalnej m > 2 para (ZÄ„" , · ) jest grupÄ… abe-
m
m
lowÄ….
Wniosek 5.1. Niech m > 2 bÄ™dzie liczbÄ… naturalnÄ…. Para (Z+ , · ) jest grupÄ… abelowÄ…
m
m
wtedy i tylko wtedy, gdy m jest liczbÄ… pierwszÄ….
Wniosek 5.2. Jeżeli p " P, to (Zp, +p, · ) jest ciaÅ‚em przemiennym.
p
16
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 wykladKryptografia wykladKryptologia Wyklad 2Kryptologia Wyklad 7aKryptografia wykladKryptografia wykladKryptologia Wyklad 6Kryptografia wykladKryptologia Wyklad 5Wyklad (Kryptografia) Pdfwięcej podobnych podstron