Movatterモバイル変換

[0]ホーム
URL:

Przejdź do zawartości
Wikipediawolna encyklopedia
Szukaj

Arytmetyka modularna

Z Wikipedii, wolnej encyklopedii
Ten artykuł dotyczy systemu liczbowego w matematyce. Zobacz też:sposoby realizacji w informatyce.

Arytmetyka modularna,arytmetyka reszt – systemliczb całkowitych, w którym liczby „zawijają się” po osiągnięciu pewnej wartości nazywanej modułem, często określanej terminemmodulo (skracanemod). Pierwszy pełny wykład arytmetyki reszt przedstawiłCarl Friedrich Gauss wDisquisitiones Arithmeticae („Badania arytmetyczne”,1801).

Arytmetyka modularna pojawia się wszędzie tam, gdzie występuje powtarzalność i cykliczność; dotyczy ona samegomierzeniaczasu i jako taka jest podstawą działaniakalendarza (zob.dalej). Ponadto korzysta się z niej wteorii liczb,teorii grup,kryptografii,informatyce, przy tworzeniusum kontrolnych, a nawet przy tworzeniu ornamentów[1]. Zasada działania szyfruRSA orazTest Millera-Rabina opierają się na własnościach mnożenia w arytmetyce modularnej liczb całkowitych.

Motywacja

[edytuj |edytuj kod]
 Zobacz też:zegar.
Wskazaniazegara 12-godzinnego jako przykład zastosowania arytmetyki modularnej.

Przykładem może być zegar 24-godzinny, w którymdoba podzielona jest na 24 godziny numerowane od 0 do 23. Każdej z nich można jednoznacznie przyporządkować okres w ciągu doby, który minął od godziny 0:00 do tej właśnie godziny – np. godzinie 7:00 można przyporządkować okres 7 godzin – można sobie wyobrażać, że w pewnym momencie ustawiono wskazówkę na 7 godzinie. W ten sposób jeśli zegar wskazuje godzinę 20:00, to znaczy, że od godziny 0:00 minęło 20 godzin; podobnie jeśli zegar wskazuje godzinę 8:00, to oznacza, że godzina 0:00 była dokładnie 8 godzin temu.

Jeżeli weźmie się jednak pod uwagę okresy dłuższe niż jedna doba, to wspomniane przyporządkowanie nie jest jedynym możliwym: jeśli teraz jest godzina 0:00, to godzinę 4:00 zegar będzie wskazywać tak po 4 godzinach, jak i po 28 godzinach – ogólnie będzie on wskazywał tę samą godzinę po upływie dowolnej liczby pełnych dób (wielokrotności 24 godzin), czyli: wskazania zegara 24-godzinnego powtarzają się co 24 godziny.

Obserwacje dotyczące wskazań zegara po dwóch okresach umożliwiają określenie wskazania zegara po upływie czasu równego sumie długości tych okresów: jeżeli zegar wskazywał godzinę 0:00 i upłynęło 19 godzin (wskazuje więc on godzinę 19:00), a następnie kolejne 8 godzin (zegar nastawiony na 0:00 wskazywałby po tym czasie godzinę 8:00), to zegar nie będzie wskazywał godziny „27:00”, lecz godzinę 3:00 – tak, jak gdyby od 0:00 minęły tylko 3 godziny.

Można więc wprowadzić następującedodawanie wskazań zegara: sumą dwóch godzin jest godzina, którą wskazywałby zegar po upływie okresu od 0:00 do pierwszej z godzin powiększonego o okres, który upłynąłby od 0:00 do drugiej z godzin. Oznacza to, że jeżeli okres jest niemniejszy niż 24 godziny, to zegar wskazywać będzie godzinę równą temu okresowi pomniejszonemu o okres 24 godzin. W ten sposób sumą godzin 12:00 i 21:00 jest godzina 9:00 (a nie 33:00). Cofaniu zegara odpowiadałyby „ujemne” okresy, tym zaś „ujemne” wskazania zegara: okresowi −7 godzin (7 godzin wstecz) odpowiada wskazanie zegara sprzed 7 godzin, gdy wskazuje on w tym momencie godzinę 0:00 – na zegarze 24-godzinnym jest to godzina 17:00. Dlatego też różnicą godzin 3:00 i 4:00 jest godzina 23:00 (a nie −1:00).

Upływ czasu liczy się więc zgodnie z arytmetyką liczb całkowitych, z kolei wskazania zegara są zgodne zarytmetyką modularną o module 24: mierzenie czasu na zegarze rozpoczyna się o godzinie 0:00 „zerując się” po osiągnięciu 24:00, z kolei gdy wskazówka zegara cofa się mijając godzinę 0:00, zegar wskazuje godzinę wcześniejszą niż 24:00.

W ten sam sposób można rozpatrywać obliczenia na dniachtygodnia (wykonywane modulo 7) lub namiesiącach (modulo 12). Prawa działań na liczbach takie jakliczba nieparzysta +liczba parzysta =liczba nieparzysta (zob.parzystość liczb) dają się opisać za pomocą arytmetyki modulo 2.

Wprowadzenie

[edytuj |edytuj kod]
 Zobacz też:działanie algebraiczne.

Zgodnie z powyższą intuicją można wprowadzić w zbiorze{0,1,…,n−1}{\displaystyle \{0,1,\dots ,n-1\}} uproszczony model arytmetyki modulon{\displaystyle n} definiując działania:

W ten sposób uzyskuje się również naturalnie określone działanie

Jak zauważono wyżej dodanie wielokrotnościn{\displaystyle n} nie zmienia wyniku działania dodawania (odejmowania) modularnego:

(a+kn)⊕nb=a⊕n(b+kn)=a⊕nb{\displaystyle (a+kn)\oplus _{n}b=a\oplus _{n}(b+kn)=a\oplus _{n}b}

dla dowolnych liczb całkowitycha,b,k.{\displaystyle a,b,k.}

Przykład
Działania te zgodne są z intuicyjnym rozumieniem arytmetyki pomiaru czasu na zegarze 24-godzinnym: dlan=24{\displaystyle n=24} zachodzą równości

Dalej zamiasta⊕nb{\displaystyle a\oplus _{n}b} stosowane będzie oznaczenie[a+b]n,{\displaystyle [a+b]_{n},} z kolei⊖nc{\displaystyle \ominus _{n}c} będzie oznaczane[−c]n,{\displaystyle [-c]_{n},} gdzie działania dodawania i odejmowania w nawiasach kwadratowych są zwykłymi działaniami arytmetycznymi liczb całkowitych, zaś symbol[ ]n{\displaystyle [\ ]_{n}} oznaczać będzie dodanie bądź odjęcie wielokrotności liczbyn{\displaystyle n} tak, by zawartość nawiasu należała do zbioru{0,…,n−1}.{\displaystyle \{0,\dots ,n-1\}.} Innymi słowy operacja[c]n{\displaystyle [c]_{n}} oznacza wzięciereszty z dzielenia liczbyc{\displaystyle c} przezn.{\displaystyle n.}

Przystawanie

[edytuj |edytuj kod]
 Zobacz też:przystawanie.

Relację≡n{\displaystyle \equiv _{n}} utożsamiającą ze sobą liczby o tej samejreszcie z dzielenia przezn,{\displaystyle n,} tzn. relację daną wzorem

a≡nb{\displaystyle a\equiv _{n}b} wtedy i tylko wtedy, gdy[a]n=[b]n,{\displaystyle [a]_{n}=[b]_{n},}

nazywa sięprzystawaniem bądźkongruencją o module (modulo)n.{\displaystyle n.} Jeśli liczbya{\displaystyle a} ib{\displaystyle b} dają tę samą resztę z dzielenia przezn,{\displaystyle n,} to ichróżnicaa−b{\displaystyle a-b} jestwielokrotnością liczbyn{\displaystyle n} lub równoważnien{\displaystyle n} jestdzielnikiema−b.{\displaystyle a-b.} Wspomniane dwa sformułowania są często przyjmowanymi definicjami przystawania[2]. Innym sposobem zapisu relacjia≡nb{\displaystyle a\equiv _{n}b} jesta=b (mod n),{\displaystyle a=b\ ({\bmod {\ }}n),} a naweta=b (n).{\displaystyle a=b\ (n).} Jeśli nie będzie prowadzić to do nieporozumień, w dalszej części artykułu indeksn{\displaystyle n} przy symbolach[ ]n{\displaystyle [\ ]_{n}} oraz≡n{\displaystyle \equiv _{n}} będzie pomijany.

W ten sposób ostatni wzór z powyższej sekcji można zapisać następująco:

[a+b+kn]=[a+b],{\displaystyle [a+b+kn]=[a+b],}

a więc

a+b+kn≡a+b{\displaystyle a+b+kn\equiv a+b}

dla dowolnej liczby całkowitejk.{\displaystyle k.} Wzór ten oznacza więc także, że przystawanie utożsamia ze sobą liczby różniące się owielokrotność ustalonej liczbyn,{\displaystyle n,} tzn. dla każdej liczby całkowitejc{\displaystyle c} zachodzi

c+kn≡c,{\displaystyle c+kn\equiv c,}

gdziek{\displaystyle k} jest dowolną liczbą całkowitą.

Przykład
Jeślin=24,{\displaystyle n=24,} to
57≡9,{\displaystyle 57\equiv 9,}
gdyż resztą z dzielenia 57 przez 24 oraz 9 przez 24 jest liczba 9; równoważnie
[57]=[9],{\displaystyle [57]=[9],}
ponieważ57−9=48=2⋅24{\displaystyle 57-9=48=2\cdot 24} jest podzielne przez24.{\displaystyle 24.}

W liczbach całkowitych oprócz działaniadodawania i branialiczby przeciwnej (odejmowania) wyróżnione jest działaniemnożenia (w liczbach całkowitychdzielenie jest nieokreślone – w ogólności iloraz liczby całkowitej i niezerowej liczby całkowitej nie zawsze jest liczbą całkowitą, zob.wewnętrzne działanie dwuargumentowe). Oprócz działania dodawania[a+b]{\displaystyle [a+b]} ma więc sens rozważanie działanie mnożenia[a⋅b],{\displaystyle [a\cdot b],} można więc przyjąć

[a⋅b+kn]=[a⋅b],{\displaystyle [a\cdot b+kn]=[a\cdot b],}

czyli

a⋅b+kn≡a⋅b.{\displaystyle a\cdot b+kn\equiv a\cdot b.}

Skoro przystawanie utożsamia liczby różniące się o pewną wielokrotność modułun{\displaystyle n} (tzn. zegar wskazuje tę samą godzinę po upływie wielokrotności 24 godzin), to można wymagać, by wynik dodawania, czy mnożenia nie zależał od wielokrotności modułu, a jedynie od reszty z dzielenia (by wynik działań na wskazaniach zegara nie zależał od czasu, który upłynął, by zegar osiągnął wskazania będące argumentami). Innymi słowy, jeśli zachodzą przystawania

a≡b{\displaystyle a\equiv b} ic≡d,{\displaystyle c\equiv d,}

to

a+c≡b+d{\displaystyle a+c\equiv b+d}

oraz

ac≡bd.{\displaystyle ac\equiv bd.}

Dlaa≡b{\displaystyle a\equiv b} i dowolnej liczby całkowitejc{\displaystyle c} zachodzą ponadto wzory

a±c≡b±c,{\displaystyle a\pm c\equiv b\pm c,}

gdyżn{\displaystyle n} dzielia−b=(a+c)−(b+c)=(a−c)−(b−c){\displaystyle a-b=(a+c)-(b+c)=(a-c)-(b-c)} oraz

ac≡bc,{\displaystyle ac\equiv bc,}

ponieważ skoron{\displaystyle n} dzielia−b,{\displaystyle a-b,} to dzieli takżec(a−b)=ac−bc.{\displaystyle c(a-b)=ac-bc.}

Powyższe wzory oznaczają więc, że kongruencje o tym samym module można dodawać, odejmować i mnożyć stronami oraz przenosić wyrazy z jednej strony kongruencji na drugą zmieniając przy tym ich znaki. Można również podnieść obie strony kongruencji do tej samejpotęgi (o naturalnym wykładniku). Niepoprawne jest jednak dzielenie kongruencji stronami, ani skracanie wspólnego dla obu stron dzielnika. Jeśliad≡bd,{\displaystyle ad\equiv bd,} ton{\displaystyle n} dzieliad−bd=d(a−b).{\displaystyle ad-bd=d(a-b).} Jeżelin{\displaystyle n} id{\displaystyle d} sąwzględnie pierwsze, ton{\displaystyle n} musi dzielića−b,{\displaystyle a-b,} a więca≡b.{\displaystyle a\equiv b.} Zatem dzielenie obu stron przez wspólny dzielnik jest poprawne jedynie wtedy, gdy jest on względnie pierwszy z modułem.

Pierścień klas reszt

[edytuj |edytuj kod]

Klasy reszt

[edytuj |edytuj kod]
 Zobacz też:relacja równoważności.

Niecha,b,c{\displaystyle a,b,c} będą dowolnymi liczbami całkowitymi. Kongruencja modulon{\displaystyle n} jest relacją równoważności, tzn. jest

Jak każda relacja równoważności, przystawanie wprowadzaPodział zbioru (w tym wypadku liczb całkowitych) napodzbiory nazywaneklasami reszt lubklasami kongruencji, które zawierają liczby dające tę samą resztę z dzielenia przez moduł i różniące się przy tym o jego wielokrotność; klas jest tyle, ile wynosi moduł przystawania. W dalszym ciągu podzbiory te będą oznaczane symbolem[i],{\displaystyle [i],} gdziei{\displaystyle i} jest dowolną liczbą należącą do tego zbioru nazywanąreprezentantem tej klasy (zwykle jest nią najmniejsza nieujemna liczba z tego zbioru). Z własności relacji równoważności każda liczba całkowita należy do dokładnie jednej klasy reszt.

Działania

[edytuj |edytuj kod]
 Zobacz też:pierścień.

Dwie klasy reszt dodaje się wybierając z każdej z nich po jednym reprezentancie, odpowiedniox{\displaystyle x} orazy;{\displaystyle y;} wynikiem jest klasa reszt, do której należyx+y.{\displaystyle x+y.} Okazuje się, że wynik takiego dodawanianie zależy od wyboru reprezentantówx{\displaystyle x} iy.{\displaystyle y.}

Przykład
Jeślin=4,{\displaystyle n=4,} to klasy reszt są zbiorami:
[0]:={…,−4,0,4,8,12,…},{\displaystyle [0]:=\{\dots ,-4,0,4,8,12,\dots \},}
[1]:={…,−3,1,5,9,13,…},{\displaystyle [1]:=\{\dots ,-3,1,5,9,13,\dots \},}
[2]:={…,−2,2,6,10,14,…},{\displaystyle [2]:=\{\dots ,-2,2,6,10,14,\dots \},}
[3]:={…,−1,3,7,11,15,…}.{\displaystyle [3]:=\{\dots ,-1,3,7,11,15,\dots \}.}
Chcąc dodać[2]{\displaystyle [2]} do[3]{\displaystyle [3]} wystarczy wybrać po jednym elemencie z każdej z nich, np.2{\displaystyle 2} i7{\displaystyle 7} – wynikiem jest klasa zawierająca2+7=9,{\displaystyle 2+7=9,} tzn. klasa[9]=[1].{\displaystyle [9]=[1].} Jeżeli wybrać przy dodawaniu10{\displaystyle 10} i3,{\displaystyle 3,} to wynik byłby taki sam: ta sama klasa reszt zawiera liczbę13.{\displaystyle 13.}

W taki sam sposób można zdefiniować mnożenie, które również jest określone jednoznacznie.

Przedstawione wyżej działania na klasach reszt mają regularne własności:

Struktura o tych własnościach nazywana jestpierścieniem przemiennymz jedynką.

Definicja

[edytuj |edytuj kod]
 Zobacz też:pierścień ilorazowy.

Niech≡{\displaystyle \equiv } będzie relacją przystawania modulon,{\displaystyle n,} gdzien{\displaystyle n} jest dowolną nieujemną liczbą całkowitą. Niech[a]{\displaystyle [a]} oznaczaklasę abstrakcji odpowiadającą liczbiea.{\displaystyle a.} Wzbiorze ilorazowymZ/≡{\displaystyle \mathbb {Z} /\equiv } wprowadza się działania dodawania i mnożenia klas reszt (dziedziczone zpierścienia liczb całkowitych) wzorami

[a]⊕[b]=[a+b],{\displaystyle [a]\oplus [b]=[a+b],}
[a]⊙[b]=[a⋅b].{\displaystyle [a]\odot [b]=[a\cdot b].}

ZbiórZ/≡{\displaystyle \mathbb {Z} /\equiv } wraz z działaniami⊕{\displaystyle \oplus } i⊙{\displaystyle \odot } nazywa siępierścieniem klas reszt modulon{\displaystyle n} i oznacza symbolamiZn{\displaystyle \mathbb {Z} _{n}} lubZ(n),{\displaystyle \mathbb {Z} (n),} przy czym symbole⊕{\displaystyle \oplus } i⊙{\displaystyle \odot } zastępuje się zwykle zwyczajowymi+{\displaystyle +} oraz⋅,{\displaystyle \cdot ,} co zostanie uczynione w dalszej części artykułu. Ponadto podając elementy pierścieniaZn{\displaystyle \mathbb {Z} _{n}} opuszcza się niekiedy nawiasy i wybiera najmniejszego nieujemnego reprezentanta, tj. liczbę ze zbioru{0,1,…,n−1},{\displaystyle \{0,1,\dots ,n-1\},} którą można znaleźć biorąc resztę z dzielenia dowolnego reprezentanta przezn.{\displaystyle n.} Innymi słowy utożsamia się w naturalny sposób elementy pierścieniaZn{\displaystyle \mathbb {Z} _{n}} z odpowiadającymi im elementami pierścieniaZ.{\displaystyle \mathbb {Z} .}

Na mocytwierdzenia o homomorfizmie dla pierścieni operator[ ]n{\displaystyle [\ ]_{n}} brania klas reszt modulon{\displaystyle n} jesthomomorfizmem pierścieniaZ{\displaystyle \mathbb {Z} } w pierścieńZn,{\displaystyle \mathbb {Z} _{n},} który przypisuje liczbie całkowitej jej resztę z dzielenia przezn.{\displaystyle n.}Jądrem tego homomorfizmu jestideałnZ,{\displaystyle n\mathbb {Z} ,} czyli wszystkie liczby podzielne przezn,{\displaystyle n,} zaśobrazem są liczby ze zbioru{0,…,n−1}.{\displaystyle \{0,\dots ,n-1\}.} To samo twierdzenie o homomorfizmie zapewnia, że ilorazZ{\displaystyle \mathbb {Z} } przeznZ{\displaystyle n\mathbb {Z} } jestizomorficzny z wyżej zdefiniowanym pierścieniem klas reszt modulon.{\displaystyle n.} Stąd też pochodzi alternatywne oznaczenieZ/nZ{\displaystyle \mathbb {Z} /n\mathbb {Z} } tego pierścienia; ponieważ ideałnZ{\displaystyle n\mathbb {Z} } oznacza się również symbolem(n),{\displaystyle (n),} to spotyka się również oznaczenieZ/(n).{\displaystyle \mathbb {Z} /(n).} W ten sposób konstrukcje dzielenia pierścienia liczb całkowitych przez relację przystawania modulon{\displaystyle n} i dzielenia go przez ideałnZ{\displaystyle n\mathbb {Z} } są równoważne z punktu widzenia algebry.

PierścieńZ0{\displaystyle \mathbb {Z} _{0}} jest izomorficzny z pierścieniemZ,{\displaystyle \mathbb {Z} ,} przypadek ten omawia się szerzej w artykule dotyczącymliczb całkowitych.

Własności

[edytuj |edytuj kod]

Elementem neutralnym dodawania wZn{\displaystyle \mathbb {Z} _{n}} jest[0],{\displaystyle [0],}elementem przeciwnym do[k]{\displaystyle [k]} jest[−k]=[n−k],{\displaystyle [-k]=[n-k],} elementem neutralnym mnożenia jest[1].{\displaystyle [1].}

Element[k]{\displaystyle [k]} pierścieniaZn{\displaystyle \mathbb {Z} _{n}} jestodwracalny wtedy i tylko wtedy, gdy liczba całkowitak{\displaystyle k} jestwzględnie pierwsza zn.{\displaystyle n.} Wynika to z faktu, iż można dobrać takie liczby całkowitea,b,{\displaystyle a,b,} dla których zachodzian+bk=1;{\displaystyle an+bk=1;} wtedybk≡1,{\displaystyle bk\equiv 1,} czyli[b][k]=1,{\displaystyle [b][k]=1,} co oznacza, iż[k]{\displaystyle [k]} ma odwrotność[b].{\displaystyle [b].} Jeżelin{\displaystyle n} ik{\displaystyle k} mają wspólny dzielnika>1,{\displaystyle a>1,} tj.n=ab,{\displaystyle n=ab,} ik=ac,{\displaystyle k=ac,} to[k][b]=[ac][b]=[abc]=0,{\displaystyle [k][b]=[ac][b]=[abc]=0,} co oznacza, że[k]{\displaystyle [k]} jestdzielnikiem zera.

Wynika stąd, że jeżelin{\displaystyle n} jestliczbą pierwszą, to w pierścieniuZn{\displaystyle \mathbb {Z} _{n}} jedynym dzielnikiem zera jest[0].{\displaystyle [0].} W przeciwnym wypadku istnieją nietrywialne dzielniki zera. Dlatego pierścieńZn{\displaystyle \mathbb {Z} _{n}} jestciałem wtedy i tylko wtedy, gdyn{\displaystyle n} jest liczbą pierwszą.

Charakterystyka pierścieniaZn{\displaystyle \mathbb {Z} _{n}} jest równan.{\displaystyle n.} Każdągrupę abelową oskończonej liczbie generatorów można przedstawić jakosumę prostą grupZn{\displaystyle \mathbb {Z} _{n}} (zob.twierdzenie).

Grupa addytywna

[edytuj |edytuj kod]
 Osobny artykuł:grupa addytywna.

Grupa addytywna pierścienia(Zn,+,⋅),{\displaystyle (\mathbb {Z} _{n},+,\cdot ),} tj.(Zn,+){\displaystyle (\mathbb {Z} _{n},+)} jestgrupącykliczną zwanąaddytywną grupą klas reszt modulon.{\displaystyle n.} Wteorii grup oznacza się ją symbolamiZn{\displaystyle \mathbb {Z} _{n}} lubZ/nZ.{\displaystyle \mathbb {Z} /n\mathbb {Z} .}

Generatorem tej grupy jest dowolna liczba względnie pierwsza zn.{\displaystyle n.} Co więcej, z dokładnością doizomorfizmu, jedynymi grupami cyklicznymi są(Zn,+){\displaystyle (\mathbb {Z} _{n},+)} i grupa addytywna liczb całkowitych.

Prawdziwa jest też równość dotyczącarzędu elementu:

o⁡(g)=nnwd⁡(g,n),{\displaystyle \operatorname {o} (g)={\tfrac {n}{\operatorname {nwd} (g,n)}},}

gdzienwd{\displaystyle \operatorname {nwd} } oznaczanajwiększy wspólny dzielnik.

Grupa multiplikatywna

[edytuj |edytuj kod]
 Osobny artykuł:grupa multiplikatywna.

Elementami odwracalnymi pierścieniaZn{\displaystyle \mathbb {Z} _{n}} są te liczby ze zbioru{0,1,…,n−1},{\displaystyle \{0,1,\dots ,n-1\},} które są względnie pierwsze zn:{\displaystyle n{:}}

Zn∗={[a]:nwd⁡(a,n)=1}.{\displaystyle \mathbb {Z} _{n}^{*}={\big \{}[a]\colon \operatorname {nwd} (a,n)=1{\big \}}.}

Ich liczbę wyznaczafunkcja φ Eulera. W szczególności,φ(n)=n−1⇔n∈P⇔Zn{\displaystyle \varphi (n)=n-1\Leftrightarrow n\in \mathbb {P} \Leftrightarrow \mathbb {Z} _{n}} jest ciałem.

Te elementy tworzą grupę, zwanąmultiplikatywną grupą klas reszt modulon.{\displaystyle n.} Oznaczana jestZn∗,{\displaystyle \mathbb {Z} _{n}^{*},}U(Zn){\displaystyle U(\mathbb {Z} _{n})} lub(Z/nZ)∗.{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}.}

Elementa{\displaystyle a} jestgeneratorem grupyZn∗{\displaystyle \mathbb {Z} _{n}^{*}} wtedy i tylko wtedy, gdy liczbaa{\displaystyle a} jestpierwiastkiem pierwotnym liczbyn.{\displaystyle n.} GrupaZn∗{\displaystyle \mathbb {Z} _{n}^{*}} jest zatem cykliczna wtedy i tylko wtedy, gdy liczban{\displaystyle n} posiada pierwiastek pierwotny, a to zachodzi dokładnie wtedy, gdyn=2,4,{\displaystyle n=2,4,} gdyn{\displaystyle n} jestpotęgą nieparzystej liczby pierwszej (to znaczy postacipα,{\displaystyle p^{\alpha },}p{\displaystyle p}-nieparzysta liczba pierwsza) lub podwojoną potęgą nieparzystej liczby pierwszej (to znaczy postaci2pα,{\displaystyle 2p^{\alpha },}p{\displaystyle p}-nieparzysta liczba pierwsza)[3]. Tak więc grupaZn∗{\displaystyle \mathbb {Z} _{n}^{*}} jest cykliczna dlan=2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,31{\displaystyle n=2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,31} itd.

Pierwiastki kwadratowe z jedności

[edytuj |edytuj kod]
 Zobacz też:pierwiastek z jedynki.

Pierwiastkiem kwadratowym z jedności modulon{\displaystyle n} nazywa się taki elementk∈Zn,{\displaystyle k\in \mathbb {Z} _{n},} dla którego zachodzi

k2=1.{\displaystyle k^{2}=1.}

W dowolnym pierścieniuZn{\displaystyle \mathbb {Z} _{n}} pierwiastkami z jedności są1{\displaystyle 1} i−1.{\displaystyle -1.} Można udowodnić, że liczba wszystkich pierwiastków kwadratowych modulon{\displaystyle n} wynosi[4]:

2f(n)+[8|n]−[2|n]+[4|n].{\displaystyle 2^{f(n)+[8|n]-[2|n]+[4|n]}.}

gdzie:

Aby sprawdzić, czy równaniea2=x{\displaystyle a^{2}=x} ma rozwiązanie, można skorzystać z własnościsymbolu Jacobiego.

Przykład
W pierścieniuZ60{\displaystyle \mathbb {Z} _{60}} jest23+0−1+1=23=8{\displaystyle 2^{3+0-1+1}=2^{3}=8}pierwiastków z jedynki:

Zobacz też

[edytuj |edytuj kod]

Przypisy

[edytuj |edytuj kod]
  1. ↑JillJ. Britton JillJ.,Modular Art, britton.disted.camosun.bc.ca, 2005 [zarchiwizowane 2006-01-01] .
  2. ↑kongruencja, [w:]Encyklopedia PWN [online],Wydawnictwo Naukowe PWN [dostęp 2021-07-21] .
  3. ↑Wacław Sierpiński,Teoria Liczb, Monografie Matematyczne 19, rozdział VIII.
  4. ↑Graham, Knuth i Patashnik 2006 ↓, s. 154.

Bibliografia

[edytuj |edytuj kod]

Linki zewnętrzne

[edytuj |edytuj kod]
Działyarytmetyki
główne
powiązanenauki
Teoria liczb
ogólne typyliczb
relacje
podzielność
zdefiniowane podzielnością
działania
liczby pierwsze
podstawy
testy pierwszości
sita
faktoryzacja
hipotezy
równania
diofantyczne
liniowe
kwadratowe
wyższych stopni
układy równań
powiązane zagadnienia
twierdzenia
arytmetyki modularnej
inne zagadnienia
twierdzenia limitacyjne
Teoria grup
podstawy
przykłady
zdodawaniem
zmnożeniem
liczb
zeskładaniem
funkcji
inne
homomorfizmy
podgrupy
ogólne
normalne
charakterystyczne
dalsze pojęcia
rodzaje grup
przemienne
inne
twierdzenia
o grupach
skończonych
dowolnych
grupy
z dodatkowymi
strukturami
uogólnienia
uczeni według
daty narodzin
XVIII wiek
XIX wiek
XX wiek

Encyklopedie internetowe (dziedzina matematyki):
Źródło: „https://pl.wikipedia.org/w/index.php?title=Arytmetyka_modularna&oldid=74823519”
Kategorie:
[8]ページ先頭
©2009-2025 Movatter.jp