परिमित क्षेत्रों में इकाई के मूल

Last updated on Oct 29, 2025

यह लेख बताता है कि एक फाइनाइट फील्ड (Finite Field) में रूट्स ऑफ यूनिटी (Roots of Unity) क्या हैं और वे मल्टीप्लिकेटिव सबग्रुप्स (multiplicative subgroups) के साथ कैसे जुड़े हुए हैं। पाठक से Fundamental Theorem of Cyclic Groups के बारे में पिछले अध्याय से परिचित होने की अपेक्षा की जाती है।

यह प्रमेय बताता है कि, $q-1$ ऑर्डर (order) वाले एक मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_q^*$ को देखते हुए, $k$ ऑर्डर का एक अनूठा (unique) सबग्रुप मौजूद होता है, जब $k$ , $q-1$ को विभाजित करता है। अन्यथा, यदि $k$ , $q-1$ को विभाजित नहीं करता है, तो $k$ ऑर्डर का कोई सबग्रुप मौजूद नहीं होता है।

यह यह भी बताता है कि, यदि $g$ , $\mathbb{F}_q^*$ का एक जेनरेटर (generator) है, तो $g^\frac{q-1}{k}$ , $k$ ऑर्डर के सबग्रुप को जेनरेट करता है।

इस लेख में, हम दिखाएंगे कि इस सबग्रुप के सभी एलिमेंट्स (elements) वे हैं जिन्हें यूनिटी का $k$ -th रूट कहा जाता है, और जेनरेटर $\omega$ वह है जिसे प्रिमिटिव (primitive) $k$ -th रूट ऑफ यूनिटी कहा जाता है।

इस अध्याय के लिए प्रेरणा और लक्ष्य

एक फाइनाइट फील्ड में $1$ के वर्गमूल (square roots) की गणना करना आसान है: वे संख्याएं जो $1$ और नेगेटिव $1$ के कॉन्ग्रुएंट (congruent) हैं (जो क्रमशः $1$ और $q - 1$ हैं। याद रखें कि, एक फील्ड $\mathbb{F}_q$ में, संख्या $-x$ , $q-x$ के कॉन्ग्रुएंट होती है)। दूसरे शब्दों में, $\sqrt{1} = \{1, q-1 \}$ । यह सेट समीकरण $a^2 \equiv 1$ के समाधानों का सेट है, जहाँ $a$ फाइनाइट फील्ड का एक एलिमेंट है।

लेकिन क्या होगा अगर हम $1$ के घनमूल (cube roots) की गणना करना चाहें, या अधिक सामान्यतः, 1 के $k$ -th रूट्स की, यानी $\sqrt[^k]{1}$ ? परिभाषा के अनुसार, यूनिटी के $k$ -th रूट्स वे एलिमेंट्स हैं जो समीकरण $a^k \equiv 1$ को संतुष्ट करते हैं। लेकिन हम उन्हें कैसे खोज सकते हैं?

हम सभी एलिमेंट्स को एक-एक करके आज़मा सकते हैं — एक ब्रूट-फोर्स (brute-force) दृष्टिकोण — लेकिन जब फील्ड में कई एलिमेंट्स हों तो यह अव्यवहार्य (infeasible) होगा। सौभाग्य से, उन सभी को खोजने का एक आसान तरीका है। फाइनाइट फील्ड $\mathbb{F}_q$ में, यूनिटी के $k$ -th रूट्स सटीक रूप से $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप के एलिमेंट्स होते हैं। यह परिभाषा मानती है कि $k$ , $q-1$ को विभाजित करता है।

इसे सबसे सशक्त शब्दों में कहने के लिए: यदि एक फाइनाइट फील्ड में कोई एलिमेंट $a$ , $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप का हिस्सा है, तो यह यूनिटी का $k$ -th रूट है, और $a^k\equiv1$ है। और यदि एक एलिमेंट $a$ यूनिटी का $k$ -th रूट है (जिसका अर्थ है $a^k\equiv1)$ , तो यह $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप का हिस्सा है।

शब्दावली की समानता

ऐसा लग सकता है कि हम एक ही एंटिटी (एक मल्टीप्लिकेटिव ग्रुप में एक एलिमेंट) के लिए बस एक नई शब्दावली जोड़ रहे हैं और यह बता रहे हैं कि इसे $k$ -th पावर (power) तक बढ़ाने पर यह 1 के बराबर हो जाता है।

एक निश्चित अर्थ में, हाँ, हम उसी एंटिटी के लिए एक नया शब्द पेश कर रहे हैं: यूनिटी का $k$ -th रूट $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप में एक एलिमेंट है और इसके विपरीत भी। आमतौर पर, एक ही एंटिटी को दो नाम देने से भ्रम पैदा होता है, इसलिए हमें “रूट ऑफ यूनिटी” शब्द पेश करने को सही ठहराने की आवश्यकता है।

जब हम सबसे सामान्य अर्थों में $k$ ऑर्डर के साइक्लिक ग्रुप्स (cyclic groups) के बारे में बात करते हैं, तो हमारे पास यह गारंटी नहीं होती है कि उस ग्रुप में एक एलिमेंट लेने और उस एलिमेंट और खुद पर $k$ बार बाइनरी ऑपरेटर (binary operator) लागू करने से आइडेंटिटी एलिमेंट (identity element) प्राप्त होता है, यानी $a^k\equiv1$ , या अधिक सामान्यतः एक बाइनरी ऑपरेटर $\star$ के लिए:

\underbrace{a\star a\star\dots\star a}_k=\text{identity}

सामान्य तौर पर साइक्लिक ग्रुप्स के लिए, उपरोक्त गुण के सत्य होने की गारंटी नहीं है, लेकिन एक फाइनाइट फील्ड में रूट्स ऑफ यूनिटी के लिए, इसकी गारंटी है।

इसलिए, हम कह सकते हैं कि रूट्स ऑफ यूनिटी में वे सभी गुण होते हैं जो Fundamental Theorem of Cyclic Groups के अनुसार होने चाहिए, और उनमें यह गुण होता है कि $a^k\equiv1.$

तो, पाठक के मन को शांत करने के लिए, आप पहले से ही एक फाइनाइट ग्रुप में रूट्स ऑफ यूनिटी के बारे में काफी कुछ जानते हैं क्योंकि आप Fundamental Theorem of Cyclic Groups को समझते हैं। चूँकि एक फाइनाइट फील्ड में रूट्स ऑफ यूनिटी एक साइक्लिक सबग्रुप हैं, इसलिए उन पर Fundamental Theorem of Cyclic Groups लागू होता है।

हालाँकि, $a^k\equiv1$ की अतिरिक्त गारंटी अतिरिक्त गुणों को अनलॉक करती है जिनका कुशल ZK एल्गोरिदम सीधे लाभ उठाते हैं। ये गुण हमें Number Theoretic Transform और अन्य Zero-Knowledge Proof एल्गोरिदम, जैसे कि PLONK और ZK-STARKs जैसे कुशल एल्गोरिदम बनाने में सक्षम बनाते हैं।

हम बाद के अध्यायों में रूट्स ऑफ यूनिटी के इन अतिरिक्त गुणों का अध्ययन करते हैं। यह अध्याय परिभाषाओं और उदाहरणों पर केंद्रित है ताकि यह समझ विकसित की जा सके कि एक फाइनाइट फील्ड में एक एलिमेंट $a$ में $a^k\equiv1$ गुण होता है यदि और केवल यदि यह $k$ ऑर्डर के एक मल्टीप्लिकेटिव सबग्रुप का हिस्सा हो।

k-th रूट्स ऑफ यूनिटी की गणना करना k ऑर्डर के मल्टीप्लिकेटिव सबग्रुप को खोजने के समान है

Fundamental Theorem of Cyclic Groups पर लेख में, हमने सीखा कि $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप के सभी एलिमेंट्स को कैसे खोजा जाए। सबसे पहले, हम मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_q^*$ के जेनरेटर से इस सबग्रुप का एक जेनरेटर प्राप्त करते हैं। फिर, इस जेनरेटर का उपयोग करके, हम $k$ ऑर्डर के सबग्रुप के सभी एलिमेंट्स को खोज सकते हैं।

इस प्रकार, $\mathbb{F}_q$ के $k$ -th रूट्स ऑफ यूनिटी को खोजना $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप को खोजने से अलग नहीं है, यदि $k$ , $q-1$ को विभाजित करता है, जो हम पहले से ही करना जानते हैं।

इस अध्याय में हमारा उद्देश्य इस समानता को साबित करना है - सभी $k$ -th रूट्स ऑफ यूनिटी के ग्रुप और $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप के बीच, यदि $k$ , $q-1$ को विभाजित करता है।

ऐसा करने के लिए, हमें निम्नलिखित दो कथनों को साबित करने की आवश्यकता है:

$k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप के भीतर प्रत्येक एलिमेंट $a$ , $a^k\equiv 1$ को संतुष्ट करता है।
मान लीजिए $k$ , $q-1$ को विभाजित करता है। फिर, $\mathbb{F}_q^*$ में प्रत्येक एलिमेंट $a$ जो $a^k\equiv 1$ को संतुष्ट करता है, वह $k$ ऑर्डर के अद्वितीय सबग्रुप से संबंधित है।

हम यह स्पष्ट करने के लिए उदाहरणों के माध्यम से इन दो कथनों का पता लगाएंगे कि वे सत्य हैं। चूँकि औपचारिक प्रमाण गणितीय रूप से थोड़े कठिन हो सकते हैं, हम इच्छुक पाठक के लिए उनमें से कुछ को परिशिष्ट (appendix) के लिए टाल देंगे, हालाँकि हमने प्रमाणों को यथासंभव व्यापक रूप से समझने योग्य बनाने का प्रयास किया है।

1. $k$ ऑर्डर के सबग्रुप में प्रत्येक एलिमेंट $a$ , $a^k\equiv 1$ को संतुष्ट करता है

यह पहला कथन दर्शाता है कि $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप के सभी एलिमेंट्स $k$ -th रूट्स ऑफ यूनिटी हैं।

हालाँकि, यह सभी $k$ -th रूट्स ऑफ यूनिटी के ग्रुप और $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप के बीच समानता स्थापित करने के लिए पर्याप्त नहीं है (जब $k$ , $q-1$ को विभाजित करता है) क्योंकि यह गारंटी नहीं देता है कि सभी $k$ -th रूट्स ऑफ यूनिटी इस सबग्रुप से संबंधित हैं — जिस पर कथन 2 में चर्चा की जाएगी।

हम इस अनुभाग की शुरुआत इस कथन के प्रमाण के साथ करेंगे, और फिर उदाहरणों के माध्यम से दिखाएंगे कि यह कथन सत्य है।

कथन 1 का प्रमाण

Fundamental Theorem of Cyclic Groups पर लेख से याद करें कि $k$ ऑर्डर का एक अद्वितीय सबग्रुप $\omega = g^{\frac{q-1}{k}}$ द्वारा जेनरेट होता है, जहाँ $g$ मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_{q}^*$ का एक जेनरेटर है। हम $\langle\omega\rangle$ को मोडुलो (modulo) $q$ के साथ $\omega$ की क्रमिक पावर लेने से उत्पन्न एलिमेंट्स के रूप में संदर्भित करते हैं:

\langle\omega\rangle = \{\omega^{0},\omega^{1},\omega^{2},\dots ,\omega^{k-1}\}.

मान लें कि $\omega^m$ , $\langle\omega\rangle$ में किसी $0\le m\le k-1$ के लिए एक मनमाना (arbitrary) एलिमेंट है। लक्ष्य यह साबित करना है कि $(\omega^m)^k\equiv 1$ ।

नीचे दिए गए प्रमाण में यह माना गया है कि जेनरेटर में $\omega^k \equiv 1$ का गुण है; इस तथ्य के प्रमाण के लिए परिशिष्ट A देखें।

आइए $(\omega^m)^k$ की गणना निम्नानुसार करें:

\begin{aligned} (\omega^m)^k &= (\omega^{mk}) &&\qquad\text{Power of a power rule }\\ &= (\omega^{km}) &&\qquad\text{Commutativity of exponents}\\ &=(\omega^k)^m&&\qquad\text{Factoring the exponent}\\ &\equiv (1)^m&&\qquad\text{Based on the discussion in the appendix A: $\omega^k\equiv 1$}\\ &\equiv 1&&\qquad\text{One raised to an arbitrary power is 1}. \end{aligned}

इसलिए, $k$ ऑर्डर के सबग्रुप में प्रत्येक एलिमेंट, जब $k$ की पावर तक बढ़ाया जाता है, तो 1 के बराबर होता है।

$\mathbb{F}_7 = \{0,1,2,3,4,5,6\}$ में कथन 1 का उदाहरण

इस उदाहरण में, हमारे पास $q-1 = 7-1 = 6$ है। साथ ही, एलिमेंट $g = 3$ मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_q^* = \{1,2,3,4,5,6\}$ का एक जेनरेटर है।

मल्टीप्लिकेटिव ग्रुप के जेनरेटर को कैसे खोजा जाए, यह इस लेख में शामिल नहीं किया जाएगा, लेकिन galois लाइब्रेरी इसे करने का एक त्वरित तरीका प्रदान करती है। फील्ड $\mathbb{F}_q$ को देखते हुए, जेनरेटर खोजने का एक तरीका primitive_element प्रॉपर्टी का उपयोग करना है, जैसा कि नीचे दिखाया गया है।

import galois
GF = galois.GF(7) # define the field
GF.primitive_element # GF(3, order=7)

3 ऑर्डर का सबग्रुप

चूँकि 3, $q-1 = 6$ को विभाजित करता है, Fundamental Theorem of Cyclic Groups 3 ऑर्डर के एक अद्वितीय सबग्रुप के अस्तित्व की गारंटी देता है।

यह सबग्रुप $3^{\frac{q-1}{k}} = 3^{\frac{6}{3}} = 3^{2} = 9\equiv 2\pmod{7}$ द्वारा जेनरेट होता है। इस प्रकार,

\langle 2\rangle = \{2^0,2^1,2^2\} = \{1, 2, 4\}.

अब, हम यह सत्यापित करना चाहते हैं कि $\langle 2\rangle$ में प्रत्येक एलिमेंट $a$ , $a^3\equiv 1$ को संतुष्ट करता है। यह नीचे किया गया है:

\begin{aligned} &1^3 \equiv \boxed{1}\pmod{7}\\ &2^3 \equiv 8 \equiv \boxed{1}\pmod{7}\\ &4^3 \equiv 16 \cdot 4 \equiv 2 \cdot 4 \equiv 8 \equiv \boxed{1}\pmod{7}\\ \end{aligned}

तो, एलिमेंट्स $1, 2$ और $4$ , $a^3\equiv 1\pmod{7}$ को संतुष्ट करते हैं। इसलिए, शर्त संतुष्ट होती है।

2 ऑर्डर का सबग्रुप

चूँकि 2, $q-1 = 6$ को विभाजित करता है, Fundamental Theorem of Cyclic Groups 2 ऑर्डर के एक अद्वितीय सबग्रुप के अस्तित्व की गारंटी देता है।

यह सबग्रुप $3^{\frac{q-1}{k}} = 3^{\frac{6}{2}} = 3^{3} = 27\equiv 6\pmod{7}$ द्वारा जेनरेट होता है। इस प्रकार,

\langle 6\rangle = \{6^0,6^1\} = \{1, 6\}.

अब, हम यह सत्यापित करना चाहते हैं कि $\langle 6\rangle$ में प्रत्येक एलिमेंट $a$ , $a^2\equiv 1$ को संतुष्ट करता है।

\begin{aligned} &1^2 \equiv \boxed{1}\pmod{7}\\ &6^2 = 36 \equiv \boxed{1}\pmod{7} \end{aligned}

तो, एलिमेंट्स $1$ और $6$ , $a^2\equiv 1\pmod{7}$ को संतुष्ट करते हैं। इसलिए, शर्त संतुष्ट होती है।

अभ्यास. सत्यापित करें कि $\mathbb{F}_7^*$ में प्रत्येक एलिमेंट $a$ , $a^6\equiv 1$ को संतुष्ट करता है।

2. यदि $k$ , $q-1$ को विभाजित करता है, तो $\mathbb{F}_q^*$ में $a^k\equiv 1$ वाला प्रत्येक एलिमेंट $a$ , $k$ ऑर्डर के अद्वितीय सबग्रुप से संबंधित है

यह कथन जोर देकर कहता है कि सभी $k$ -th रूट्स ऑफ यूनिटी $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप से संबंधित हैं, बशर्ते कि $k$ , $q-1$ को विभाजित करे।

इस अनुभाग में, हम कुछ उदाहरणों के माध्यम से इस दावे को स्पष्ट करते हैं। इच्छुक पाठक के लिए पूरा प्रमाण परिशिष्ट B में प्रदान किया गया है।

आगे बढ़ने से पहले, आइए उस मामले पर विचार करें जहाँ $k$ , $q-1$ को विभाजित नहीं करता है। इस स्थिति में, Fundamental Theorem of Cyclic Groups हमें बताता है कि $k$ ऑर्डर का कोई सबग्रुप नहीं है, और इसलिए कोई समानता मौजूद नहीं हो सकती है।

$\mathbb{F}_7 = \{0,1,2,3,4,5,6\}$ में उदाहरण

$k=3$ ऑर्डर का सबग्रुप

चूँकि 3, $q-1 = 6$ को विभाजित करता है, इसलिए 3 ऑर्डर का एक अद्वितीय सबग्रुप मौजूद है। यह सबग्रुप $3^{\frac{q-1}{k}} = 3^{\frac{6}{3}} = 3^{2} = 9\equiv 2\pmod{7}$ द्वारा जेनरेट होता है। इस प्रकार,

\langle 2\rangle = \{2^0,2^1,2^2\} = \{1, 2, 4\}.

हम यह सत्यापित करना चाहते हैं कि $\mathbb{F}_{7}^*$ में प्रत्येक एलिमेंट $a$ जो $a^3\equiv 1$ को संतुष्ट करता है, $\mathbb{F}_{7}^*$ में $k = 3$ ऑर्डर के इस अद्वितीय सबग्रुप से संबंधित है। आइए $\mathbb{F}_{7}^*$ में ऐसे सभी एलिमेंट्स $a$ खोजें, निम्नानुसार:

\begin{aligned} &\boxed{1^3 \equiv 1}\pmod{7}\\ &\boxed{2^3 \equiv 8 \equiv 1}\pmod{7}\\ &3^3 \equiv 9 \cdot 3 \equiv 2 \cdot 3 \equiv 6\pmod{7}\\ &\boxed{4^3 \equiv 16 \cdot 4 \equiv 2 \cdot 4 \equiv 8 \equiv 1}\pmod{7}\\ &5^3 \equiv 25 \cdot 5 \equiv 4 \cdot 5 \equiv 20 \equiv 6\pmod{7}\\ &6^3 \equiv 36 \cdot 6 \equiv 1 \cdot 6 \equiv 6\pmod{7}. \end{aligned}

एलिमेंट्स $1, 2$ और $4$ , $a^3\equiv 1\pmod{7}$ को संतुष्ट करते हैं। ये तीन एलिमेंट्स $\mathbb{F}_{7}^*$ में $k =3$ ऑर्डर के सबग्रुप के बिल्कुल वही सदस्य हैं। इसलिए, $\mathbb{F}_{7}^*$ में प्रत्येक एलिमेंट $a$ जिसका $a^3\equiv 1$ है, $k = 3$ ऑर्डर के अद्वितीय सबग्रुप से संबंधित है।

अभ्यास. सत्यापित करें कि $\mathbb{F}_7^*$ में प्रत्येक एलिमेंट $a$ जो $a^2\equiv 1$ को संतुष्ट करता है, $k = 2$ ऑर्डर के अद्वितीय सबग्रुप से संबंधित है।

$\mathbb{F}_{17} = \{0,1,2,\dots,16\}$ में उदाहरण

इस उदाहरण में, हमारे पास $q-1 = 17-1 = 16$ है। साथ ही, एलिमेंट $g = 3$ मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_q^* = \{1,2,\dots,16\}$ का एक जेनरेटर है, जिसे galois लाइब्रेरी का उपयोग करके सत्यापित किया जा सकता है:

GF = galois.GF(17) # define the field
GF.primitive_element # GF(3, order=17)

$k=4$ ऑर्डर का सबग्रुप

चूँकि 4, $q-1 = 16$ को विभाजित करता है, 4 ऑर्डर का एक अद्वितीय सबग्रुप मौजूद है। यह सबग्रुप $3^{\frac{q-1}{k}} = 3^{\frac{16}{4}} = 3^{4} = 81\equiv 13\pmod{17}$ द्वारा जेनरेट होता है। इस प्रकार,

\langle 13\rangle = \{13^0,13^1,13^2, 13^3\} = \{1, 13, 16, 4\}.

हम यह सत्यापित करना चाहते हैं कि $\mathbb{F}_{17}^*$ में प्रत्येक एलिमेंट $a$ जो $a^4\equiv 1$ को संतुष्ट करता है, $\mathbb{F}_{17}^*$ में $k = 4$ ऑर्डर के इस अद्वितीय सबग्रुप से संबंधित है। आइए $\mathbb{F}_{17}^*$ में ऐसे सभी एलिमेंट्स $a$ खोजें, निम्नानुसार:

\begin{aligned} &\boxed{1^4 = 1}\\ &2^4 = 16\not\equiv 1\\ &3^4 = 81 \equiv 13\not\equiv 1\\ &\boxed{4^4 \equiv 16 \cdot 16 \equiv (-1) \cdot (-1) \equiv 1}\\ &5^4 \equiv 25 \cdot 25 \equiv 7 \cdot 7 \equiv 49 \equiv 15\not\equiv 1\\ &6^4 \equiv 36 \cdot 36 \equiv 2 \cdot 2 \equiv 4\not\equiv 1\\ &7^4 \equiv 49 \cdot 49 \equiv 15 \cdot 15 \equiv (-2) \cdot (-2)\equiv 4\not\equiv 1\\ &8^4 \equiv (2^3)^4 = (2^4)^3 \equiv (-1)^3 \equiv -1\equiv 16\not\equiv 1\qquad\qquad\pmod{17}\\ &9^4 = 81 \cdot 81 \equiv 13 \cdot 13 \equiv (-4) \cdot (-4) \equiv 16\not\equiv 1\\ &10^4 \equiv 100 \cdot 100 \equiv 15 \cdot 15 \equiv (-2) \cdot (-2) \equiv 4\not\equiv 1\\ &11^4 \equiv 121 \cdot 121 \equiv 2 \cdot 2 \equiv 4\not\equiv 1\\ &12^4 \equiv 144 \cdot 144 \equiv 8 \cdot 8 \equiv 13\not\equiv 1\\ &\boxed{13^4 \equiv 169 \cdot 169 \equiv 16 \cdot 16 \equiv (-1) \cdot (-1)\equiv 1}\\ &14^4 \equiv (-3)^4 \equiv 9 \cdot 9\equiv 13\not\equiv 1\\ &15^4\equiv (-2)^4\equiv 16\not\equiv 1\\ &\boxed{16^4 \equiv (-1)^4 \equiv 1}. \end{aligned}

एलिमेंट्स $1, 4, 13$ और $16$ , $a^4\equiv 1\pmod{17}$ को संतुष्ट करते हैं। ये चार एलिमेंट्स $\mathbb{F}_{17}^*$ में $k =4$ ऑर्डर के सबग्रुप के बिल्कुल वही सदस्य हैं। इसलिए, $\mathbb{F}_{17}^*$ में प्रत्येक एलिमेंट $a$ जिसका $a^4\equiv 1$ है, $k = 4$ ऑर्डर के अद्वितीय सबग्रुप से संबंधित है।

अभ्यास. सत्यापित करें कि $\mathbb{F}_{17}^*$ में प्रत्येक एलिमेंट $a$ जो $a^8\equiv 1$ को संतुष्ट करता है, $k = 8$ ऑर्डर के अद्वितीय सबग्रुप से संबंधित है।

प्रिमिटिव $k$ -th रूट ऑफ यूनिटी

एक प्रिमिटिव (primitive) $k$ -th रूट ऑफ यूनिटी एक विशेष $k$ -th रूट ऑफ यूनिटी है: यह वह $k$ -th रूट ऑफ यूनिटी है जो अन्य सभी $k$ -th रूट्स ऑफ यूनिटी को जेनरेट करता है।

चूँकि $k$ -th रूट्स ऑफ यूनिटी का वह ग्रुप जिसमें हमारी रुचि है, वही $k$ ऑर्डर का सबग्रुप है, प्रिमिटिव $k$ -th रूट्स ऑफ यूनिटी बिल्कुल इस सबग्रुप के जेनरेटर हैं।

नोट: उस मामले में जहाँ $k$ , $q-1$ को विभाजित नहीं करता है (फाइनाइट फील्ड्स $\mathbb{F}_q$ पर विचार करते हुए), वहाँ अभी भी $k$ -th रूट्स ऑफ यूनिटी हो सकते हैं, लेकिन इस मामले में कोई प्रिमिटिव $k$ -th रूट्स ऑफ यूनिटी नहीं होते हैं।

इस प्रकार, एक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी खोजना सीधा है: यह $k$ ऑर्डर के सबग्रुप का एक जेनरेटर खोजने के समान है, और Fundamental Theorem of Cyclic Groups हमें बताता है कि इसे कैसे करना है।

एक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी की एक औपचारिक परिभाषा यह है कि यह $k$ ऑर्डर के साथ यूनिटी का $k$ -th रूट है, जहाँ एक एलिमेंट $a$ का ऑर्डर सबसे छोटा धनात्मक (positive) पूर्णांक $r$ (शून्य से बड़ा) है ताकि $a^r \equiv 1$ हो।

उदाहरण के लिए, $4$ , $\mathbb{F}_7$ में यूनिटी का 6th रूट है क्योंकि $4^6\equiv 1\pmod{7}$ , लेकिन यह एक प्रिमिटिव 6th रूट नहीं है क्योंकि एक पावर 6 से कम है जो इसे $1$ बनाती है, विशेष रूप से 3, यानी $4^3 \equiv 1\pmod{7}$ ।

प्रिमिटिव $k$ -th रूट्स ऑफ यूनिटी की संख्या

जिस प्रकार $k$ ऑर्डर के एक सबग्रुप में एक से अधिक जेनरेटर हो सकते हैं, उसी प्रकार एक से अधिक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी हो सकते हैं। प्रिमिटिव $k$ -th रूट्स ऑफ यूनिटी की संख्या $k$ ऑर्डर के सबग्रुप के जेनरेटर की संख्या के समान है।

प्रिमिटिव $k$ -th रूट्स ऑफ यूनिटी (और जेनरेटर) की संख्या यूलर के टॉटिएंट फंक्शन (Euler’s totient function) $\phi(k)$ द्वारा दी गई है। इस तथ्य का प्रमाण इस लेख के दायरे से बाहर है। जिस एप्लिकेशन पर हम विचार कर रहे हैं — Number Theoretic Transform — उसके लिए हमें केवल एक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी की आवश्यकता है, जिसे Fundamental Theorem का उपयोग करके पाया जा सकता है, यह मानते हुए कि हम $\mathbb{F}_q^*$ के लिए एक जेनरेटर जानते हैं।

इस अध्याय के शेष भाग में, हम उदाहरण प्रस्तुत करेंगे जो दिखाएंगे कि एक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी, और फिर किसी दिए गए $k$ के लिए सभी $k$ -th रूट्स ऑफ यूनिटी खोजने के लिए Fundamental Theorem का उपयोग कैसे करें।

$\mathbb{F}_{17}^*$ में 4th रूट्स ऑफ यूनिटी का उदाहरण

मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_{17}^*$ का एक जेनरेटर एलिमेंट $3$ है, जिसे galois लाइब्रेरी का उपयोग करके पाया जा सकता है।

4 ऑर्डर के सबग्रुप के लिए एक जेनरेटर तब $\omega = 3^{\frac{16}{4}} = 3^4 \equiv 13$ है।

हमारी चर्चा के आधार पर, यह जेनरेटर एक प्रिमिटिव 4th रूट ऑफ यूनिटी है। आइए एक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी की परिभाषा का उपयोग करके इसकी जाँच करें। हमें यह दिखाना होगा कि:

एलिमेंट $13$ , 4th रूट ऑफ यूनिटी है। इसे यह जाँच कर देखा जा सकता है कि $13^4 \equiv 1 \pmod{17}$ है।
एलिमेंट $13$ का ऑर्डर 4 है। इसका अर्थ है कि 4 सबसे छोटा धनात्मक पूर्णांक $r$ है जिससे $13^r \equiv 1 \pmod{17}$ हो। आइए इसे नीचे जाँचें:

\begin{aligned} &13^1 = 13,\\ &13^2 \equiv 16,&&\pmod{17}\\ &13^3 \equiv 13 \cdot 16 \equiv 4,\\ &\boxed{13^4 \equiv 16 \cdot 16\equiv -1 \cdot -1 \equiv 1}. \end{aligned}

इसलिए, एलिमेंट $13$ एक प्रिमिटिव 4th रूट ऑफ यूनिटी है, और हम सभी 4th रूट्स ऑफ यूनिटी का सबग्रुप जेनरेट करने के लिए एलिमेंट $13$ का उपयोग कर सकते हैं, निम्नानुसार:

\begin{aligned} \langle\omega\rangle &= \{ \omega^0, \omega^1, \omega^2, \omega^3, \omega^4\}\\ &= \{13^0, 13^1, 13^2, 13^3\}\\ &=\{1, 13, 16, 4\}. \end{aligned}

$\mathbb{F}_{17}^*$ में 8th रूट्स ऑफ यूनिटी का उदाहरण

चूँकि $g =3$ मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_{17}^*$ का एक जेनरेटर है, $8$ ऑर्डर के सबग्रुप के लिए एक जेनरेटर $\omega = 3^{\frac{16}{8}} = 3^2 \equiv 9$ है।

आइए जाँचें कि यह एक प्रिमिटिव 8th रूट ऑफ यूनिटी भी है। हमें यह जाँचना होगा कि:

एलिमेंट $9$ , 8th रूट ऑफ यूनिटी है। इसे यह जाँच कर देखा जा सकता है कि $9^8 \equiv 1 \pmod{17}$ है।
एलिमेंट $9$ का ऑर्डर 8 है। इसका अर्थ है कि 8 सबसे छोटा धनात्मक पूर्णांक $r$ है जिससे $9^r \equiv 1 \pmod{17}$ हो। आइए इसे नीचे जाँचें:

\begin{aligned} &9^1 = 9,\\ &9^2 \equiv 13,\\ &9^3 \equiv 9 \cdot 13 \equiv 15,\\ &9^4 \equiv 13 \cdot 13 \equiv (-4) \cdot (-4)\equiv 16,\qquad\pmod{17}\\ &9^5 \equiv 9 \cdot 16 \equiv 8,\\ &9^6 \equiv 9 \cdot 8 \equiv 4,\\ &9^7 \equiv 9 \cdot 4 \equiv 2,\\ &\boxed{9^8 \equiv 9 \cdot 2 = 18\equiv 1}. \end{aligned}

इसलिए, एलिमेंट $9$ एक प्रिमिटिव 8th रूट ऑफ यूनिटी है, और हम सभी 8th रूट्स ऑफ यूनिटी का सबग्रुप जेनरेट करने के लिए एलिमेंट $9$ का उपयोग कर सकते हैं, निम्नानुसार:

\begin{aligned} \langle\omega\rangle &= \{ \omega^0, \omega^1, \omega^2, \omega^3, \omega^4, \omega^5, \omega^6, \omega^7\}\\ &= \{9^0, 9^1, 9^2, 9^3, 9^4, 9^5, 9^6, 9^7\}\\ &=\{1, 9, 13, 15, 16, 8, 4, 2\}. \end{aligned}

अभ्यास. $\mathbb{F}_{17}^*$ में एक प्रिमिटिव 2nd रूट ऑफ यूनिटी और सभी 2nd रूट्स ऑफ यूनिटी का सबग्रुप खोजें।

निष्कर्ष और सारांश

सभी $k$ -th रूट्स ऑफ यूनिटी को खोजने के लिए एक कुशल विधि की आवश्यकता होती है, जिसका अध्ययन हमने इस लेख में किया। संक्षेप में, हमने स्थापित किया कि:

एक फाइनाइट फील्ड $\mathbb{F}_q$ का एलिमेंट $a$ , $k$ -th रूट ऑफ यूनिटी है यदि $a^k \equiv 1$ हो।
यदि $k$ , $q-1$ को विभाजित करता है, तो $\mathbb{F}_q^*$ का सबग्रुप जिसमें सभी $k$ -th रूट्स ऑफ यूनिटी शामिल हैं, Fundamental Theorem of Cyclic Groups द्वारा गारंटीकृत $k$ ऑर्डर का अद्वितीय सबग्रुप है।
एक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी सभी $k$ -th रूट्स ऑफ यूनिटी का सबग्रुप जेनरेट करता है। यदि $g$ मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_q^*$ का एक जेनरेटर है और $k$ , $q-1$ को विभाजित करता है, तो एलिमेंट $\omega = g^{\frac{q-1}{k}}$ एक प्रिमिटिव $k$ -th रूट ऑफ यूनिटी है।

परिशिष्ट A (Appendix A)

$k$ ऑर्डर के सबग्रुप का जेनरेटर $\omega$ संतुष्ट करता है: $\omega^k \equiv 1$

मान लें कि $g$ मल्टीप्लिकेटिव ग्रुप $\mathbb{F}_q^*$ का एक जेनरेटर है। Fundamental Theorem of Cyclic Groups से याद करें कि एलिमेंट $\omega = g^{\frac{q-1}{k}}$ , $k$ ऑर्डर के अद्वितीय सबग्रुप को जेनरेट करता है। हमारा उद्देश्य यह साबित करना है कि $\omega^k \equiv 1$ ।

प्रमाण. Fermat’s Little Theorem यह बताता है कि यदि $q$ एक अभाज्य संख्या (prime number) है, तो किसी भी पूर्णांक $g$ के लिए:

g^{q}\equiv g\pmod{q}.

उदाहरण के लिए, यदि $g = 2$ और $q=7$ , तो $2^7\equiv 2\pmod{7}$ ।

यदि $g$ , $q$ द्वारा विभाज्य नहीं है, तो हम उपरोक्त समीकरण के दोनों पक्षों को $g$ से विभाजित कर सकते हैं। यह दर्शाता है कि Fermat’s Little Theorem इस कथन के समतुल्य है:

g^{q-1}\equiv 1\pmod{q}.

अब हम $\omega^k$ की गणना निम्नानुसार करते हैं:

\begin{aligned} \omega^k &= (g^{\frac{q-1}{k}})^k &&\qquad\text{By definition of $\omega$}\\ &= g^{q-1} &&\qquad\text{Simplifying the exponent}\\ &\equiv 1\pmod{q}&&\qquad\text{Applying Fermat's Little Theorem} \end{aligned}

परिशिष्ट B (Appendix B)

यदि $a\in\mathbb{F}_q^*$ और $a^k\equiv1$ तो $a$ , $k$ ऑर्डर के एक अद्वितीय साइक्लिक सबग्रुप का सदस्य है।

मान लें कि $g$ , $\mathbb{F}_q^*$ का एक जेनरेटर है। इसका समतुल्य रूप से अर्थ है कि $g$ एक $(q-1)$ -th रूट ऑफ यूनिटी है।

मान लें कि $\omega=g^\frac{q-1}{k}$ , $k$ ऑर्डर के मल्टीप्लिकेटिव सबग्रुप के लिए एक जेनरेटर है ( $\omega=g^\frac{q-1}{k}$ सीधे तौर पर Fundamental Theorem of Cyclic Groups से आता है)।

यदि $a\in\mathbb{F}_q^*$ और $a^k\equiv1$ तो हमें यह साबित करना होगा कि एक ऐसा पूर्णांक $s$ मौजूद है जिससे $\omega^s=a$ हो। $\omega^s\equiv a$ में पूर्णांक $s$ का अस्तित्व यह साबित करता है कि $a$ को $\omega$ द्वारा जेनरेट किया जा सकता है और इस प्रकार यह $k$ ऑर्डर के अद्वितीय सबग्रुप का हिस्सा है।

ऐसा $s$ खोजने के लिए, हम $\omega$ को $g^\frac{q-1}{k}$ और $a$ को $g^m$ से प्रतिस्थापित (substitute) करेंगे ताकि $\omega^s=a$ को इसमें बदला जा सके:

{\left(g^\frac{q-1}{k}\right)}^s\stackrel{?}{=}g^m

क्या हम कोई ऐसा $s$ लेकर आ सकते हैं जो समीकरण को सत्य बनाता हो? यदि हम रणनीतिक रूप से ऐसा $s$ चुनते हैं जिससे घातांक $\frac{q-1}{k}$ रद्द हो जाए और $m$ बच जाए तो हमारे पास है:

s=\frac{mk}{q-1}

$s=\frac{mk}{q-1}$ को इस समीकरण ${\left(g^\frac{q-1}{k}\right)}^s\stackrel{?}{=}g^m$ के बाएँ पक्ष में रखने पर, हमें प्राप्त होता है

{\left(g^\frac{q-1}{k}\right)}^{(\frac{mk}{q-1})}

हम देख सकते हैं कि $q-1$ और $k$ पद रद्द (cancel) हो जाते हैं, जिससे हमारे पास $g^m$ बचता है।

g^{\frac{\cancel{q-1}}{\cancel{k}}\frac{m\cancel{k}}{\cancel{q-1}}}\implies g^m

हम $g^\frac{q-1}{k}=\omega$ , $\frac{mk}{q-1}=s$ , और $g^m=a$ की मूल परिभाषाओं को वापस रख सकते हैं और देख सकते हैं कि

\omega^s=a

इसलिए, यदि $a^k\equiv1$ है, तो वास्तव में एक ऐसा $s$ मौजूद है जिससे $\omega^s=a$ हो। $s$ केवल यह है

s=\frac{mk}{q-1}

जहाँ $m$ , $g^m=a$ का हल है, $k$ सबग्रुप का ऑर्डर है, और $q$ हमारे फाइनाइट फील्ड का मोडुलो है।

हालाँकि, हमें अभी भी यह साबित करना होगा कि $s$ एक पूर्णांक है क्योंकि $\omega$ को किसी भिन्न (fraction) की घात तक बढ़ाकर कोई मान जेनरेट करना $\omega$ द्वारा जेनरेट किए गए सबग्रुप का सदस्य होने के योग्य नहीं है।

यह दिखाना कि $s$ एक पूर्णांक है

यह दिखाने के लिए कि $\frac{mk}{q-1}$ एक पूर्णांक है, हमें यह दिखाना होगा कि $mk$ को $q-1$ से विभाजित करने पर कोई शेषफल (remainder) नहीं बचता है।

जब हम विभाजन करते हैं, तो हमें एक भागफल (quotient) $n$ और एक शेषफल $r$ मिलना चाहिए। हम यह दिखाना चाहते हैं कि $r$ अनिवार्य रूप से 0 है।

\frac{mk}{q-1}=n+r

एक शेषफल भाजक (divisor) से बड़ा नहीं हो सकता (उदा., $\frac{11}{5}$ का शेषफल 5 या उससे बड़ा नहीं हो सकता), इसलिए हमारे पास यह शर्त भी है कि:

0\leq r\lt q-1

हम $\frac{mk}{(q-1)}=n+r$ में $mk$ को अलग (isolate) कर सकते हैं, इसे भाज्य / भाजक = भागफल + शेषफल (dividend / divisor = quotient + remainder) के रूप से भाज्य = भागफल⋅भाजक + शेषफल (dividend = quotient⋅divisor + remainder) में बदलकर। (इस पुनर्लेखन को स्पष्ट करने के लिए, विचार करें कि 6/4=1 शेषफल 2 को 6 = 4⋅1 + 2 के रूप में लिखा जा सकता है)। पुन: लिखे गए रूप में, हमारे पास है:

mk = n\cdot(q-1) + r\qquad\text{where $0\le r < q-1$}

यह दिखाने के लिए कि $r=0$ है, हम कुछ समय के लिए $mk=n\cdot(q-1)+r$ को एक तरफ रख देंगे, और $mk$ का एक और गुण प्राप्त करेंगे।

तथ्य: $g^{mk}\equiv1$

$g^{mk}\equiv1$ को निम्नलिखित तथ्यों से प्राप्त किया जा सकता है:

$a^k\equiv1$
$a=g^m$

तो प्रतिस्थापन (substitution) द्वारा, $(g^m)^k\equiv1$ और घात की घात के नियम द्वारा, $g^{mk}\equiv1$ ।

$mk = n\cdot(q-1) + r$ को $g^{mk}\equiv1$ में प्रतिस्थापित करें

अब हमारे पास यह दिखाने के लिए पर्याप्त उपकरण हैं कि $mk = n\cdot(q-1) + r$ में शेषफल $r$ शून्य है। हम पाठक को याद दिलाते हैं कि $g^{q-1}\equiv1$ है चूँकि $g$ एक प्रिमिटिव $(q-1)$ -th रूट ऑफ यूनिटी है।

अब हम दिखाते हैं कि इन परिभाषाओं का उपयोग करना

$g^{mk}\equiv1$
$mk = n\cdot(q-1) + r$
$g^{q-1}\equiv1$

यह दिखाने के लिए पर्याप्त हैं कि $g^{mk}\equiv g^r$ :

\begin{aligned} g^{mk} &= g^{n\cdot (q-1) + r}&&\qquad\text{Substitution}\\ &= g^{n\cdot(q-1)}\cdot g^r&&\qquad\text{Power multiplication rule}\\ &= (g^{q-1})^n\cdot g^r&&\qquad\text{Power of a power rule}\\ &\equiv 1\cdot g^r&&\qquad\text{Because $g^{q-1}\equiv 1$}\\ &= g^r \end{aligned}

$g^{mk}\equiv g^r$ और $g^{mk}\equiv 1$ के परिणामस्वरूप, हमारे पास यह है कि

g^r\equiv1

चूँकि $g$ एक प्रिमिटिव $(q-1)$ -th रूट ऑफ यूनिटी है, $r$ के लिए केवल दो समाधान हैं:

$r=0$
$r\equiv q-1$

याद करें कि $r$ को इसके समाधान के रूप में परिभाषित किया गया है

\frac{mk}{q-1}=n+r\qquad\text{where $0\le r < q-1$}

हम जानते हैं कि कोई भी वैध विभाजन $\frac{mk}{q-1}$ $q-1$ या उससे अधिक के शेषफल $r$ का परिणाम नहीं दे सकता, विशेष रूप से, शेषफल $0\le r \lt q-1$ की सीमा में होना चाहिए। शेषफल पर वह सीमा प्रतिबंध दर्शाता है कि $r\neq q-1$ है।

तो इस संभावना को खारिज करते हुए कि $r=q-1$ , $g^r\equiv1$ के लिए एकमात्र समाधान $r=0$ है (यानी $g^0\equiv1$ )।

चूँकि $r=0$ , $mk$ को $q-1$ से विभाजित करने का परिणाम एक पूर्णांक है।

अंत में, चूँकि $s$ को इस रूप में परिभाषित किया गया है

s=\frac{mk}{q-1}

$s$ एक पूर्णांक है।