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ówi- my, ż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ść: jeśli a ≡ b mod n c ≡ d mod n to a + c ≡ b + d mod n i a · c ≡ b · d mod n . Każdą 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 przysta- wania 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} = n Z [1] = {x ∈ Z : n| ( x − 1) } = 1 + n Z [2] = {x ∈ Z : n| ( x − 2) } = 2 + n Z .. . [ n − 1] = {x ∈ Z : n| ( x − ( n − 1)) } = ( n − 1) + n Z 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 ¯ b = a + b ¯ a ·n ¯ b = a · 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ść:
(…)
… 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)