Introduction

यह अध्याय subgroups (उपसमूहों) और generators (जनकों) के बारे में विस्तार से बताकर ग्रुप थ्योरी (group theory) के हमारे अध्ययन को आगे बढ़ाता है। अंत में एक primitive element की अवधारणा को प्रस्तुत किया जाएगा। हम यह मानकर चलते हैं कि आप पहले से ही एक ग्रुप (group) की परिभाषा से परिचित हैं। यदि आपको इसे फिर से समझने की आवश्यकता है, तो this article देखें।

समझ विकसित करने के लिए, हम additive groups से शुरुआत करते हैं, जो सीधे और सरल होते हैं तथा subgroups और generators जैसी मुख्य अवधारणाओं को स्पष्ट करने में मदद करते हैं।

इसके बाद हम multiplicative groups of integers modulo $n$ की ओर बढ़ते हैं। गुणा (multiplication) के अंतर्गत, पूर्णांक (integers) स्वयं एक ग्रुप नहीं बनाते हैं—$\mathbb{Z}$ में केवल $1$ और $-1$ के मल्टीप्लिकेटिव इन्वर्स (multiplicative inverses) होते हैं, इसलिए ग्रुप के नियम विफल हो जाते हैं। इसे हल करने के लिए, हम $n$ से छोटे उन पूर्णांकों पर ध्यान केंद्रित करते हुए मॉड्यूलो $n$ (modulo $n$) गुणा पर विचार करते हैं जो इसके coprime (सह-अभाज्य) हैं। इन coprime पूर्णांकों के मॉड्यूलो $n$ मल्टीप्लिकेटिव इन्वर्स होते हैं, और ये मिलकर एक अच्छी तरह से परिभाषित ग्रुप बनाते हैं। यह संरचना नंबर थ्योरी (number theory) में केंद्रीय भूमिका निभाती है और कई क्रिप्टोग्राफ़िक सिस्टम (cryptographic systems) का आधार है।

Coprime: दो संख्याएँ coprime होती हैं यदि उनका महत्तम समापवर्तक (Greatest Common Divisor - GCD) 1 हो।

Example 1: 8 और 15 coprime हैं क्योंकि
8 के गुणनखंड (Factors): 1, 2, 4, 8
15 के गुणनखंड: 1, 3, 5, 15
सामान्य गुणनखंड (Common factor): 1
gcd 1 है।

Example 2: 12 और 18 coprime नहीं हैं क्योंकि
12 के गुणनखंड: 1, 2, 3, 4, 6, 12
18 के गुणनखंड: 1, 2, 3, 6, 9, 18
सामान्य गुणनखंड: 1, 2, 3, 6
gcd 6 है।

अंत में, हम generators का परीक्षण करते हैं—ऐसे एलिमेंट्स जो बार-बार गुणा करने के माध्यम से एक संपूर्ण ग्रुप या subgroup का निर्माण कर सकते हैं। generators को समझने से महत्वपूर्ण subgroup संरचनाओं का पता चलता है, विशेष रूप से जब $n$ अभाज्य (prime) हो, और यह क्रिप्टोग्राफ़िक अनुप्रयोगों (cryptographic applications) में उनकी महत्वपूर्ण भूमिका को उजागर करता है।

1. Additive Groups

एडिटिव ग्रुप्स में ऑपरेशन के रूप में जोड़ (अक्सर किसी संख्या के मॉड्यूलो) का उपयोग किया जाता है, जिसमें आइडेंटिटी एलिमेंट $0$ होता है और किसी एलिमेंट $a$ का इन्वर्स $-a$ होता है, जिससे इनकी संरचना अपेक्षाकृत सरल हो जाती है। आइए उदाहरणों के माध्यम से समझें कि वे कैसे काम करते हैं।

1.1 Example: $(\mathbb{Z}_6, +)$

शुरुआत करने के लिए, जोड़ (addition) के अंतर्गत $\mathbb{Z}_6 = \{0, 1, 2, 3, 4, 5\}$ पर विचार करें। closure के साथ शुरू करें:

प्रत्येक परिणाम $\{0, 1, 2, 3, 4, 5\}$ में है, इसलिए closure लागू होता है। अन्य गुणों की जाँच करें:

• Associativity: ग्रुपिंग (Grouping) से परिणाम नहीं बदलता है:
  • $(2 + 3) + 4 = 5 + 4 = 9 \equiv 3 \pmod{6}$,
  • $2 + (3 + 4) = 2 + (7 \equiv 1) = 3$.
• Identity: $0$ आइडेंटिटी एलिमेंट के रूप में काम करता है, क्योंकि $3 + 0 = 3$ (टेबल की पहली पंक्ति या कॉलम देखें)।
• Inverses: प्रत्येक एलिमेंट का एक जोड़ा होता है जिसका योग $0 \pmod{6}$ होता है:

इस प्रकार, $(\mathbb{Z}_6, +)$ एक ग्रुप है जिसका order (सेट में एलिमेंट्स की संख्या) $|\mathbb{Z}_6| = 6$ है।

Exercise 1.1: जाँच करें कि क्या $(\mathbb{Z}_{9}, +)$ एक ग्रुप है।

Hint: $\mathbb{Z}_6$ की तरह ही एडिशन टेबल बनाने का प्रयास करें।

इसे हाथ से करना थोड़ा थकाऊ हो सकता है, इसलिए यहाँ एक Python स्क्रिप्ट दी गई है जो किसी भी $\mathbb{Z}_n$ के लिए पूर्ण एडिशन टेबल जनरेट करेगी:

Copy

def print_addition_table(mod):
    header = ["+ mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))
    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row + col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))


# Try it with Z_9
print_addition_table(9)

Follow-up: $\mathbb{Z}_9$ का विश्लेषण करने के बाद, $\mathbb{Z}_{10}$ के लिए टेबल जनरेट करने का प्रयास करें। क्या आप निर्धारित कर सकते हैं कि $(\mathbb{Z}_{10}, +)$ भी एक ग्रुप है?

इस प्रकार, $(\mathbb{Z}_n, +)$, $n$ order वाला एक ग्रुप है। इस तरह के फाइनाइट ग्रुप्स (Finite groups) मॉड्यूलर अरिथमेटिक (modular arithmetic) और क्रिप्टोग्राफ़ी में महत्वपूर्ण हैं। इसके बाद, हम अपना ध्यान इस ओर मोड़ते हैं कि किसी ग्रुप के भीतर कुछ विशेष एलिमेंट्स और सबसेट्स (subsets) कैसे गहरी संरचना को प्रकट कर सकते हैं—subgroups और generators के माध्यम से।

2. Subgroups और Generators

2.1 Subgroups को समझना

ग्रुप्स का अध्ययन करते समय, हमारा सामना अक्सर ऐसे सबसेट्स (subsets) से होता है जो समान ऑपरेशन के अंतर्गत ग्रुप की संरचना को बनाए रखते हैं। ये विशेष सबसेट्स, जिन्हें subgroups कहा जाता है, मूल ग्रुप के छोटे संस्करणों की तरह व्यवहार करते हैं। हालाँकि, हर सबसेट इसके योग्य नहीं होता है—आइए उदाहरणों के साथ इसे समझें कि क्या चीज़ एक subgroup बनाती है।

Example 2.1.1: Subgroups in $(\mathbb{Z}, +)$

जोड़ के अंतर्गत सभी पूर्णांकों के ग्रुप $(\mathbb{Z}, +)$, और दो परिचित सबसेट्स पर विचार करें:

• सम पूर्णांकों (even integers) का सेट: $\{\ldots, -4, -2, 0, 2, 4, \ldots\}$
• विषम पूर्णांकों (odd integers) का सेट: $\{\ldots, -3, -1, 1, 3, 5, \ldots\}$

आइए सम पूर्णांकों की जाँच करें:

• Closure: दो सम संख्याओं का योग सम होता है (उदाहरण के लिए, $-2 +4= 2$).
• Identity: $0$ सम है और इसमें शामिल है।
• Inverses: किसी भी सम संख्या का इन्वर्स भी सम होता है (उदाहरण के लिए, $2$ का इन्वर्स $-2$ है)।
• Associativity: $\mathbb{Z}$ से प्राप्त होती है (Inherited)।

सम पूर्णांक ग्रुप के सभी गुणों को संतुष्ट करते हैं—यह एक मान्य subgroup है।

अब विषम पूर्णांकों की जाँच करें:

• Closure: $1 + 3= 4$, जो कि सम है—सेट का हिस्सा नहीं है। इसलिए closure विफल हो जाता है।
• Identity: $0$ विषम नहीं है, इसलिए आइडेंटिटी एलिमेंट गायब है।
• Inverses: $1$ के लिए, $-1$ विषम है—लेकिन चूँकि closure और identity पहले ही विफल हो चुके हैं, इसलिए यह एक subgroup नहीं है।

जोड़ के अंतर्गत विषम पूर्णांक subgroup मानदंडों को पूरा नहीं करते हैं—वे केवल एक सबसेट हैं, subgroup नहीं।

Example 2.1.2: Subgroups in $(\mathbb{Z}_8, +)$

अब $(\mathbb{Z}_8, +) = \{0, 1, 2, 3, 4, 5, 6, 7\}$ लें और दो सबसेट्स का परीक्षण करें:

• Evens modulo 8: $\{0, 2, 4, 6\}$
• First half: $\{0, 1, 2, 3\}$

$\{0, 2, 4, 6\}$ के लिए:

• Closure: $2 +4= 6$, $4 +6= 10 \equiv2\pmod{8}$ (दोनों सेट में हैं)।
• Identity: $0$ मौजूद है।
• Inverses: $2 +6= 8 \equiv 0$, $4 +4= 8 \equiv 0$, $0 + 0 = 0$ (सभी जोड़े काम करते हैं)।
• Associativity: $\mathbb{Z}_8$ से लागू होती है।

यह एक subgroup है!

$\{0, 1, 2, 3\}$ के लिए:

• Closure: $2+3= 5$ (सेट में नहीं है)।
• Identity: $0$ मौजूद है।
• Inverses: $1$ के लिए, $\{0, 1, 2, 3\}$ में कोई भी एलिमेंट $0$ नहीं देता है (उदाहरण के लिए, $1 +3=4\pmod{8}$)।

यह एक ग्रुप होने में विफल रहता है, इसलिए यह केवल एक सबसेट है, subgroup नहीं।

Definition: किसी ग्रुप $G$ का सबसेट $H$ एक subgroup होता है यदि वह उसी ऑपरेशन के अंतर्गत एक ग्रुप हो, जिसका अर्थ है कि यह closure को संतुष्ट करता है, इसमें identity शामिल है, इसके सभी एलिमेंट्स के लिए inverses हैं, और यह $G$ से associativity प्राप्त करता है।

Exercise 2.1.1: $(\mathbb{Z}_{5}, +)$ के सभी subgroups खोजें।

2.2 Additive Groups में Generators

अब जब हमने subgroups को देख लिया है, तो आइए जानें कि कैसे सिंगल एलिमेंट्स उन्हें—या यहाँ तक कि पूरे ग्रुप को—जनरेट कर सकते हैं। हम $(\mathbb{Z}_6, +) = \{0, 1, 2, 3, 4, 5\}$ पर फिर से विचार करेंगे, जो मॉड्यूलो $6$ एडिशन के अंतर्गत एडिटिव ग्रुप है, और जाँच करेंगे कि क्या होता है जब हम किसी एलिमेंट को बार-बार उसी में जोड़ते हैं, जैसे कि मॉड्यूलो $6$ संख्याओं के चारों ओर “घूमना”।

Example 2.2.1: Generators in $(\mathbb{Z}_6, +)$

Try 1:

• $1$
• $1 + 1 = 2$
• $2 + 1 = 3$
• $3 + 1 = 4$
• $4 + 1 = 5$
• $5 + 1 = 6 \equiv 0 \pmod{6}$

यह $\{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$ देता है। बार-बार $1$ जोड़ने से संपूर्ण ग्रुप में चक्र (cycle) चलता है।

Try 2:

• $2$
• $2 + 2 = 4$
• $4 + 2 = 6 \equiv 0 \pmod{6}$
• $0 + 2 = 2$

यह $\{0, 2, 4\}$ देता है—केवल आधा ग्रुप।

Try 3:

• $3$
• $3 + 3 = 6 \equiv 0 \pmod{6}$
• $0 + 3 = 3$

यह $\{0, 3\}$ देता है, और भी छोटा!

Try 5:

• $5$
• $5 + 5 = 10 \equiv 4 \pmod{6}$
• $4 + 5 = 9 \equiv 3 \pmod{6}$
• $3 + 5 = 8 \equiv 2 \pmod{6}$
• $2 + 5 = 7 \equiv 1 \pmod{6}$
• $1 + 5 = 6 \equiv 0 \pmod{6}$

यह $\{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$ देता है, जो $1$ की तरह ही सब कुछ कवर करता है।

Exercise 2.2.1: $(\mathbb{Z}_9, +)$ में, कौन से एलिमेंट्स संपूर्ण $\mathbb{Z}_9$ जनरेट करते हैं? कौन से एलिमेंट्स proper subgroups जनरेट करते हैं?

2.2.2 Subgroups Generated by Elements

अब बाइनरी ऑपरेशन (जैसे जोड़ या गुणा) वाले किसी भी ग्रुप $G$ पर विचार करें, और मान लें कि $g$, $G$ का एक एलिमेंट है। ग्रुप ऑपरेशन को $g$ पर बार-बार लागू करके, हम इसके द्वारा जनरेट किए गए एलिमेंट्स का सेट बना सकते हैं। इस सेट को $\langle g \rangle$ से दर्शाया जाता है और इसे $g$ द्वारा जनरेट किया गया cyclic subgroup कहा जाता है।

उदाहरण के लिए additive groups में:

कई एलिमेंट्स के लिए, $\langle g \rangle$ एक proper subgroup होता है। लेकिन जब $\langle g \rangle = G$ होता है, तो हम कहते हैं कि $g$, $G$ का एक generator है, और $G$ एक cyclic group है।
जैसा कि Example 2.2.1 में दिखाया गया है, हमने मॉड्यूलो 6 एडिशन के अंतर्गत $(\mathbb{Z}_6, +) = \{0, 1, 2, 3, 4, 5\}$ में एलिमेंट्स द्वारा जनरेट किए गए subgroups की गणना की। प्रत्येक एलिमेंट द्वारा जनरेट किए गए subgroups इस प्रकार हैं:

• $\langle 0 \rangle = \{0\}$ (proper subgroup)
• $\langle 1 \rangle = \{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$
• $\langle 2 \rangle = \{0, 2, 4\}$ (proper subgroup)
• $\langle 3 \rangle = \{0, 3\}$ (proper subgroup)
• $\langle 4 \rangle = \{0, 4, 2\}$ (proper subgroup)
• $\langle 5 \rangle = \{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$

एलिमेंट्स $1$ और $5$ संपूर्ण ग्रुप $\mathbb{Z}_6$ जनरेट करते हैं, जिससे वे generators बन जाते हैं, जबकि $0$, $2$, $3$, और $4$ proper subgroups जनरेट करते हैं।

Example 2.2.3: Generators in $(\mathbb{Z}_5, +)$

अब मॉड्यूलो 5 एडिशन के अंतर्गत $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ का परीक्षण करें:

• $\langle1\rangle = \{0, 1, 2, 3, 4\}=\mathbb{Z}_5$
• $\langle2\rangle =\{2, 4, 6 \equiv 1 \pmod 5 , 8 \equiv 3 \pmod 5\} =\{1,2,3,4\}=\mathbb{Z}_5$
• $\langle3\rangle= \{3, 6 \equiv 1 \pmod 5, 9 \equiv 4\pmod 5 , 7 \equiv 2\pmod 5 \}=\{1,2,3,4\}=\mathbb{Z}_5$
• $\langle4\rangle =\{4, 8 \equiv 3 \pmod 5, 12 \equiv 2\pmod 5 , 16 \equiv 1\pmod 5 \}=\{1,2,3,4\}=\mathbb{Z}_5$

प्रत्येक गैर-शून्य (non-zero) एलिमेंट एक generator है।

ऐसा इसलिए होता है क्योंकि सभी $g \neq 0$ के लिए $\gcd(g, 5) = 1$ है, और $5$ अभाज्य (prime) है।

Conclusion: $(\mathbb{Z}_n, +)$ में, एक एलिमेंट $g$ संपूर्ण ग्रुप को तभी जनरेट करता है जब $\gcd(g, n) = 1$ हो। अभाज्य $n$ के लिए, सभी गैर-शून्य एलिमेंट्स generators होते हैं। भाज्य (composite) $n$ के लिए, केवल कुछ ही एलिमेंट्स योग्य होते हैं।

2.3 Code: $(\mathbb{Z}_n, +)$ में Additive Generators की खोज

Copy
def additive_closure(a, n):
    """Generates {0, a, 2a, 3a, ...} mod n until it repeats."""
    result = []
    current = 0
    while current not in result:
        result.append(current)
        current = (current + a) % n
    return sorted(result)  # Sorted for readability

# Show generated sets in (Z_6 , +)
print("Z_6:")
for a in range(6):
    print(f"Generated by {a}: {additive_closure(a, 6)}")

# Show generated sets in (Z_5, +)
print("\nZ_5:")
for a in range(5):
    print(f"Generated by {a}: {additive_closure(a, 5)}")

Output:

Copy
(Z_6, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4, 5]
Generated by 2: [0, 2, 4]
Generated by 3: [0, 3]
Generated by 4: [0, 2, 4]
Generated by 5: [0, 1, 2, 3, 4, 5]

(Z_5, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4]
Generated by 2: [0, 1, 2, 3, 4]
Generated by 3: [0, 1, 2, 3, 4]
Generated by 4: [0, 1, 2, 3, 4]

एडिटिव ग्रुप्स (additive groups) की खोज करने के बाद, अब हम उनके मल्टीप्लिकेटिव समकक्षों (multiplicative counterparts) की ओर मुड़ते हैं।

3. Multiplicative Groups

मल्टीप्लिकेटिव ग्रुप्स गुणा (अक्सर किसी संख्या के मॉड्यूलो) के अंतर्गत काम करते हैं, जिसमें आइडेंटिटी एलिमेंट $1$ होता है, हालांकि इन्वर्सेस ढूँढना थोड़ा जटिल हो सकता है, विशेष रूप से फाइनाइट सेटिंग्स में। इसे स्पष्ट करने के लिए, हम मॉड्यूलो $7$ गुणा का उपयोग करके एक ठोस उदाहरण की जाँच करेंगे।

3.1 Example:

$\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$ पर विचार करें:

• Closure लागू होता है, उदा., $2 \times5= 10 \equiv 3$, सेट में है।
• Identity: आइडेंटिटी एलिमेंट $1$ है, लेकिन यह $0$ के लिए विफल रहता है, जिसका कोई इन्वर्स नहीं है;
• Inverses: प्रत्येक गैर-शून्य एलिमेंट का एक इन्वर्स होता है:
  • $1 \times1= 1$
  • $2 \times4= 8 \equiv1\pmod{7}$
  • $3 \times5= 15 \equiv1\pmod{7}$
  • $4 \times2= 8 \equiv1\pmod{7}$
  • $5 \times3= 15 \equiv1\pmod{7}$
  • $6 \times6= 36 \equiv1\pmod{7}$

चूँकि $0$ का कोई इन्वर्स नहीं है, इसलिए $(\mathbb{Z}_7, \times)$ एक ग्रुप नहीं है। लेकिन यदि हम $0$ को हटा दें और केवल गैर-शून्य एलिमेंट्स पर विचार करें — अर्थात, $\mathbb{Z}_7 \setminus \{0\} = \{1, 2, 3, 4, 5, 6\}$ — तो हमें गुणा के अंतर्गत एक ग्रुप मिल जाता है। इस सेट को अक्सर $\mathbb{Z}_7^*$ से दर्शाया जाता है और यह 6 आर्डर का एक ग्रुप है।

आप किसी भी मॉड्यूलो $n$ के लिए गुणन तालिका (multiplication table) जनरेट करने के लिए इस कोड का उपयोग कर सकते हैं:

Copy
def print_multiplication_table(mod):
    header = ["× mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))

    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row * col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))

print_multiplication_table(5)

3.2 Example: $(\mathbb{Z}_6\setminus \{0\}, \times)$, एक ग्रुप नहीं है

आइए अब गुणा mod 6 के अंतर्गत सेट $\{1, 2, 3, 4, 5\}$ का परीक्षण करें।

अब हमारे पास एक अधिक बुनियादी समस्या है: कुछ गुणाओं का परिणाम 0 होता है जो सेट का हिस्सा नहीं है। इसलिए, यह सेट और बाइनरी ऑपरेटर क्लोज्ड (closed) नहीं है, इसलिए यह एक ग्रुप नहीं है।

3.3 Example: $(\mathbb{Z}_8\setminus\{0\}, \times)$

एक अन्य उदाहरण के रूप में, आइए अब $\mathbb{Z}_8\setminus\{0\} = \{1, 2, 3, 4, 5, 6, 7\}$ में गुणा पर विचार करें:

केवल वे एलिमेंट्स $\{1, 3, 5, 7\}$—जो 8 के साथ coprime हैं—में मॉड्यूलो 8 मल्टीप्लिकेटिव इन्वर्स होते हैं:

• $1 \times1= 1 \pmod 8$
• $3 \times3= 9 \equiv 1 \pmod 8$
• $5 \times5= 25 \equiv 1 \pmod 8$
• $7 \times7= 49 \equiv 1 \pmod 8$

शेष एलिमेंट्स, $\{2, 4, 6\}$, सभी 8 के साथ एक सामान्य गुणनखंड (common factor) साझा करते हैं और इसलिए उनके इन्वर्स नहीं होते हैं। इस प्रकार, $\mathbb{Z}_8 \setminus \{0\}$ गुणा के अंतर्गत एक ग्रुप नहीं है।

3.4. $\mathbb{Z}_n^*$ क्या है?

सेट $\mathbb{Z}_n^*$ को औपचारिक रूप से इस प्रकार परिभाषित किया गया है:

अर्थात, $\mathbb{Z}_n^*$ में $\mathbb{Z}_n$ के वे सभी एलिमेंट्स शामिल हैं जिनका एक मल्टीप्लिकेटिव इन्वर्स मॉड्यूलो $n$ होता है।

• जब $n$ अभाज्य (prime) हो, तो प्रत्येक गैर-शून्य एलिमेंट इन्वर्टिबल (invertible) होता है, इसलिए:
  

  $$\mathbb{Z}_n^* = \mathbb{Z}_n \setminus \{0\}$$

• जब $n$ भाज्य (composite) हो, तो केवल $n$ के coprime एलिमेंट्स ही इन्वर्टिबल होते हैं। उदाहरण के लिए:

  • $\mathbb{Z}_6^* = \{1, 5\}$
  • $\mathbb{Z}_8^* = \{1, 3, 5, 7\}$

दोनों मामलों में, $\mathbb{Z}_n^*$ गुणा के अंतर्गत एक ग्रुप बनाता है। हालाँकि, पूर्ण सेट $\mathbb{Z}_n \setminus \{0\}$ हमेशा एक ग्रुप नहीं बनाता है—जब तक कि $n$ अभाज्य न हो।

इससे पहले, हमने यह दर्शाने के लिए $\mathbb{Z}_n \setminus \{0\}$ का उपयोग किया था कि जब $n$ भाज्य होता है तो इन्वर्सेस की अनुपस्थिति (और zero divisors की उपस्थिति) ग्रुप संरचना को क्यों तोड़ देती है। यह अंतर केवल तकनीकी होने से कहीं अधिक है: यह मॉड्यूलर अरिथमेटिक, क्रिप्टोग्राफ़िक एल्गोरिदम और नंबर थ्योरी को समझने में केंद्रीय भूमिका निभाता है।

अगले भाग में, हम यह जानेंगे कि $n$ के अभाज्य होने पर $\mathbb{Z}_n^*$ की संरचना कैसे बदलती है।

3.5 Prime Moduli क्यों काम करते हैं

ये विफलताएँ prime moduli को प्रेरित करती हैं। $\{1,2,\ldots, p-1\}$ में, जहाँ $p$ अभाज्य है, प्रत्येक एलिमेंट का एक इन्वर्स होता है। वास्तव में, यह नंबर थ्योरी के एक क्लासिक परिणाम द्वारा गारंटीकृत है।

मॉड्यूलो $n$ के लिए $\{1, 2, \ldots, n-1\}$ के पैटर्न पर विचार करें:

• यदि $n$ अभाज्य नहीं है, तो यह zero divisors और गायब इन्वर्सेस के कारण एक ग्रुप नहीं है (उदाहरण के लिए, $n = 6, 8$)।
• यदि $n$ अभाज्य है, तो यह एक ग्रुप है।

3.6 Inverse की गणना के लिए Python कोड

मॉड्यूलर इन्वर्सेस की गणना करने के लिए सबसे सरल और सबसे कुशल तरीकों में से एक Python के अंतर्निहित
pow(a, -1, p) का उपयोग करना है। पर्दे के पीछे, यह नंबर थ्योरी के एक प्रसिद्ध परिणाम के कारण काम करता है जिसे Fermat’s Little Theorem कहा जाता है, जो गारंटी देता है कि एक इन्वर्स मौजूद है और हमें बताता है:

जब मॉड्यूलो $p$ एक अभाज्य संख्या है और $a$, $p$ से विभाज्य नहीं है।

यहाँ एक उदाहरण है:

Copy
def mod_inverse(a, p):  
    return pow(a, -1, p)

# Test for Z_7^*
def test_inverses(p):
    print(f"Testing inverses modulo {p}:")
    for a in range(1, p):
        inv = mod_inverse(a, p)
        print(f"Inverse of {a} mod {p} is {inv} (check: {a} * {inv} = {a * inv % p})")

if __name__ == "__main__":
    p = 7
    test_inverses(p)

Output:

Copy
Testing inverses modulo 7:
Inverse of 1 mod 7 is 1 (check: 1 * 1 = 1)
Inverse of 2 mod 7 is 4 (check: 2 * 4 = 1)
Inverse of 3 mod 7 is 5 (check: 3 * 5 = 1)
Inverse of 4 mod 7 is 2 (check: 4 * 2 = 1)
Inverse of 5 mod 7 is 3 (check: 5 * 3 = 1)
Inverse of 6 mod 7 is 6 (check: 6 * 6 = 1)

3.7 Exercises

Math Exercises:

1. Python के pow(a, -1, n) फ़ंक्शन या कैलकुलेटर का उपयोग करके निम्नलिखित के लिए मॉड्यूलर इन्वर्स (यदि यह मौजूद है) खोजें। Prime moduli के लिए, आप वैकल्पिक रूप से Fermat’s Little Theorem का उपयोग कर सकते हैं:

   • $3^{-1} \mod 11$
   • $7^{-1} \mod 26$
   • $4^{-1} \mod 15$

2. $\mathbb{Z}_{12}^*$ में $a$ के किन मानों के लिए मॉड्यूलर इन्वर्स मौजूद है?

Coding Exercises:

1. एक फ़ंक्शन list_all_inverses(n) लिखें जो $\mathbb{Z}_n^*$ के सभी एलिमेंट्स का उनके इन्वर्सेस (यदि वे मौजूद हैं) के साथ एक डिक्शनरी (dictionary) लौटाता है।

2. एक प्रोग्राम लिखें जो यूजर इनपुट a और n लेता है, और जाँच करता है कि क्या कोई मॉड्यूलर इन्वर्स मौजूद है। यदि यह मौजूद है, तो इन्वर्स प्रिंट करें। इसे अलग-अलग मानों के साथ आज़माएँ और देखें कि आप क्या खोजते हैं।

3. Challenge: कुछ छोटे primes p चुनें, और एक प्रोग्राम लिखें जो यह जाँचता हो कि क्या
   {1, 2, ..., p - 1} में सभी a के लिए pow(a, p - 1, p) == 1 है।
   क्या यह प्रत्येक a के लिए सही है? यदि p अभाज्य (prime) नहीं है तो क्या होता है?

4. Multiplicative Groups में Generators

अब हम अपना ध्यान multiplicative groups में generators की ओर मोड़ते हैं। समझ विकसित करने के लिए, हम $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}$ में ठोस उदाहरणों से शुरू करते हैं, यह पता लगाते हुए कि कैसे अलग-अलग एलिमेंट्स बार-बार गुणा करके पूर्ण ग्रुप—या इसके सिर्फ एक हिस्से—को जनरेट कर सकते हैं।

Example 4.1: $(\mathbb{Z}_7^*, \times)$

Try 3:

• $3^1 = 3$
• $3^2 = 9 \equiv 2 \pmod{7}$
• $3^3 = 27 \equiv 6 \pmod{7}$
• $3^4 = 81 \equiv 4 \pmod{7}$
• $3^5 = 243 \equiv 5 \pmod{7}$
• $3^6 = 729 \equiv 1 \pmod{7}$

$\langle 3 \rangle = \{1, 2, 3, 4, 5, 6\} = \mathbb{Z}_7^*$। एलिमेंट $3$ एक generator है।

Try 2:

• $2^1 = 2$
• $2^2 = 4$
• $2^3 = 8 \equiv 1 \pmod{7}$

$\langle 2 \rangle = \{1, 2, 4\}$, एक subgroup, पूर्ण ग्रुप नहीं।

Try Other Elements:

• $4$: $4, 16 \equiv 2, 8 \equiv 1$ $\Rightarrow \{1, 2, 4\}$
• $5$: $5, 25 \equiv 4, 20 \equiv 6, 30 \equiv 2, 10 \equiv 3, 15 \equiv 1$ $\Rightarrow \mathbb{Z}_7^*$
• $6$: $6, 36 \equiv 1$ $\Rightarrow \{1, 6\}$

Summary:

4.1 Primitive Elements

जैसा कि हम देखते हैं, एडिटिव ग्रुप $(\mathbb{Z}_p, +)$ में, जहाँ $p$ अभाज्य है, प्रत्येक गैर-शून्य एलिमेंट के एक generator होने की गारंटी है। यानी, किसी भी गैर-शून्य एलिमेंट को बार-बार जोड़ने पर अंततः ग्रुप के सभी एलिमेंट्स का चक्र (cycle) पूरा हो जाएगा। हालाँकि, मल्टीप्लिकेटिव ग्रुप्स $(\mathbb{Z}_p^*, \times)$ में, केवल कुछ ही एलिमेंट्स generators होते हैं—इन्हें primitive elements कहा जाता है। यह विषमता एक मूलभूत अंतर को उजागर करती है: primes पर एडिटिव ग्रुप्स हमेशा cyclic होते हैं जिनमें सभी गैर-शून्य एलिमेंट्स generators होते हैं, जबकि primes पर मल्टीप्लिकेटिव ग्रुप्स cyclic तो होते हैं लेकिन उनमें एलिमेंट्स का केवल एक सबसेट (subset) ही होता है जो generators के रूप में काम करता है।

Definition: एक एलिमेंट $g \in \mathbb{Z}_p^*$ एक primitive element है यदि

$$\langle g \rangle = \{g^1, g^2, \ldots, g^{p-1}\} \pmod{p} = \mathbb{Z}_p^*.$$

उदाहरण के लिए, $\mathbb{Z}_7^*$ लें: $3$ और $5$ primitive elements हैं, जबकि $2$, $4$, और $6$ नहीं हैं।

नंबर थ्योरी में एक foundational result इस बात की गारंटी देता है कि किसी भी अभाज्य $p$ के लिए, ग्रुप $\mathbb{Z}_p^*$ cyclic होता है, जिसका अर्थ है कि इसमें हमेशा कम से कम एक primitive element शामिल होता है। यह एडिटिव ग्रुप $(\mathbb{Z}_p, +)$ के विपरीत है, जहाँ प्रत्येक गैर-शून्य एलिमेंट संपूर्ण ग्रुप जनरेट करता है।

Example 4.1.1: $\mathbb{Z}_5^* = \{1, 2, 3, 4\}$

• Element 2:
  

  $$\begin{align*} 2^1 &= 2 \pmod{5}, \\ 2^2 &= 4 \pmod{5}, \\ 2^3 &= 8 \equiv 3 \pmod{5}, \\ 2^4 &= 16 \equiv 1 \pmod{5} \end{align*}$$
  
  $\langle 2 \rangle = \{1, 2, 3, 4\} = \mathbb{Z}_5^*$, इसलिए $2$ एक primitive element है।

• Element 3:
  

  $$\begin{align*} 3^1 &= 3 \pmod{5}, \\ 3^2 &= 9 \equiv 4 \pmod{5}, \\ 3^3 &= 27 \equiv 2 \pmod{5}, \\ 3^4 &= 81 \equiv 1 \pmod{5} \end{align*}$$
  
  $\langle 3 \rangle = \{1, 2, 3, 4\} = \mathbb{Z}_5^*$, इसलिए $3$ भी एक primitive element है।

Example 4.1.2: $\mathbb{Z}_{11}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$

• Element 2:
  

  $$\begin{align*} 2^1 &= 2 \pmod{11}, \\ 2^2 &= 4 \pmod{11}, \\ 2^3 &= 8 \pmod{11}, \\ 2^4 &= 16 \equiv 5 \pmod{11}, \\ 2^5 &= 10 \pmod{11}, \\ 2^6 &= 20 \equiv 9 \pmod{11}, \\ 2^7 &= 18 \equiv 7 \pmod{11}, \\ 2^8 &= 14 \equiv 3 \pmod{11}, \\ 2^9 &= 6 \pmod{11}, \\ 2^{10} &= 12 \equiv 1 \pmod{11} \end{align*}$$
  
  $\langle 2 \rangle = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} = \mathbb{Z}_{11}^*$, इसलिए $2$ एक primitive element है।

• Element 3:
  

  $$\begin{align*} 3^1 &= 3 \pmod{11}, \\ 3^2 &= 9 \pmod{11}, \\ 3^3 &= 27 \equiv 5 \pmod{11}, \\ 3^4 &= 15 \equiv 4 \pmod{11}, \\ 3^5 &= 12 \equiv 1 \pmod{11} \end{align*}$$
  
  $\langle 3 \rangle = \{1, 3, 4, 5, 9\}$, एक subgroup, पूर्ण ग्रुप नहीं।

Example 4.1.3: $\mathbb{Z}_{17}^*$

• Element 3:
  

  $$\begin{align*} 3^1 &= 3 \pmod{17}, \\ 3^2 &= 9 \pmod{17}, \\ 3^3 &= 27 \equiv 10 \pmod{17}, \\ 3^4 &= 81 \equiv 13 \pmod{17}, \\ 3^5 &= 243 \equiv 5 \pmod{17}, \\ 3^6 &= 729 \equiv 15 \pmod{17}, \\ 3^7 &= 2187 \equiv 11 \pmod{17}, \\ 3^8 &= 6561 \equiv 16 \pmod{17}, \\ 3^9 &= 19683 \equiv 14 \pmod{17}, \\ 3^{10} &= 59049 \equiv 8 \pmod{17}, \\ 3^{11} &= 177147 \equiv 7 \pmod{17}, \\ 3^{12} &= 531441 \equiv 4 \pmod{17}, \\ 3^{13} &= 1594323 \equiv 12 \pmod{17}, \\ 3^{14} &= 4782969 \equiv 2 \pmod{17}, \\ 3^{15} &= 14348907 \equiv 6 \pmod{17}, \\ 3^{16} &= 43046721 \equiv 1 \pmod{17} \end{align*}$$

  $\langle 3 \rangle = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\} = \mathbb{Z}_{17}^*$, आर्डर $16$ (पूर्ण ग्रुप)। अतः, $3$, $\mathbb{Z}_{17}^*$ का एक primitive element है।