To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Wykład 3
Arytmetyka modulo n
Niech n będzie dodatnią liczbą całkowitą (n 0) i niech a, b ∈ Z. Mówimy, że a przystaje do b modulo n jeśli n|(a−b) i piszemy wtedy a ≡ b mod n.
Relacja przystawania modulo n jest relacją równoważności. Rzeczywiście
relacja jest zwrotna bo dla każdej liczby całkowitej a, liczba 0 = a − a jest
podzielna przez n. Zatem a ≡ a mod n. Relacja ta jest również symetryczna
bo jeśli n|(a − b) to również n|(b − a), bo b − a = −(a − b). Relacja jest
przechodnia, bo jeśli n|(a − b) i n|(b − c) to również n dzieli (a − b) + (b − c) =
a − c, a więc n|(a − c).
Relacja przystawania modulo n ma jeszcze jedną bardzo ważną własność:
a ≡ b mod n
jeśli
to a + c ≡ b + d mod n i a · c ≡ b · d mod n. Każdą
c ≡ d mod n
relację równoważności, która spełnia powyższą własność nazywać będziemy
kongruencją w Z.
Oznaczmy przez [a] klasę abstrakcji elementu a względem relacji przystawania modulo n, a więc:
[a] = {b ∈ Z : n|(a − b)}
Można zauważyć, że klasa abstrakcji elementu a jest wyznaczona przez resztę
z dzielenia tego elementu przez n i że dwa elementy są w relacji wtedy i
tylko wtedy gdy dają tę samą resztę przy dzieleniu przez n. A więc w tym
przypadku mamy dokładnie n różnych klas abstrakcji:
[0] = {x ∈ Z : n|x} = nZ
[1] = {x ∈ Z : n|(x − 1)} = 1 + nZ
[2] = {x ∈ Z : n|(x − 2)} = 2 + nZ
.
.
.
[n − 1] = {x ∈ Z : n|(x − (n − 1))} = (n − 1) + nZ
Zamiast zapisu [a] będziemy zwykle używać zapisu a, a czasem będziemy
opuszczać kreskę nad elementem. Przez Zn oznaczać będziemy zbiór klas
abstrakcji relacji przystawania modulo n, a więc:
Zn = {0, 1, . . . , n − 1}
1
W zbiorze Zn można wprowadzić następujące działania:
a +n ¯ = a + b
¯
b
a ·n ¯ = a · b
¯ b
Czy działania te są dobrze określone? Czy może się zdarzyć taka sytuacja, że
a = c, b = d a a + c = b + d lub a · c = b · d? Otóż nie, a wynika to z faktu,
że relacja przystawania modulo n jest kongruencją. Jeśli mamy a = c, b = d
to a ≡ c mod n, b ≡ d mod n, a stąd a + c ≡ b + d mod n, a · c ≡ b · d mod n,
a więc a + c = b + d i a · c = b · d
Oczywiście spełniona jest następująca własność:
a = ¯ ⇐⇒ a ≡ b mod n
¯ b
i dwie klasy są albo równe albo są rozłączne.
Twierdzenie 1 Dla dowolnych klas a, ¯ c ∈ Zn mamy:
¯ b, ¯
(i) a + (¯ + c) = (¯ + ¯ + c,
¯
b ¯
a b) ¯
(ii) a + ¯ = ¯ + a,
¯ b b ¯
(iii) a + ¯ = ¯ + a = a,
¯ 0 0 ¯ ¯
¯
¯
(iv) a + n − a = n − a + a = ¯
¯
¯ 0,
¯ · c) = (¯ · ¯ · c,
(v) a · (b ¯
¯
a b) ¯
(vi) a · ¯ = ¯ · a,
¯ b b ¯
(vii) a · ¯ = ¯ · a = a,
¯ 1 1 ¯ ¯
(viii) a · (¯ + c) = a · ¯ + a · c,
¯ b ¯
¯ b ¯ ¯
(ix) (¯ + c) · a = ¯ · a + c · a.
b ¯ ¯ b ¯ ¯ ¯
Przykład Skonstruować tabelki działań w pierścieniu Z5 .
+n 0 1 2 3 4
·n 0 1 2 3 4
0 0 1 2 3 4
0 0 0 0 0 0
1 1 2 3 4 0
1 0 1 2 3 4
2 2 3 4 0 1
2 0 2 4 1 3
3 3 4 0 1 2
3 0 3 1 4 2
4 4 0 1 2 3
4 0 4 3 2 1
Strukturę (Zn , +, ·) nazywać będziemy pierścieniem reszt modulo n.
Pytanie, które teraz się pojawia to: Kiedy równanie a ·n x = 1 ma rozwiązanie w pierścieniu Zn ? Odpowiedzi można udzielić korzystając z wcześniejszych rozważań
(…)
… element odwrotny (jeśli istnieje) do 25 modulo 34.
Bezpośrednią konsekwencją tego Twierdzenia jest następujące Twierdzenie:
Twierdzenie 3 Jeśli p > 0 jest liczbą pierwszą to w pierścieniu Zp każdy
niezerowy elemnt jest odwracalny.
Niezerowy element a pierścienia Zn nazywamy dzielnikiem zera jeśli istnieje niezerowy element b, taki że ab = 0 w Zn . Na przykład element 2 jest
dzielnikiem zera w Z6 bo w Z6…
... zobacz całą notatkę
Komentarze użytkowników (0)