alg23

Podstrony

[ Pobierz całość w formacie PDF ]
.��Wykład 3Arytmetyka modulo nNiech 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 a" b mod n.Relacja przystawania modulo n jest relacją równoważności.Rzeczywiścierelacja jest zwrotna bo dla każdej liczby całkowitej a, liczba 0 = a - a jestpodzielna przez n.Zatem a a" a mod n.Relacja ta jest również symetrycznabo jeśli n|(a - b) to również n|(b - a), bo b - a = -(a - b).Relacja jestprzechodnia, 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 a" b mod njeśli to a + c a" b + d mod n i a � c a" b � d mod n.Każdąc a" d mod nrelację równoważności, która spełnia powyższą własność nazywać będziemykongruencją 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 itylko wtedy gdy dają tę samą resztę przy dzieleniu przez n.A więc w tymprzypadku 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) + nZZamiast zapisu [a] będziemy zwykle używać zapisu a, a czasem będziemyopuszczać kreskę nad elementem.Przez Zn oznaczać będziemy zbiór klasabstrakcji relacji przystawania modulo n, a więc:Zn = {0, 1,., n - 1}1W zbiorze Zn można wprowadzić następujące działania: +n � = a + bb� � b = a � bnCzy działania te są dobrze określone? Czy może się zdarzyć taka sytuacja, żea = 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 = dto a a" c mod n, b a" d mod n, a stąd a + c a" b + d mod n, a � c a" b � d mod n,a więc a + c = b + d i a � c = b � dOczywiście spełniona jest następująca własność:� = b �!�! a a" b mod ni dwie klasy są albo równe albo są rozłączne.�Twierdzenie 1 Dla dowolnych klas , b, c " Zn mamy:��(i) + (� + c) = ( + b) + c,b � �� (ii) + b = b + ,� �(iii) + 0 = 0 + = ,�� (iv) + n - a = n - a + = 0,�(v) � (� � c) = ( � b) � c,b � �� (vi) � b = b � ,� �(vii) � 1 = 1 � = ,�(viii) � (� + c) = � b + � c,b � ��(ix) (� + c) � = b � + c � .b � �Przykład Skonstruować tabelki działań w pierścieniu Z5.+n 0 1 2 3 4 � 0 1 2 3 4n0 0 1 2 3 4 0 0 0 0 0 01 1 2 3 4 0 1 0 1 2 3 42 2 3 4 0 1 2 0 2 4 1 33 3 4 0 1 2 3 0 3 1 4 24 4 0 1 2 3 4 0 4 3 2 1Strukturę (Zn, +, �) nazywać będziemy pierścieniem reszt modulo n.Pytanie, które teraz się pojawia to: Kiedy równanie a � x = 1 ma rozwią-nzanie w pierścieniu Zn? Odpowiedzi można udzielić korzystając z wcześniej-szych rozważań dotyczących równań diofantycznych.Twierdzenie 2 Równanie a� x = 1 ma rozwiązanie w pierścieniu Zn wtedyni tylko wtedy gdy liczby a i n są względnie pierwsze.Inaczej mówiąc liczba ajest odwracalna modulo n wtedy i tylko wtedy gdy NWD(a, b) = 1.2Dowód Jeśli NWD(a, n) = 1 to istnieją liczby całkowite u, v takie, że au +nv = 1 wtedy modulo n mamy � v = 1, a więc liczba a jest odwracalna�modulo n.Jeśli teraz liczba a jest odwracalna modulo n to istnieje b, żea � b = 1 i a � b - 1 = 0 to oznacza, że n|(ab - 1), a więc istnieje k, żenab - 1 = kn, zatem równanie ax + ny = 1 ma rozwiązanie, a to oznacza, żeliczby a i n są względnie pierwsze.Zadanie Znalezć element odwrotny (jeśli istnieje) do 25 modulo 34.Bezpośrednią konsekwencją tego Twierdzenia jest następujące Twierdze-nie:Twierdzenie 3 Jeśli p > 0 jest liczbą pierwszą to w pierścieniu Zp każdyniezerowy elemnt jest odwracalny.Niezerowy element a pierścienia Zn nazywamy dzielnikiem zera jeśli ist-nieje niezerowy element b, taki że ab = 0 w Zn.Na przykład element 2 jestdzielnikiem zera w Z6 bo w Z6 mamy 2 � 3 = 0.Twierdzenie 4 Pierścień Zn posiada dzielniki zera wtedy i tylko wtedy gdyn nie jest liczbą pierwszą.Pierścień Zp gdzie p jest dodatnią liczbą pierwszą nazywamy ciałemreszt modulo p.Twierdzenie 5 Jeśli a, b są liczbami odwracalnymi modulo n to ich iloczynteż jest odwracalny modulo n.Dowód Istnieją liczby a i b takie, że modulo n mamy a � a = 1 i b � b = 1wtedy liczba b � a jest odwrotna do ab modulo n.3 [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

bezglutenowo.pev.pl