प्रिमिटिव रूट मॉड्यूलो n

मॉड्यूलर अंकगणित में, संख्या g आदिम रूट मॉड्यूलो n है n अगर हर नंबर a सह अभाज्य n की शक्ति से सर्वांगसमता संबंध है g मापांक n वह है, g आदिम रूट मॉड्यूलो है n यदि प्रत्येक पूर्णांक के लिए a कोप्राइम n, कुछ पूर्णांक है k जिसके लिए g^k ≡ a (mod n). ऐसा मान k का सूचकांक या असतत लघुगणक कहा जाता है a आधार के लिए g मापांक n. इसलिए g आदिम रूट मॉड्यूलो है n अगर और केवल अगर g पूर्णांक मॉड्यूलो n|पूर्णांक मॉड्यूलो के गुणक समूह का जेनरेटिंग सेट n है

कार्ल फ्रेडरिक गॉस ने आदिम रूट को अंकगणितीय शोध (1801) के अनुच्छेद 57 में परिभाषित किया, जहां उन्होंने इस शब्द को गढ़ने का श्रेय यूलर को दिया। अनुच्छेद 56 में उन्होंने कहा कि जोहान हेनरिक लैम्बर्ट और यूलर उनके बारे में जानते थे, लेकिन वह पहले व्यक्ति थे जिन्होंने कठोर रूप से प्रदर्शित किया कि अभाज्य संख्या के लिए आदिम रूट उपस्थित हैं। n वास्तव में, विवादों में दो प्रमाण होते हैं: अनुच्छेद 54 में एक गैर-रचनात्मक अस्तित्व प्रमेय है, जबकि अनुच्छेद 55 में प्रमाण रचनात्मक प्रमाण है।

प्रारंभिक उदाहरण

नंबर 3 प्रिमिटिव रूट मोडुलो 7 है क्योंकि

${\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\\3^{7}&=&3^{6}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\\end{array}}$

यहाँ हम देखते हैं कि 3 का क्रम (समूह सिद्धांत) 3^k मॉड्यूलो 7 और 6 है। अवधि में अवशेष, जो 3, 2, 6, 4, 5, 1 हैं, सभी अशून्य अवशेषों मॉड्यूलो 7 की पुनर्व्यवस्था बनाते हैं, जिसका अर्थ है कि 3 वास्तव में आदिम रूट मॉड्यूलो 7 है यह इस तथ्य से निकला है कि अनुक्रम (g^k मोडुलोn) के कुछ मान के बाद हमेशा दोहराता है k, मॉड्यूल के बाद से n मूल्यों की सीमित संख्या उत्पन्न करता है। अगर g आदिम रूट मॉड्यूलो है n और n प्रधान है, तो पुनरावृत्ति की अवधि है n − 1. इस तरह से बनाए गए क्रमपरिवर्तन (और उनके वृत्ताकार बदलाव) कोस्टास सरणी वेल्च के रूप में दिखाए गए हैं।

परिभाषा

अगर n धनात्मक पूर्णांक है, 0 से पूर्णांक n − 1 जो कि कोप्राइम हैं n (या समतुल्य रूप से, सर्वांगसमता वर्ग सह अभाज्य हैं n) गुणन मॉड्यूलर अंकगणित के साथ समूह (गणित) बनाते हैं n ऑपरेशन के रूप में; इसे पूर्णांकों के गुणक समूह n द्वारा निरूपित किया जाता है $\mathbb {Z}$^×
_n, और इकाइयों का समूह कहा जाता है n, या प्रिमिटिव क्लास मोडुलो का समूह n. जैसा कि लेख में बताया गया है कि पूर्णांकों का गुणक समूह मॉड्यूल n पूर्णांक मॉड्यूलो का गुणक समूह n, यह गुणात्मक समूह ($\mathbb {Z}$^×
_n) चक्रीय समूह है अगर और केवल अगर n 2, 4 के बराबर है, p^k, या 2p^k कहाँ p^k एक विषम अभाज्य संख्या की शक्ति है। कब (और केवल कब) यह समूह $\mathbb {Z}$^×
_n चक्रीय है, इस चक्रीय समूह के समूह के जनरेटिंग सेट को आदिम रूट मॉड्यूल कहा जाता है n (या पूर्ण भाषा में एकता मॉड्यूलो की आदिम रूट n, एकता मॉड्यूल n बहुपद समीकरण x की रूट के मौलिक समाधान के रूप में अपनी भूमिका पर बल देते हुए^m
− 1 वलय में $\mathbb {Z}$_n), या बस का एक आदिम तत्व $\mathbb {Z}$^×
_n है

जब $\mathbb {Z}$^×
_n गैर-चक्रीय है, ऐसे आदिम तत्व मॉड n उपस्थित नहीं है। इसके बजाय, प्रत्येक प्रमुख घटक n की अपनी उप-आदिम रूट हैं (देखें 15 नीचे दिए गए उदाहरणों में)।

किसी के लिए n (की भी होगी या नहीं $\mathbb {Z}$^×
_n चक्रीय है), का क्रम $\mathbb {Z}$^×
_n यूलर के कुल फलन द्वारा दिया गया है φ(n) (sequence A000010 in the OEIS). और फिर, यूलर प्रमेय यह कहता है a^φ(n) ≡ 1 (mod n) हर एक के लिए a कोप्राइम n; की सबसे कम शक्ति a जो 1 मॉड्यूलो के अनुरूप है n का गुणन क्रम कहा जाता है a मापांक n. विशेष रूप से, के लिए a आदिम रूट मॉड्यूल होना n, a^φ(n) की सबसे छोटी शक्ति होनी चाहिए a जो 1 मॉड्यूलो के अनुरूप n है

उदाहरण

उदाहरण के लिए, यदि n = 14 फिर के तत्व $\mathbb {Z}$^×
_n सर्वांगसमता वर्ग {1, 3, 5, 9, 11, 13} हैं; वहाँ हैं φ(14) = 6 उनमें से। यहाँ उनकी शक्तियों की तालिका 14 मॉड्यूल है:

x     x, x2, x3, ... (mod 14)
 1 :   1
 3 :   3,  9, 13, 11,  5,  1 
 5 :   5, 11, 13,  9,  3,  1
 9 :   9, 11,  1
11 :  11,  9,  1
13 :  13,  1

1 का क्रम 1 है, 3 और 5 का क्रम 6 है, 9 और 11 का क्रम 3 है, और 13 का क्रम 2 है। इस प्रकार, 3 और 5 आदिम रूट मॉड्यूलो 14 हैं।

दूसरे उदाहरण के लिए आइए n = 15 . के तत्व $\mathbb {Z}$^×
₁₅ सर्वांगसमता वर्ग {1, 2, 4, 7, 8, 11, 13, 14} हैं; वहाँ हैं φ(15) = 8 उनमें से

 x     x, x2, x3, ... (mod 15)
 1 :   1
 2 :   2,  4,  8, 1 
 4 :   4,  1
 7 :   7,  4, 13, 1
 8 :   8,  4,  2, 1
11 :  11,  1
13 :  13,  4,  7, 1
14 :  14,  1

चूँकि ऐसी कोई संख्या नहीं है जिसका क्रम 8 है, कोई आदिम रूट मॉड्यूलो 15 नहीं है। वास्तव में, λ(15) = 4, कहाँ λ कारमाइकल फलन है। (sequence A002322 in the OEIS)

आदिम रूट की तालिका

नंबर $n$ जिनकी मूल रूट आकार की होती है

$n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},$

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}

ये नंबर हैं $n$ साथ $\varphi (n)=\lambda (n),$ क्रम में भी रखा A033948 OEIS में।

निम्न तालिका आदिम रूट मॉड्यूलो को सूचीबद्ध करती है n तक $n=31$:

$n$	आदिम रूट मॉड्यूलो $n$	क्रम $\varphi (n),$ (OEIS: A000010)	एक्सपोनेंट $\lambda (n),$ (OEIS: A002322)
1	0	1	1
2	1	1	1
3	2	2	2
4	3	2	2
5	2, 3	4	4
6	5	2	2
7	3, 5	6	6
8		4	2
9	2, 5	6	6
10	3, 7	4	4
11	2, 6, 7, 8	10	10
12		4	2
13	2, 6, 7, 11	12	12
14	3, 5	6	6
15		8	4
16		8	4
17	3, 5, 6, 7, 10, 11, 12, 14	16	16
18	5, 11	6	6
19	2, 3, 10, 13, 14, 15	18	18
20		8	4
21		12	6
22	7, 13, 17, 19	10	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	22
24		8	2
25	2, 3, 8, 12, 13, 17, 22, 23	20	20
26	7, 11, 15, 19	12	12
27	2, 5, 11, 14, 20, 23	18	18
28		12	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	28
30		8	4
31	3, 11, 12, 13, 17, 21, 22, 24	30	30

गुण

गॉस सिद्ध हुआ कि किसी भी अभाज्य संख्या के लिए p (एकमात्र अपवाद के साथ p = 3), इसकी आदिम रूट का गुणनफल 1 मॉड्यूल के अनुरूप है p वह सिद्ध भी हुआ कि किसी भी अभाज्य संख्या के लिए p, इसके आदिम मूलों का योग सर्वांगसम है μ(p − 1) रूप p, कहाँ μ मोबियस फलन है।

उदाहरण के लिए,

p = 3,	μ(2) = −1.	मूल रूट 2 है
p = 5,	μ(4) = 0.	आदिम रूट 2 और 3 हैं।
p = 7,	μ(6) = 1.	आदिम रूट 3 और 5 हैं।
p = 31,	μ(30) = −1.	आदिम रूट 3, 11, 12, 13, 17, 21, 22 और 24 हैं।

जैसे, बाद की आदिम रूट का उत्पाद है $2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}$, और उनका योग है $123\equiv -1\equiv \mu (31-1){\pmod {31}}$.

अगर $a$ आदिम रूट मॉड्यूलो प्राइम है $p$, तब $a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$.

आदिम रूट पर आर्टिन का अनुमान बताता है कि दिया हुआ पूर्णांक a जो कि न तो वर्ग संख्या है और न ही -1 आदिम रूट मॉडुलो अपरिमित रूप से अनेक अभाज्य संख्या है।

आदिम रूट ढूँढना

आदिम रूट के मॉड्यूलो की गणना करने के लिए कोई सामान्य सामान्य सूत्र नहीं है n ज्ञात है। चुकीं , आदिम रूट का पता लगाने की विधियाँ हैं जो सभी उम्मीदवारों को आज़माने की तुलना में तेज़ हैं। यदि किसी संख्या का गुणन क्रम (इसका मरोड़ समूह) m मापांक n यूलर के फाई फलन के बराबर है$\varphi (n)$(के लिए $\mathbb {Z}$^×
_n), तो यह आदिम रूट है। वास्तव में विलोम सत्य है: यदि m आदिम रूट मॉड्यूलो है n, फिर का गुणक क्रम m है $\varphi (n)=\lambda (n)~.$ हम इसका उपयोग उम्मीदवार का परीक्षण करने के लिए कर सकते हैं m यह देखने के लिए कि क्या यह आदिम है।

के लिए $n>1$ सबसे पहले, गणना करें $\varphi (n)~.$ फिर के विभिन्न प्रमुख कारकों का निर्धारण करें $\varphi (n)$, कहना p₁, ..., p_k. अंत में गणना करें

$g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k$

मॉड्यूलर घातांक के लिए तेज़ एल्गोरिथम का उपयोग करना जैसे कि वर्ग बनाकर घातांक संख्या g जिसके लिए ये k परिणाम सभी भिन्न हैं 1 से आदिम रूट है।

आदिम रूट की संख्या मॉड्यूलो n, यदि कोई हो, के बराबर है

$\varphi \left(\varphi (n)\right)$

चूंकि, सामान्य तौर पर, चक्रीय समूह के साथ r तत्व होते हैं $\varphi (r)$ जनरेटर, के साथ r को अभाज्य पूर्णांक होने के नाते n, जो उत्पन्न करता है n.

प्रधान के लिए n, यह बराबर है $\varphi (n-1)$, और तबसे $n/\varphi (n-1)\in O(\log \log n)$ जेनरेटर {2, ..., के बीच बहुत आम हैं n−1} और इस प्रकार इसे खोजना अपेक्षाकृत सरल है।

अगर g आदिम रूट मॉड्यूलो है p, तब g भी आदिम रूट मॉड्यूलो सभी शक्तियां हैं p^k जब तक g^p−1 ≡ 1 (मॉड p²); उस स्थिति में, g + p है।

अगर g आदिम रूट मॉड्यूलो है p^k, तब g भी सभी छोटी शक्तियों का आदिम रूट मोडुलो p है

अगर g आदिम रूट मॉड्यूलो है p^k, तो कोई g या g + p^k (जो भी विषम हो) आदिम रूट मॉड्यूल 2 p^k है.

आदिम रूट का पता लगाना p की रूट को खोजने के बराबर भी है (p − 1) सेंट साइक्लोटोमिक बहुपद मोडुलो p.

आदिम रूट के परिमाण का क्रम

सबसे कम आदिम रूट g_p मापांक p (श्रेणी 1, 2, ..., में p − 1 ) सामान्यतः छोटा होता है।

ऊपरी सीमा

बर्गेस (1962) सिद्ध हुआ कि प्रत्येक ε > 0 के लिए एक है C ऐसा है कि $g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.$

एमिल ग्रॉसवाल्ड (1981) ने सिद्ध किया कि अगर $p>e^{e^{24}}\approx 10^{11504079571}$, तब $g_{p}<p^{0.499}~.$

विक्टर शौप (1990, 1992) ने सिद्ध किया, सामान्यीकृत रीमैन परिकल्पना मानते हुए, कि g_p = O(log⁶ p).

निचली सीमा

फ्रिडलैंडर (1949) और साली (1950) सिद्ध हुएकि सकारात्मक स्थिरांक है C जैसे कि असीम रूप से कई अभाज्य संख्याओं के लिए g_p > C log p .यह सिद्ध किया जा सकता है प्राथमिक विधि से कि किसी भी सकारात्मक पूर्णांक के लिए M ऐसे अपरिमित रूप से अनेक अभाज्य संख्याएँ M < g_p < p − M .है

अनुप्रयोग

आदिम रूट मॉड्यूलो n अधिकांशतः छद्म यादृच्छिक संख्या जनरेटर में प्रयोग किया जाता है और क्रिप्टोग्राफी, जिसमें डिफी-हेलमैन कुंजी विनिमय योजना शामिल है। प्रसार (ध्वनिकी) आदिम-रूट विसारक संख्या-सैद्धांतिक अवधारणाओं जैसे कि आदिम रूट और द्विघात अवशेष पर आधारित हैं।

यह भी देखें

• डिरिचलेट चरित्र
• पूर्ण पश्चाताप प्रधान
• विल्सन की प्रमेय गौस.27s सामान्यीकरण|विल्सन की प्रमेय का गॉस का सामान्यीकरण
• गुणक क्रम
• द्विघात अवशेष
• एकता मॉड्यूलो की जड़ n एकता मॉड्यूलो की जड़ n

स्रोत

• Bach, Eric; Shallit, Jeffrey (1996). कुशल एल्गोरिदम. Algorithmic Number Theory. Vol. I. Cambridge, MA: The MIT Press. ISBN 978-0-262-02405-1.

• Carella, N. A. (2015). "कम से कम प्रधान आदिम जड़ें". International Journal of Mathematics and Computer Science. 10 (2): 185–194. arXiv:1709.01172.

डिक्विजिशन एरिथमेटिका का अनुवाद गॉस के सिसरोनियन लैटिन से अंग्रेजी और जर्मन में किया गया है। जर्मन संस्करण में संख्या सिद्धांत पर उनके सभी कागजात शामिल हैं: द्विघात पारस्परिकता के सभी प्रमाण, गॉस योग के चिह्न का निर्धारण, द्विवर्गीय पारस्परिकता की जांच, और अप्रकाशित नोट्स।

• Gauss, Carl Friedrich (1986) [1801]. अंकगणितीय शोध (in English). Translated by Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2.

• Gauss, Carl Friedrich (1965) [1801]. उच्च अंकगणित पर जांच [Studies of Higher Arithmetic] (in Deutsch). Translated by Maser, H. (2nd ed.). New York, NY: Chelsea. ISBN 978-0-8284-0191-3.

• Robbins, Neville (2006). शुरुआत संख्या सिद्धांत. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9.

• Vinogradov, I.M. (2003). "§ VI Primitive roots and indices". संख्या सिद्धांत के तत्व. Mineola, NY: Dover Publications. pp. 105–121. ISBN 978-0-486-49530-9.

• von zur Gathen, Joachim; Shparlinski, Igor (1998). "परिमित क्षेत्रों में गॉस काल के आदेश". Applicable Algebra in Engineering, Communication and Computing. 9 (1): 15–24. CiteSeerX 10.1.1.46.5504. doi:10.1007/s002000050093. MR 1624824. S2CID 19232025.

अग्रिम पठन

• Ore, Oystein (1988). Number Theory and Its History. Dover. pp. 284–302. ISBN 978-0-486-65620-5..

बाहरी संबंध

• Weisstein, Eric W. "Primitive Root". MathWorld.
• Holt. "Quadratic residues and primitive roots". Mathematics. Michigan Tech.
• "Primitive roots calculator". BlueTulip.