Çarpımsal tamsayı grubu modulo n -Multiplicative group of integers modulo n

Olarak modüler aritmetik , tam sayılar asal için (göreceli asal) n kümesinden arasında n- negatif olmayan tam bir oluşturan grup çarpma altında modülo N adı verilen tamsayılar çarpımsal grubu modulo n . Aynı şekilde, bu grubun elemanları düşünülebilir uyum sınıfları olarak da bilinen, kalıntıları modulo n için göreceli asal olduğu, n . Bu nedenle başka bir isim, modulo n ilkel kalıntı sınıfları grubudur . Gelen halkaların teori , bir dalı soyut cebir , bu şekilde açıklanan birim grubunun tamsayılar halkasının modulo n . Burada birimler , bu halkada tam olarak n'nin aralarında asal olan çarpımsal tersi olan öğeleri ifade eder . ${\görüntüleme stili \{0,1,\noktalar,n-1\}}$

Cebirsel yapı → Grup teorisi Grup teorisi
Temel kavramlar alt grup Normal alt grup bölüm grubu (Yarı-) direkt ürün Grup homomorfizmaları çekirdek resim doğrudan toplam çelenk ürünü basit sonlu sonsuz sürekli çarpımsal katkı döngüsel değişmeyen dihedral nilpotent çözülebilir eylem Grup teorisi sözlüğü grup teorisi konularının listesi
sonlu gruplar Sonlu basit grupların sınıflandırılması döngüsel dönüşümlü yalan türü sporadik Cauchy teoremi Lagrange teoremi Sylow teoremleri Hall teoremi p grubu Temel değişmeli grup Frobenius grubu Schur çarpanı Simetrik grup S n Klein dört grup V Dihedral grup D n Kuaterniyon grubu Q Disiklik grup Dic n
ayrık gruplar kafesler Tamsayılar ( )${\displaystyle \mathbb {Z} }$ Ücretsiz grup Modüler gruplar PSL(2, )${\displaystyle \mathbb {Z} }$ SL(2, )${\displaystyle \mathbb {Z} }$ aritmetik grubu kafes hiperbolik grup
Topolojik ve Lie grupları solenoid Daire Genel doğrusal GL( n ) Özel doğrusal SL( n ) Ortogonal O( n ) Öklid E( n ) Özel ortogonal SO( n ) Üniter U( n ) Özel üniter SU( n ) Simplektik Sp( n ) G, 2 F 4 E 6 E 7 E 8 Lorentz poincare konformal difeomorfizm Döngü Sonsuz boyutlu Lie grubu O(∞) SU(∞) Sp(∞)
cebirsel gruplar Doğrusal cebir grubu indirgeyici grup değişmeli çeşit eliptik eğri
v T e

Bu bölüm grubu , genellikle belirtilen, içinde temel bir sayı teorisi . Kriptografi , tamsayı çarpanlarına ayırma ve asallık testinde uygulamalar bulmuştur . Bu, sırası Euler'in totient fonksiyonu tarafından verilen değişmeli , sonlu bir gruptur : Asal n için grup döngüseldir ve genel olarak yapının tanımlanması kolaydır, ancak asal n için bile üreteçleri bulmak için genel bir formül bilinmemesine rağmen . ${\ Displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).}$

Grup aksiyomları

Çarpma altında, bir değişmeli grup için aksiyomları karşılayan n için asal olan modulo n uygunluk sınıfları kümesini göstermek için basit bir alıştırmadır .

Gerçekten de, bir karşı göreceli asal olan n , ancak ve ancak gcd ( bir , n = 1) . Aynı uygunluk sınıfındaki a ≡ b (mod n ) tamsayıları gcd( a , n ) = gcd( b , n ) ' yi karşılar , dolayısıyla biri ve ancak diğeri ise n'ye asaldır . Böylece uyum sınıflarının kavramı modulo n edilene göreceli asal olan n iyi tanımlanmıştır.

Yana gcd ( bir , n ) = 1 ve gcd ( b , n ) 1 = ima gcd ( ab , n ) 1 = sınıfların grubu için asal, n, çarpma altında kapatılır.

Tamsayı çarpması, uygunluk sınıflarını dikkate alır, yani a ≡ a' ve b ≡ b' (mod n ) ab ≡ a'b' (mod n ) anlamına gelir . Bu, çarpmanın birleştirici, değişmeli olduğu ve 1 sınıfının benzersiz çarpımsal özdeşlik olduğu anlamına gelir.

Son olarak, söz konusu bir , çarpımsal ters ait bir modülo N bir tam sayı olduğu X tatmin ax ≡ 1 (mod N ) . a tam olarak n ile asal olduğunda var olur , çünkü bu durumda gcd( a , n ) = 1 ve Bézout'un lemmasına göre ax + ny = 1'i sağlayan x ve y tam sayıları vardır . ax + ny = 1 denkleminin , x'in n'ye asal olduğunu ima ettiğine dikkat edin , bu nedenle çarpımsal tersi gruba aittir.

gösterim

Toplama ve çarpma işlemleriyle modulo n tamsayılarının (uyum sınıfları) kümesi bir halkadır . İle gösterilir   veya    (gösterim, modulo tamsayılarının bölümünün ideal olarak alınması veya n'nin katlarından oluşması anlamına gelir ). Sayı teorisinin dışında, daha basit gösterim sıklıkla kullanılır, ancak n bir asal sayı olduğunda p -adic tamsayılarla karıştırılabilir . ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} /(n)}$ ${\displaystyle n\mathbb {Z} }$${\görüntüleme stili (n)}$${\displaystyle \mathbb {Z} _{n}}$

Bu halkadaki birimlerin grubu olan modulo n tamsayılarının çarpımsal grubu, (yazarına bağlı olarak)   ( birim olarak çevrilen Almanca Einheit için ) , veya benzer gösterimler şeklinde yazılabilir. Bu makale${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}$   ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}$   ${\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),}$   ${\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )}$${\displaystyle \mathbb {Z} _{n}^{*}}$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

Notasyon , n düzeyindeki döngüsel gruba atıfta bulunur . Öyle izomorf tam sayıların grubu modulo için n ek altında. Dikkat edin veya ek altındaki gruba da atıfta bulunabilir. Örneğin, bir p asalının çarpımsal grubu döngüseldir ve dolayısıyla toplama grubuna göre izomorfiktir, ancak izomorfizm açık değildir. ${\ Displaystyle \ matematik {C} _{n}}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} _{n}}$${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$${\displaystyle \mathbb {Z} /(p-1)\mathbb {Z} }$

Yapı

Tamsayılar çarpımsal grubunun dizi modulo n tam sayılar sayısı için asal n . Bu verilir totient : (dizi A000010 içinde OEIS ). Asal p için , . ${\görüntüleme stili \{0,1,\noktalar,n-1\}}$${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n)}$${\displaystyle \varphi (p)=p-1}$

döngüsel durum

Grup , ancak ve ancak n 1, 2, 4, p ^k veya 2 p ^{k ise} ve burada p tek bir asal ve k > 0 ise döngüseldir . n'nin diğer tüm değerleri için grup döngüsel değildir. Bu ilk olarak Gauss tarafından kanıtlanmıştır . ${\ Displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Bu, bu n için şu anlama gelir :

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times}\cong \mathrm {C} _{\varphi (n)},}$ nerede ${\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}$

Ve bir sahip olması durumunda Tanım gereği, grubunun, halkalı bir jeneratör g (bir jeneratör { g , yetki olan boyutu birinin}), mümkün olan tüm artıklar modulo elde n için göreceli asal n (ilk güçler tam olarak bir kez, her vermek ). Bir üretecine ilkel kök modulo n denir . Jeneratör varsa onlardan da vardır. ${\displaystyle g^{0},g^{1},g^{2},\dots ,}$${\görüntüleme stili \varphi (n)}$${\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}$${\ Displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$${\görüntüleme stili \varphi (\varphi (n))}$

2'nin güçleri

Modulo 1 herhangi iki tamsayı uyumludur, yani sadece bir uyum sınıfı vardır, [0], 1 ile asaldır. Bu nedenle, φ(1) = 1 elemanlı önemsiz gruptur . Önemsiz doğası nedeniyle, modulo 1 kongrüans durumu genellikle göz ardı edilir ve bazı yazarlar n = 1 durumunu teorem ifadelerine dahil etmemeyi tercih eder . ${\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times}\cong \mathrm {C} _{1}}$

Modülo 2, yani sadece tek bir göreceli asal uyum sınıfı, [1] orada olduğu önemsiz grubu . ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

Modulo 4, [1] ve [3] olmak üzere iki asal uygunluk sınıfı vardır, bu nedenle iki elemanlı döngüsel grup. ${\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}$

Modulo 8, [1], [3], [5] ve [7] olmak üzere dört tane asal uygunluk sınıfı vardır. Bunların her biri, kare, böylece 1, Klein, dört grup . ${\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$

Modulo 16, [1], [3], [5], [7], [9], [11], [13] ve [15] olmak üzere sekiz tane asal uygunluk sınıfı vardır. 2 burulma alt grubudur (yani, her elemanın karesi 1'dir), dolayısıyla döngüsel değildir. 3 yetkileri, 5 güçler gibi, sipariş 4 bir alt grubudur   Dolayısıyla${\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}$${\görüntüleme stili \{1,3,9,11\}}$${\görüntüleme stili \{1,5,9,13\}.}$${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}$

8 ve 16 ile gösterilen model daha yüksek güçler için geçerlidir ^2k , k > 2 : 2-burulma alt grubudur (yani döngüsel değildir) ve 3'ün güçleri 2 ^{k − 2} mertebesinde bir döngüsel alt gruptur , yani${\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\kez }}$${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k -2}}.}$

Genel bileşik sayılar

By sonlu değişmeli grupların temel teoremi , grup bir izomorftur doğrudan ürünün asal güç siparişlerin halkalı gruplar. ${\ Displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Daha spesifik olarak, Çin kalan teoremi , eğer öyleyse, halkanın , asal güç faktörlerinin her birine karşılık gelen halkaların doğrudan ürünü olduğunu söylüyor : ${\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

${\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb { Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z } \noktalar \;\;}$

Benzer şekilde, birimler grubu , asal güç faktörlerinin her birine karşılık gelen grupların doğrudan ürünüdür: ${\ Displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} ) ^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{ 3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}$

Her bir tek asal güç için karşılık gelen faktör , asal-kuvvet sıralarının döngüsel gruplarını daha da çarpanlarına ayırabilecek döngüsel mertebe grubudur . 2'nin kuvvetleri için faktör , k = 0, 1, 2 olmadıkça döngüsel değildir , ancak yukarıda açıklandığı gibi döngüsel gruplara çarpanlara ayrılır. ${\görüntüleme stili p^{k}}$${\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\kez }}$${\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}$${\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\kez }}$

Grubun sırası , doğrudan üründeki döngüsel grupların sıralarının ürünüdür. Üs olan grubun, en sık birden siklik grupları siparişlerin, ile verilmektedir Carmichael fonksiyonu (dizi A002322 olarak OEIS ). Diğer bir deyişle, her biri için en küçük sayıda şekildedir bir üzere asal n , tutar. Sadece ve sadece grup döngüsel ise bölünür ve ona eşittir. ${\görüntüleme stili \varphi (n)}$ ${\displaystyle \lambda (n)}$${\displaystyle \lambda (n)}$${\displaystyle a^{\lambda (n)}\eşdeğer 1{\pmod {n}}}$${\görüntüleme stili \varphi (n)}$

Sahte tanıklar alt grubu

Eğer n bileşik ise, çarpımsal grubun bir alt grubu vardır ve "yanlış tanıklar grubu" olarak adlandırılır ve burada elemanlar n - 1 kuvvetine yükseltildiklerinde 1 modulo n ile uyumludur . (Herhangi bir güce yükseltildiğinde 1 kalıntısı 1 modulo n ile uyumlu olduğundan , bu tür elemanların kümesi boş değildir.) Fermat'ın Küçük Teoremi nedeniyle , bu tür artıkların "yanlış pozitifler" veya "yanlış tanıklar" olduğu söylenebilir. arasında asallık n . 2 sayısı bu temel asallık kontrolünde en sık kullanılan kalıntıdır, dolayısıyla 341 = 11 × 31 ünlüdür çünkü 2 ³⁴⁰ 1 modulo 341 ile uyumludur ve 341 bu tür en küçük bileşik sayıdır (2'ye göre). 341 için, yalancı tanıklar alt grubu 100 kalıntı içerir ve bu nedenle, mod 341 300 elemanlı çarpma grubu içinde indeks 3'tedir.

Örnekler

sayı = 9

Önemsiz bir sahte tanık alt grubuna sahip en küçük örnek 9 = 3 × 3'tür . 9 ile aynı asal 6 artık vardır: 1, 2, 4, 5, 7, 8. 8, -1 modulo 9 ile uyumlu olduğundan , 8 ^8'in 1 modulo 9 ile uyumlu olduğu sonucu çıkar. Dolayısıyla 1 ve 8 için yanlış pozitiflerdir. 9'un "asallığı" (9 aslında asal olmadığı için). Bunlar aslında tek olanlardır, dolayısıyla {1,8} alt grubu yalancı tanıkların alt grubudur. Aynı argüman, n - 1'in herhangi bir tek bileşik n için "yanlış tanık" olduğunu gösterir .

sayı = 91

İçin , n = 91 (= 7 x 13), orada kalıntıları, 91 asal yarısı (diğer bir deyişle, bunların 36) 91 yalancı tanık, yani 1, 3, 4, 9, 10, 12, 16, 17 vardır , 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 çünkü bu değerler için, 87, 88, ve 90, x , x ⁹⁰ uyumlu 1 mod 91'dir. ${\görüntüleme stili \varphi (91)=72}$

sayı = 561

n = 561 (= 3 × 11 × 17) bir Carmichael sayısıdır , bu nedenle s ⁵⁶⁰ , s'nin 561'e eşit asal herhangi bir tamsayı için 1 modulo 561'e eşittir. Bu durumda, yalancı tanıklar alt grubu uygun değildir; 320 kalıntıdan oluşan modülo 561 çarpımsal birimlerin tüm grubudur.

Örnekler

Bu tablo, n ≤ 128 için bir üretici kümenin ve döngüsel ayrışmasını gösterir . Ayrıştırma ve üretici kümeler benzersiz değildir; Örneğin, ${\ Displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle \displaystyle {\begin{hizalanmış}(\mathbb {Z} /35\mathbb {Z} )^{\times }&\cong (\mathbb {Z} /5\mathbb {Z} )^{\ kez }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong \mathrm {C} _{4}\times \mathrm {C} _{6}\cong \mathrm { C} _{4}\times \mathrm {C} _{2}\times \mathrm {C} _{3}\cong \mathrm {C} _{2}\times \mathrm {C} _{12} \cong (\mathbb {Z} /4\mathbb {Z} )^{\times }\times (\mathbb {Z} /13\mathbb {Z} )^{\times }\\&\cong (\mathbb {Z} /52\mathbb {Z} )^{\times }\end{hizalı}}}$

(ama ). Aşağıdaki tablo en kısa ayrıştırmayı listeler (bunlar arasında sözlükbilimsel olarak ilk seçilir - bu, izomorfik grupların aynı ayrıştırmalarla listelenmesini garanti eder). Oluşturucu küme de mümkün olduğunca kısa olacak şekilde seçilir ve ilkel köklü n için en küçük ilkel kök modulo n listelenir. ${\displaystyle \not \cong \mathrm {C} _{24}\cong \mathrm {C} _{8}\times \mathrm {C} _{3}}$

Örneğin, al . O zaman , grubun sırasının 8 olduğu anlamına gelir (yani, 20'den küçük 8 sayı vardır ve ona asaldır); her elemanın sırası 4'e bölünür, yani 20'ye asal olan herhangi bir sayının dördüncü kuvveti 1'e eşittir (mod 20). {3,19} kümesi grubu oluşturur; bu, her öğesinin 3 ^a × 19 ^b biçiminde olduğu anlamına gelir (burada a , 0, 1, 2 veya 3'tür, çünkü öğe 3, sıra 4'e sahiptir ve benzer şekilde b 0 veya 1'dir, çünkü eleman 19'un sırası 2) vardır. ${\ Displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$${\görüntüleme stili \varphi (20)=8}$${\displaystyle \lambda (20)=4}$${\ Displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$

En küçük ilkel kök mod n'dir (kök yoksa 0'dır)

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, ... (dizi A046145 olarak OEIS )

Minimum üretici mod n kümesindeki öğelerin sayıları ,

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, ... (dizi A046072 olarak OEIS )

Ayrıca bakınız

• Lenstra eliptik eğri çarpanlarına ayırma

Notlar

Referanslar

Disquisitiones Arithmeticae Gauss çevrildi Ciceronian Latin içine İngilizce ve Almanca . Alman baskısı sayılar teorisi üzerine kağıtları tümünü içerir: tüm deliller karesel karşılıklılık , işareti belirlenmesi Gauss toplamı , içine araştırmalar biquadratic karşılıklılık ve yayınlanmamış notları.

• Gauss, Carl Friedrich; Clarke, Arthur A. (İngilizceye çeviren) (1986), Disquisitiones Arithmeticae (İkinci, düzeltilmiş baskı) , New York: Springer , ISBN 978-0-387-96254-2
• Gauss, Carl Friedrich; Maser, H. (Almancaya çevirmen) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & sayı teorisi üzerine diğer makaleler) (İkinci baskı) , New York: Chelsea, ISBN 978-0-8284-0191-3
• Riesel, Hans (1994), Çarpanlara Ayırma için Asal Sayılar ve Bilgisayar Yöntemleri (ikinci baskı) , Boston: Birkhäuser, ISBN 978-0-8176-3743-9
• Vinogradov, IM (2003), "§ VI İLKEL KÖKLER VE ENDEKSLER" , Elements of Number Theory , Mineola, NY: Dover Publications, s. 105–121, ISBN 978-0-486-49530-9

Dış bağlantılar

• Weisstein, Eric W. "Modulo Çarpma Grubu" . Matematik Dünyası .
• Weisstein, Eric W. "İlkel Kök" . Matematik Dünyası .
• Grup tablolarını etkileşimli olarak hesaplamak için Web tabanlı araç, John Jones tarafından