Multiplikativní skupina celých čísel modulo n - Multiplicative group of integers modulo n
v modulární aritmetika, celá čísla coprime (relativně prime) až n ze sady z n nezáporná celá čísla tvoří a skupina pod násobením modulo n, nazvaný multiplikativní skupina celých čísel modulo n. Rovněž lze prvky této skupiny považovat za třídy shody, také známý jako zbytky modulo n, které jsou coprime nJiný název je tedy skupina primitivní zbytkové třídy modulo n.V teorie prstenů, pobočka abstraktní algebra, je popisován jako skupina jednotek kruhu celých čísel modulo n. Tady Jednotky odkazuje na prvky s a multiplikativní inverzní, které v tomto kruhu jsou přesně ty coprime n.
Algebraická struktura → Skupinová teorie Skupinová teorie |
---|
![]() |
Nekonečná dimenzionální Lieova skupina
|
Tato skupina je obvykle označována , je zásadní v teorie čísel. Nalezlo aplikace v kryptografie, celočíselná faktorizace, a testování primality. Je to abelian, konečný skupina, jejíž pořadí je dáno Eulerova totientová funkce: Pro nejlepší n skupina je cyklický a obecně je struktura snadno popsatelná, i když i pro prime n žádný obecný vzorec pro hledání generátory je známo.
Skupinové axiomy
Jedná se o jednoduché cvičení, které ukazuje, že při násobení je množina třídy shody modulo n které jsou coprime n uspokojit axiomy pro abelianská skupina.
Vskutku, A je coprime n kdyby a jen kdyby gcd (A, n) = 1. Celá čísla ve stejné třídě shody A ≡ b (mod n) uspokojit gcd (A, n) = gcd (b, n), proto je jeden coprime n právě když je ten druhý. Tedy pojem kongruenčních tříd modulo n které jsou coprime n je dobře definovaný.
Od té doby gcd (A, n) = 1 a gcd (b, n) = 1 naznačuje gcd (ab, n) = 1, sada tříd coprime do n je uzavřen při násobení.
Násobení celého čísla respektuje třídy shody, tj. A ≡ A' a b ≡ b ' (mod n) naznačuje ab ≡ a'b ' (mod n)To znamená, že násobení je asociativní, komutativní a že třída 1 je jedinečná multiplikativní identita.
Nakonec zadáno A, multiplikativní inverzní z A modulo n je celé číslo X uspokojující sekera ≡ 1 (mod n)Existuje přesně tehdy A je coprime n, protože v tom případě gcd (A, n) = 1 a tím Bézoutovo lemma existují celá čísla X a y uspokojující sekera + ny = 1. Všimněte si, že rovnice sekera + ny = 1 to naznačuje X je coprime n, takže multiplikativní inverze patří do skupiny.
Zápis
Sada (tříd shody) celých čísel modulo n s operacemi sčítání a násobení je a prsten Je označen nebo (zápis se týká převzetí kvocient celých čísel modulo ideál nebo skládající se z násobků nMimo teorii čísel jednodušší notace je často používán, ačkoli to může být zaměňováno s p-adická celá čísla když n je prvočíslo.
Multiplikativní skupina celých čísel modulo n, který je skupina jednotek v tomto kruhu lze napsat jako (v závislosti na autorovi) (pro němčinu Einheit, což se překládá jako jednotka), nebo podobné notace. Tento článek používá
Zápis Odkazuje na cyklická skupina řádu n.To je izomorfní do skupiny celých čísel modulo n pod doplněním. Všimněte si toho nebo může také odkazovat na přidávanou skupinu. Například multiplikativní skupina pro nejlepšího p je cyklický, a tudíž isomorfní vůči skupině aditiv , ale izomorfismus není zřejmý.
Struktura
Pořadí multiplikativní skupiny celých čísel modulo n je počet celých čísel v coprime to nJe to dáno Eulerova totientová funkce: (sekvence A000010 v OEIS ) p, .
Cyklický případ
Skupina je cyklický kdyby a jen kdyby n je 1, 2, 4, pk nebo 2pk, kde p je liché prvočíslo a k > 0. Pro všechny ostatní hodnoty n skupina není cyklická.[1][2][3]To bylo poprvé prokázáno Gauss.[4]
To znamená, že pro tyto n:
- kde
Podle definice je skupina cyklická právě tehdy, má-li generátor G (A generující sada {G} velikosti jedna), tj. pravomoci dát všechny možné zbytky modulo n coprime to n (první pravomoci dát každému přesně jednou). Generátor se nazývá a primitivní root modulo n.[5]Pokud existuje nějaký generátor, pak existují z nich.
Pravomoci 2
Modulo 1 libovolná dvě celá čísla jsou shodná, tj. Existuje pouze jedna třída shody, [0], coprime k 1. Proto, je triviální skupina s φ (1) = 1 živel. Vzhledem ke své triviální povaze je případ kongruencí modulo 1 obecně ignorován a někteří autoři se rozhodnou případ nezahrnout n = 1 ve větách.
Modulo 2 existuje pouze jedna třída kongruence coprime, [1], takže je triviální skupina.
Modulo 4 existují dvě třídy shody coprime, [1] a [3], takže cyklická skupina se dvěma prvky.
Modulo 8 existují čtyři třídy shodnosti coprime, [1], [3], [5] a [7]. Čtverec každého z nich je 1, takže the Kleinova čtyřčlenná skupina.
Modulo 16 existuje osm tříd kongruence coprime [1], [3], [5], [7], [9], [11], [13] a [15]. je 2-torzní podskupina (tj. čtverec každého prvku je 1), takže není cyklický. Pravomoci 3, jsou podskupinou řádu 4, stejně jako mocniny 5, Tím pádem
Vzor zobrazený 8 a 16 drží[6] pro vyšší síly 2k, k > 2: je 2-torzní podskupina (tak není cyklický) a mocniny 3 jsou cyklickou podskupinou řádu 2k − 2, tak
Obecná složená čísla
Podle základní věta o konečných abelianských skupinách, skupina je izomorfní s a přímý produkt cyklických skupin hlavních objednávek energie.
Přesněji řečeno Čínská věta o zbytku[7] říká, že pokud pak prsten je přímý produkt prstenů odpovídajících každému z jeho hlavních výkonových faktorů:
Podobně skupina jednotek je přímým součinem skupin odpovídajících každému z hlavních činitelů výkonu:
Pro každou lichou primární sílu odpovídající faktor je cyklická skupina řádu , které se mohou dále rozdělovat do cyklických skupin příkazů prime-power. Pro mocniny 2 faktor není cyklický, pokud k = 0, 1, 2, ale rozdělí se do cyklických skupin, jak je popsáno výše.
Pořadí skupiny je produktem objednávek cyklických skupin v přímém produktu exponent skupiny, tj nejmenší společný násobek objednávek v cyklických skupinách je dáno Funkce Carmichael (sekvence A002322 v OEIS ).Jinými slovy, je nejmenší číslo pro každý A coprime to n, drží. rozděluje a rovná se jí právě tehdy, pokud je skupina cyklická.
Podskupina falešných svědků
Li n je složený, existuje podskupina multiplikativní skupiny zvaná „skupina falešných svědků“, ve které jsou prvky, když jsou pozvednuty k moci n − 1, jsou shodné s 1 modulo n (protože zbytek 1, na jakoukoli sílu, je shodný s 1 modulo n, sada takových prvků je neprázdná).[8] Dalo by se říci, kvůli Fermatova malá věta, že takové zbytky jsou „falešně pozitivní“ nebo „falešní svědci“ pro primitivitu n. Číslo 2 je tedy nejčastěji používaným zbytkem v této základní kontrole primality 341 = 11 × 31 je známý od 2340 je shodné s 1 modulo 341 a 341 je nejmenší takové složené číslo (s ohledem na 2). U 341 obsahuje podskupina falešných svědků 100 zbytků, takže má index 3 uvnitř modifikace 341 multiplikativní skupiny 300 prvků.
Příklady
n = 9
Nejmenší příklad s netriviální podskupinou falešných svědků je 9 = 3 × 3. Existuje 6 zbytků současně s 9: 1, 2, 4, 5, 7, 8. Protože 8 je shodné s −1 modulo 9, z toho vyplývá, že 88 je shodné s 1 modulo 9. Takže 1 a 8 jsou falešně pozitivní pro „primitivitu“ 9 (protože 9 není ve skutečnosti prvočíslo). Ve skutečnosti jsou jediní, takže podskupina {1,8} je podskupinou falešných svědků. Stejný argument to ukazuje n − 1 je „falešný svědek“ pro jakýkoli zvláštní složený výraz n.
n = 91
Pro n = 91 (= 7 × 13), existují zbytky společně na 91, polovina z nich (tj. 36 z nich) jsou falešní svědci 91, jmenovitě 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88 a 90, protože pro tyto hodnoty X, X90 je shodný s 1 módem 91.
n = 561
n = 561 (= 3 × 11 × 17) je a Carmichael číslo, tím pádem s560 je shodné s 1 modulo 561 pro jakékoli celé číslo s coprime na 561. Podskupina falešných svědků není v tomto případě správná; je to celá skupina multiplikativních jednotek modulo 561, která se skládá z 320 zbytků.
Příklady
Tato tabulka ukazuje cyklický rozklad a a generující sada pro n ≤ 128. Dekompoziční a generující množiny nejsou jedinečné; například, (ale ). Níže uvedená tabulka uvádí nejkratší rozklad (z nich je vybrán lexikograficky první - to zaručuje, že isomorfní skupiny jsou uvedeny se stejnými rozklady). Generovací sada je také zvolena tak, aby byla co nejkratší a pro n s primitivním kořenem, nejmenším primitivním kořenem modulo n je uveden.
Například vezměte . Pak znamená, že pořadí skupiny je 8 (tj. je zde 8 čísel menších než 20 a coprime); znamená pořadí každého prvku dělí 4, to znamená, že čtvrtá síla libovolného čísla coprime na 20 je shodná s 1 (mod 20). Sada {3,19} generuje skupinu, což znamená, že každý prvek z je ve formě 3A × 19b (kde A je 0, 1, 2 nebo 3, protože prvek 3 má řád 4 a podobně b je 0 nebo 1, protože prvek 19 má pořadí 2).
Nejmenší primitivní kořenový mod n jsou (0, pokud neexistuje root)
- 0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... (sekvence A046145 v OEIS )
Počet prvků v minimální generující sadě mod n jsou
- 0, 0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... (sekvence A046072 v OEIS )
Generátorová sada | Generátorová sada | Generátorová sada | Generátorová sada | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | C1 | 1 | 1 | 0 | 33 | C2× C.10 | 20 | 10 | 2, 10 | 65 | C4× C.12 | 48 | 12 | 2, 12 | 97 | C96 | 96 | 96 | 5 | |||
2 | C1 | 1 | 1 | 1 | 34 | C16 | 16 | 16 | 3 | 66 | C2× C.10 | 20 | 10 | 5, 7 | 98 | C42 | 42 | 42 | 3 | |||
3 | C2 | 2 | 2 | 2 | 35 | C2× C.12 | 24 | 12 | 2, 6 | 67 | C66 | 66 | 66 | 2 | 99 | C2× C.30 | 60 | 30 | 2, 5 | |||
4 | C2 | 2 | 2 | 3 | 36 | C2× C.6 | 12 | 6 | 5, 19 | 68 | C2× C.16 | 32 | 16 | 3, 67 | 100 | C2× C.20 | 40 | 20 | 3, 99 | |||
5 | C4 | 4 | 4 | 2 | 37 | C36 | 36 | 36 | 2 | 69 | C2× C.22 | 44 | 22 | 2, 68 | 101 | C100 | 100 | 100 | 2 | |||
6 | C2 | 2 | 2 | 5 | 38 | C18 | 18 | 18 | 3 | 70 | C2× C.12 | 24 | 12 | 3, 69 | 102 | C2× C.16 | 32 | 16 | 5, 101 | |||
7 | C6 | 6 | 6 | 3 | 39 | C2× C.12 | 24 | 12 | 2, 38 | 71 | C70 | 70 | 70 | 7 | 103 | C102 | 102 | 102 | 5 | |||
8 | C2× C.2 | 4 | 2 | 3, 5 | 40 | C2× C.2× C.4 | 16 | 4 | 3, 11, 39 | 72 | C2× C.2× C.6 | 24 | 6 | 5, 17, 19 | 104 | C2× C.2× C.12 | 48 | 12 | 3, 5, 103 | |||
9 | C6 | 6 | 6 | 2 | 41 | C40 | 40 | 40 | 6 | 73 | C72 | 72 | 72 | 5 | 105 | C2× C.2× C.12 | 48 | 12 | 2, 29, 41 | |||
10 | C4 | 4 | 4 | 3 | 42 | C2× C.6 | 12 | 6 | 5, 13 | 74 | C36 | 36 | 36 | 5 | 106 | C52 | 52 | 52 | 3 | |||
11 | C10 | 10 | 10 | 2 | 43 | C42 | 42 | 42 | 3 | 75 | C2× C.20 | 40 | 20 | 2, 74 | 107 | C106 | 106 | 106 | 2 | |||
12 | C2× C.2 | 4 | 2 | 5, 7 | 44 | C2× C.10 | 20 | 10 | 3, 43 | 76 | C2× C.18 | 36 | 18 | 3, 37 | 108 | C2× C.18 | 36 | 18 | 5, 107 | |||
13 | C12 | 12 | 12 | 2 | 45 | C2× C.12 | 24 | 12 | 2, 44 | 77 | C2× C.30 | 60 | 30 | 2, 76 | 109 | C108 | 108 | 108 | 6 | |||
14 | C6 | 6 | 6 | 3 | 46 | C22 | 22 | 22 | 5 | 78 | C2× C.12 | 24 | 12 | 5, 7 | 110 | C2× C.20 | 40 | 20 | 3, 109 | |||
15 | C2× C.4 | 8 | 4 | 2, 14 | 47 | C46 | 46 | 46 | 5 | 79 | C78 | 78 | 78 | 3 | 111 | C2× C.36 | 72 | 36 | 2, 110 | |||
16 | C2× C.4 | 8 | 4 | 3, 15 | 48 | C2× C.2× C.4 | 16 | 4 | 5, 7, 47 | 80 | C2× C.4× C.4 | 32 | 4 | 3, 7, 79 | 112 | C2× C.2× C.12 | 48 | 12 | 3, 5, 111 | |||
17 | C16 | 16 | 16 | 3 | 49 | C42 | 42 | 42 | 3 | 81 | C54 | 54 | 54 | 2 | 113 | C112 | 112 | 112 | 3 | |||
18 | C6 | 6 | 6 | 5 | 50 | C20 | 20 | 20 | 3 | 82 | C40 | 40 | 40 | 7 | 114 | C2× C.18 | 36 | 18 | 5, 37 | |||
19 | C18 | 18 | 18 | 2 | 51 | C2× C.16 | 32 | 16 | 5, 50 | 83 | C82 | 82 | 82 | 2 | 115 | C2× C.44 | 88 | 44 | 2, 114 | |||
20 | C2× C.4 | 8 | 4 | 3, 19 | 52 | C2× C.12 | 24 | 12 | 7, 51 | 84 | C2× C.2× C.6 | 24 | 6 | 5, 11, 13 | 116 | C2× C.28 | 56 | 28 | 3, 115 | |||
21 | C2× C.6 | 12 | 6 | 2, 20 | 53 | C52 | 52 | 52 | 2 | 85 | C4× C.16 | 64 | 16 | 2, 3 | 117 | C6× C.12 | 72 | 12 | 2, 17 | |||
22 | C10 | 10 | 10 | 7 | 54 | C18 | 18 | 18 | 5 | 86 | C42 | 42 | 42 | 3 | 118 | C58 | 58 | 58 | 11 | |||
23 | C22 | 22 | 22 | 5 | 55 | C2× C.20 | 40 | 20 | 2, 21 | 87 | C2× C.28 | 56 | 28 | 2, 86 | 119 | C2× C.48 | 96 | 48 | 3, 118 | |||
24 | C2× C.2× C.2 | 8 | 2 | 5, 7, 13 | 56 | C2× C.2× C.6 | 24 | 6 | 3, 13, 29 | 88 | C2× C.2× C.10 | 40 | 10 | 3, 5, 7 | 120 | C2× C.2× C.2× C.4 | 32 | 4 | 7, 11, 19, 29 | |||
25 | C20 | 20 | 20 | 2 | 57 | C2× C.18 | 36 | 18 | 2, 20 | 89 | C88 | 88 | 88 | 3 | 121 | C110 | 110 | 110 | 2 | |||
26 | C12 | 12 | 12 | 7 | 58 | C28 | 28 | 28 | 3 | 90 | C2× C.12 | 24 | 12 | 7, 11 | 122 | C60 | 60 | 60 | 7 | |||
27 | C18 | 18 | 18 | 2 | 59 | C58 | 58 | 58 | 2 | 91 | C6× C.12 | 72 | 12 | 2, 3 | 123 | C2× C.40 | 80 | 40 | 7, 83 | |||
28 | C2× C.6 | 12 | 6 | 3, 13 | 60 | C2× C.2× C.4 | 16 | 4 | 7, 11, 19 | 92 | C2× C.22 | 44 | 22 | 3, 91 | 124 | C2× C.30 | 60 | 30 | 3, 61 | |||
29 | C28 | 28 | 28 | 2 | 61 | C60 | 60 | 60 | 2 | 93 | C2× C.30 | 60 | 30 | 11, 61 | 125 | C100 | 100 | 100 | 2 | |||
30 | C2× C.4 | 8 | 4 | 7, 11 | 62 | C30 | 30 | 30 | 3 | 94 | C46 | 46 | 46 | 5 | 126 | C6× C.6 | 36 | 6 | 5, 13 | |||
31 | C30 | 30 | 30 | 3 | 63 | C6× C.6 | 36 | 6 | 2, 5 | 95 | C2× C.36 | 72 | 36 | 2, 94 | 127 | C126 | 126 | 126 | 3 | |||
32 | C2× C.8 | 16 | 8 | 3, 31 | 64 | C2× C.16 | 32 | 16 | 3, 63 | 96 | C2× C.2× C.8 | 32 | 8 | 5, 17, 31 | 128 | C2× C.32 | 64 | 32 | 3, 127 |
Viz také
Poznámky
- ^ Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.
- ^ Primitivní kořen, Encyclopedia of Mathematics
- ^ (Vinogradov 2003, s. 105–121, § VI PRIMITIVNÍ KOŘENY A INDIKACE)
- ^ (Gauss & Clarke 1986 umění. 52–56, 82–891)
- ^ (Vinogradov 2003, str. 106)
- ^ (Gauss & Clarke 1986 umění. 90–91)
- ^ Riesel to všechno pokrývá. (Riesel 1994, str. 267–275)
- ^ Erdős, Paul; Pomerance, Carle (1986). „O počtu falešných svědků pro složené číslo“. Matematika. Comput. 46 (173): 259–279. doi:10.1090 / s0025-5718-1986-0815848-x. Zbl 0586.10003.
Reference
The Disquisitiones Arithmeticae byl přeložen z Gaussova Ciceronian latina do Angličtina a Němec. Německé vydání obsahuje všechny jeho práce o teorii čísel: všechny důkazy o kvadratická vzájemnost, určení znaménka Gaussova suma, vyšetřování dvojkvadratická vzájemnost a nepublikované poznámky.
- Gauss, Carl Friedrich; Clarke, Arthur A. (překladatel do angličtiny) (1986), Disquisitiones Arithmeticae (druhé, opravené vydání), New York: Springer, ISBN 978-0-387-96254-2
- Gauss, Carl Friedrich; Maser, H. (překladatel do němčiny) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae a další články o teorii čísel) (druhé vydání), New York: Chelsea, ISBN 978-0-8284-0191-3
- Riesel, Hans (1994), Prvočísla a počítačové metody pro faktorizaci (druhé vydání), Boston: Birkhäuser, ISBN 978-0-8176-3743-9
- Vinogradov, I. M. (2003), „§ VI PRIMITIVNÍ KOŘENY A INDIKÁTY“, Prvky teorie čísel, Mineola, NY: Dover Publications, s. 105–121, ISBN 978-0-486-49530-9