इकाई के k-वें मूल का वर्ग इकाई का k/2-वाँ मूल होता है

Last updated on Nov 12, 2025

यदि हम इकाई के $k$ -वें मूलों (जहाँ $k$ सम है) का समुच्चय (set) लें और प्रत्येक अवयव (element) का वर्ग (square) करें, तो परिणामी समुच्चय का आकार आधा होगा। नया समुच्चय इकाई के $\frac{k}{2}$ -वें मूलों का होगा।

उदाहरण के लिए, मान लें कि $k = 6$ है। इकाई के 6-वें मूल होंगे:

\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5}

यदि हम प्रत्येक अवयव का वर्ग करते हैं, तो हमें निम्नलिखित समुच्चय मिलता है। कुछ अवयवों के घातांक (exponents) $k$ के बराबर या उससे अधिक हैं, लेकिन हम इसे अगले चरण में संभालेंगे।

\set{1^2,\omega^2,\omega^4,\omega^6,\omega^8,\omega^{10}}

फिर हम घातांकों का गुणनखंड इस प्रकार कर सकते हैं:

\set{1^2,\omega^2,\omega^4,\omega^6,(\omega^6)\omega^2,(\omega^{6})\omega^4}

चूंकि $\omega$ इकाई का 6-वां मूल है, $\omega^6\equiv1$ है, इसलिए हमारे पास है:

\set{1^2,\omega^2,\omega^4,1,(1)\omega^2,(1)(\omega^4)}

$1$ से गुणा को हटाने पर, हमें मिलता है:

\set{1^2,\omega^2,\omega^4,1,\omega^2,\omega^4}

अब सभी डुप्लिकेट (duplicate) पदों को एकल अवयव से बदलें:

\set{1,\omega^2,\omega^4}

नए समुच्चय का आकार मूल से आधा है, और प्रत्येक अवयव इकाई का 3-रा मूल है:

$1^3\equiv1$
$(\omega^2)^3=\omega^6\equiv1$
$(\omega^4)^3=\omega^{12}=\omega^6\omega^6\equiv1\cdot1=1$

यदि हम इकाई के 6-वें मूलों को एक वृत्त पर आलेखित करते हैं, तो हम देख सकते हैं कि वर्ग करने पर हर दूसरा अवयव “हटा” दिया जाता है। हमने $\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5}$ से शुरुआत की थी और $\set{1,\omega^2,\omega^4}$ पर समाप्त किया।

दोहराने के लिए, यदि हम इकाई के $k$ -वें मूलों का समुच्चय लेते हैं, और $k$ सम (even) है, फिर प्रत्येक अवयव का वर्ग करते हैं, तो हमें आधे आकार का एक समुच्चय मिलता है जिसमें प्रत्येक अवयव इकाई का $\frac{k}{2}$ -वां मूल होता है।

कुछ और उदाहरण:

यदि $k = 10$ है और हम इकाई के 10-वें मूलों में से प्रत्येक का वर्ग करते हैं, तो हमें पांच आकार का एक समुच्चय मिलता है जो इकाई के पांचवें मूल हैं।
यदि $k = 8$ है और हम इकाई के 8-वें मूलों में से प्रत्येक का वर्ग करते हैं, तो हमें चार आकार का एक समुच्चय मिलता है जो इकाई के चौथे मूल हैं।
यदि $k = 4$ है और हम इकाई के 4-वें मूलों में से प्रत्येक का वर्ग करते हैं, तो हमें दो आकार का एक समुच्चय मिलता है जो इकाई के दूसरे मूल हैं।
यदि $k = 2$ है और हम इकाई के 2-रे मूलों में से प्रत्येक का वर्ग करते हैं, तो हमें 1 आकार का एक समुच्चय मिलता है जो केवल अवयव 1 है।

अंतिम बिंदु को आसानी से दर्शाया जा सकता है। इकाई के दूसरे मूल 1 के वर्गमूल होते हैं, जो हमेशा $\set{1,-1}\equiv\set{1,\omega^{k/2}}$ होते हैं। 1 का वर्ग करने पर 1 प्राप्त होता है और -1 का वर्ग करने पर भी 1 प्राप्त होता है। समतुल्य रूप से (Equivalently), $(\omega^{k/2})^2=\omega^k\equiv1$ होता है।

इकाई के 8-वें मूलों का वर्ग करने का उदाहरण

परिमित क्षेत्र (finite field) $\mathbb{F}_{17}$ में इकाई के 8वें मूलों के उपसमूह (subgroup) $\langle 9\rangle = \{1, 9, 13, 15, 16, 8, 4, 2\}$ पर विचार करें। हम इस उपसमूह के सभी अवयवों का वर्ग इस प्रकार करते हैं:

\begin{aligned} &1^2 = 1\pmod{17},\\ &9^2 \equiv 13\pmod{17},\\ &13^2 \equiv 16\pmod{17} ,\\ &15^2 \equiv 4\pmod{17},\\ &16^2 \equiv 1\pmod{17},\\ &8^2 \equiv 13\pmod{17},\\ &4^2 \equiv 16\pmod{17},\\ &2^2 = 4\pmod{17}. \end{aligned}

वर्ग करने के बाद प्राप्त समुच्चय $\{1,13,16,4\}$ है, जो कि ठीक इकाई के चौथे मूलों का उपसमूह है।

यहाँ वर्ग करने से पहले और बाद में इकाई के मूलों का एक दृश्य (visualization) दिया गया है। हमने $\set{1, 9, 13, 15, 16, 8, 4, 2}$ समुच्चय के साथ शुरुआत की थी और $\set{1,13,16,4}$ समुच्चय पर समाप्त किया।

k सम होना चाहिए

यदि $k$ विषम (odd) है, तो “समूह का आधा” जैसी कोई चीज़ नहीं होती क्योंकि विषम आकार के समुच्चय को दो में विभाजित नहीं किया जा सकता है। NTT के उद्देश्यों के लिए, हम केवल सम आकार वाले $k$ से निपटते हैं, इसलिए हम उस स्थिति में रुचि नहीं रखते जहाँ $k$ विषम हो।

इस दावे का प्रमाण कि नया समुच्चय आधे आकार का है

मान लें कि $\omega$ इकाई का एक प्रिमिटिव (primitive) $k$ -वां मूल है जहाँ $k$ सम है। मान लें कि $\langle\omega\rangle$ , कोटि (order) $k$ के $\omega$ द्वारा जनित उपसमूह है। हम दावा करते हैं कि $|\set{\omega^2|\omega\in\langle\omega\rangle}|=k/2$ है।

यह प्रमाण वास्तव में काफी सरल और सहज है।

हमने पिछले अध्याय में स्थापित किया था कि $\omega^{i}$ और $\omega^{i+k/2}$ योज्य प्रतिलोम (additive inverses) हैं। चूँकि $k$ सम है, हम समूह को दो समुच्चयों में विभाजित कर सकते हैं, पहला $0...(k/2-1)$ है और दूसरा $k/2...k-1$ है:

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{\omega^{k/2},\omega^{k/2+1},\omega^{k/2+2},...}

वे अवयव निम्नलिखित प्रतिनिधित्व के सर्वांगसम (congruent) हैं:

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{-\omega^0,-\omega^1,-\omega^2,...}

यदि हम दोनों समुच्चयों पर $f(x)=x^2$ लागू करते हैं, तो हमें समान सामग्री और $k/2$ आकार के दो समुच्चय मिलते हैं:

\set{1,\omega^2,\omega^4,...}\quad\set{1,\omega^2,\omega^4,...}

चूँकि दोनों समुच्चय समान हैं, दोनों समुच्चयों का संघ (union) समान आकार का होगा, जो कि $k/2$ है।

इस बात का प्रमाण कि इकाई के $k$ -वें मूल का वर्ग करने पर इकाई का $k/2$ -वां मूल प्राप्त होता है

मान लीजिए कि $a$ इकाई का एक $k$ -वां मूल है। हमारा उद्देश्य यह दिखाना है कि $a^2$ इकाई का एक $\frac{k}{2}$ -वां मूल है, अर्थात:

(a^2)^{\frac{k}{2}}\equiv 1

आइए $(a^2)^{\frac{k}{2}}$ को सरल करें:

(a^2)^{\frac{k}{2}} = a^{k}

चूंकि $a^k\equiv1$ (क्योंकि $a$ इकाई का $k$ -वां मूल है), इसलिए यह निष्कर्ष निकलता है कि $(a^2)^{\frac{k}{2}}\equiv 1$ है।

अतः, $a^2$ वास्तव में इकाई का एक $\frac{k}{2}$ -वां मूल है।