Wykład 4
Określimy teraz pewną ważną klasę pierścieni.
Twierdzenie 1 Niech m, n ∈ Z. Jeśli n 0 to istnieje dokładnie jedna para
licz q, r, że:
m = qn + r, 0 r 0, wtedy w zbiorze Zn
możemy określić działania +n , ·n w następujący sposób:
a +n b = (a + b)n
a ·n b = (a · b)n
a więc sumę i iloczyn w Zn określamy jako resztę z dzielenia zwykłej sumy i
zwykłego iloczynu przez n. Określmy następującą funkcję:
fn : Z → Zn
fn (x) = reszta z dzielenia liczby x przez n. Wtedy funkcja fn ma własności:
fn (x + y) = fn (x) +n fn (y)
fn (x · y) = fn (x) ·n fn (y)
Niech r, s oznaczają reszty z dzielenia x i y przez n wtedy mamy x = an +
r, y = bn + s. Stąd x + y = (a + b)n + r + s i fn (x + y) = fn (r + s) i fn (x) = r
oraz fn (y) = s. Ponieważ 0
r, s
(…)
… resztę przez następną resztę.
Można zauważyć, że
NWD(a, b) = NWD(b, r0 ) = NWD(r0 , r1 ) = NWD(r1 , r2 ) = . . .
i ponieważ ciąg reszt jest ściśle malejącym ciągiem liczb całkowitych nieujemnych to po skończonej ilości kroków musimy otrzymać resztę równą zero.
Zgodnie z wcześniejszym stwierdzeniem największym wspólnym dzielnikiem
liczb a i b będzie ostatnia niezerowa reszta w tym procesie. Opisany algorytm
znajdowania największego wspólnego dzielnika nosi nazwę Algorytmu Euklidesa. Pokażemy teraz na przykładzie działanie tego algorytmu.
Zadanie Wyznaczyć przy pomocy Algorytmu Euklidesa największy wspólny
3
dzielnik liczb 324 i 148. A więc wykonujemy kolejne dzielenia:
324 = 2 · 148 + 28
148 = 5 · 28 + 8
28 = 3 · 8 + 4
8=4·2+0
Ostatnią niezerową resztą jest 4. To oznacza, że NWD(324, 148) = 4…
… będą liczbami całkowitymi, z których przynajmniej jedna jest
różna od zera. Wtedy największym wspólnym dzielnikiem tych liczb
nazywamy największą liczbę całkowitą d, która dzieli jednocześnie a i b. Największy wspólny dzielnik oznaczamy przez NWD(a, b) i jest on wyznaczony
(w tym przypadku) jednoznacznie. Inaczej mówiąc d = NWD(a, b) wtedy i
tylko wtedy gdy
(i) d|a i d|b,
(ii) jeśli c|a i c|b to c d.
Z powyższej definicji widać, że NWD(a, b) 1.
Na przykład NWD(12, 30) = 6.
Opiszemy teraz algorytm, który pozwala w prosty sposób wyznaczać największy wspólny dzielnik dwóch liczb. Załóżmy, że a b. Oczywiście jeśli b|a
to NWD(a, b) = b i problemu nie ma. Przypuśćmy, że b a wtedy możemy a
podzielić przez b z niezerową resztą:
a = q0 b + r 0 ,
0 < r0 < b
Jeśli liczba c dzieli a i dzieli b to ta liczba…
… można wykorzystywać nie tylko do poszukiwania największego wspólnego dzielnika dwóch liczb, ale również do rozwiązywania równań typu
ax + by = NWD(a, b)
Wprost z powyższych rozumowań można wywnioskować następujące Twierdzenie:
Twierdzenie 3 Niech a, b będą dwiema liczbami całkowitymi z których przynajmniej jedna liczba jest różna od 0. Wtedy istnieją liczby całkowite u, v,
takie że
ua + vb = NWD(a, b)
Z powyższego…
… + s i fn (x + y) = fn (r + s) i fn (x) = r
oraz fn (y) = s. Ponieważ 0
r, s < n to zgodnie z definicją funkcji fn i
dodawania +n otrzymujemy żądaną równość.
Twierdzenie 2 System algebraiczny (Zn , +n , ·n ) jest pierścieniem przemiennym z jedynką.
1
Dowód Wszystkie własności pierścienia można sprawdzić korzystając z funkcji fn . Na przykład jeśli chcemy udowodnić łączność to weźmy dowolne elementy a, b, c ∈ Zn . Wtedy mamy:
a +n (b +n c) = fn (a + (b + c)) = fn ((a + b) + c) = (a +n b) +n c
Inne własności pokazuje się podobnie. Elementem neutralnym dodawania jest
0, mnożenia jest 1. Elementem przeciwnym do a ∈ Zn jest n − a.
Działania +n , ·n nazywa się zwykle dodawaniem i mnożeniem modulo n,
a pierścień (Zn , +n , ·n ) pierścieniem reszt modulo n. Można też zdefiniować
potęgowanie np. a2 w Zn…
... zobacz całą notatkę
Komentarze użytkowników (0)