Finite groups: subgroups, generators और Lagrange theorem
उद्देश्य और पूर्वज्ञान
पहले पाठ के identity, inverse और elementary order examples से आगे बढ़कर subgroup tests, cyclic generators, element orders तथा Lagrange का coset-आधारित प्रमाण सीखेंगे। साथ में उसके गलत converses के counterexamples देखेंगे। Ambient group का operation पहले से associative है; subgroup में वही operation प्रयोग होता है। Lagrange के सभी उपयोग finite groups पर हैं। Multiplicative identity e और additive identity 0 लिखेंगे।
1. दिए गए group के भीतर subgroup
H⊆G को subgroup, H≤G, कहते हैं यदि inherited operation में H स्वयं group हो। उपयोगी test: H nonempty हो और हर a,b∈H के लिए ab⁻¹∈H।
Sufficiency का प्रमाण: h∈H चुनें; hh⁻¹=e∈H। फिर b∈H पर eb⁻¹=b⁻¹∈H। अब a,b⁻¹ पर test लगाकर a(b⁻¹)⁻¹=ab∈H। Associativity G से मिलती है, इसलिए सभी group axioms पूरे। Necessity subgroup की closure और inverses से सीधी है। Additive notation में test a−b∈H बनता है।
Z₁₂ में addition modulo 12 के तहत H={0,4,8} subgroup है: 4 के multiples का अंतर modulo 12 फिर उसी set में है। K={0,2,4} subgroup नहीं: 4+2=6∉K। K का size 3, 12 को divide करता है, पर यह arithmetic तथ्य उस खास subset को subgroup नहीं बनाता।
Group के finite nonempty subset के लिए multiplication closure अकेली पर्याप्त है। h की powers repeat होंगी: hⁱ=hʲ, i<j; इसलिए hʲ⁻ⁱ=e और positive powers से inverse भी मिलेगा। h=e हो तो inverse स्वयं e है। Closure इन powers को H में रखती है। Infinite subset में shortcut गलत: (Z,+) के भीतर positive integers addition में closed हैं, पर identity और additive inverses नहीं। दोनों tests में nonempty होना आवश्यक है।
2. Cyclic subgroup और element order
⟨g⟩={gᵏ:k∈Z}, g से generated subgroup है। Powers के product में exponents जुड़ते और inverse में sign बदलता है; इससे subgroup test पूरा होता है। Finite group में powers repeat होंगी, इसलिए कोई positive power e होगी। सबसे छोटा ऐसा positive exponent ord(g)=m है। तब e,g,…,gᵐ⁻¹ distinct हैं और हर power modulo m reduce होती है; अतः |⟨g⟩|=m।
gᵗ=e ठीक तब होता है जब m, t को divide करे। t≥0 के लिए t=qm+r, 0≤r<m लिखें। gᵗ=gʳ; यदि यह e है तो m की minimality से r=0। Negative exponents में inverses से यही निष्कर्ष। इसलिए identity देने वाला कोई भी exponent order नहीं; सबसे छोटा positive exponent चाहिए।
Additive Zₙ में residue k का order n/gcd(n,k) है। सबसे छोटा t>0 चाहिए जिसके लिए tk≡0 mod n। n=d n′, k=d k′, gcd(n′,k′)=1 लिखने पर n|tk iff n′|t। न्यूनतम t=n′। इसलिए k पूरे Zₙ का generator iff gcd(n,k)=1।
Z₁₂ में 5 की यात्रा 0,5,10,3,8,1,6,11,4,9,2,7 और फिर 0 है। Order 12 है। सभी generators {1,5,7,11} हैं। 8 का order 12/gcd(12,8)=3 और generated subgroup {0,8,4} है। Zₙ के generators की संख्या φ(n) है, जहाँ φ, n से coprime residues गिनता है; actual generators निकालने के लिए gcd test करें।
यदि ord(g)=m, तो ord(gᵏ)=m/gcd(m,k); वही divisibility argument m|kt पर लगाएँ। Order n के cyclic group में हर subgroup cyclic है। हर positive divisor d|n के लिए ठीक एक subgroup order d का है: ⟨gⁿ⁄ᵈ⟩। प्रमाण में सबसे छोटा positive r लें जिसके लिए gʳ∈H; H={e} में r=n मान सकते हैं। Division with remainder से H में represented हर exponent, r का multiple है। gⁿ=e∈H से r|n और H=⟨gʳ⟩। यह अतिरिक्त existence तथा uniqueness cyclic groups के लिए है, arbitrary groups के लिए नहीं।
3. Cosets से Lagrange theorem
H≤G और a∈G के लिए left coset aH={ah:h∈H}। Map h↦ah bijective है, inverse x↦a⁻¹x है; इसलिए |aH|=|H|। दो cosets disjoint या समान होते हैं। यदि ah₁=bh₂ तो b⁻¹a=h₂h₁⁻¹∈H। इससे aH का हर element bH में लिखा जा सकता है और उलटा भी। e∈H से a∈aH, इसलिए cosets पूरे G को समान-size blocks में partition करते हैं।
यदि k blocks हों और G finite हो, |G|=k|H|। अतः |H|, |G| को divide करता है। k=[G:H] index है। कहीं commutativity नहीं मानी गई। Z₁₂ में H={0,4,8} के additive cosets {0,4,8}, {1,5,9}, {2,6,10}, {3,7,11} हैं। Size तीन के चार blocks सभी बारह residues देते हैं। Coset जरूरी नहीं subgroup हो: {1,5,9} में identity 0 नहीं।
⟨g⟩ पर theorem लगाने से ord(g)||G| तथा g^|G|=e मिलता है। Prime order p का group cyclic है: g≠e चुनें; उसका order p को divide करता और 1 नहीं है, इसलिए p है और वह सब elements generate करता है। Composite group size में divisibility केवल संभावनाएँ सीमित करती है।
4. दो गलत converses के सटीक counterexamples
पहला: |G| का हर divisor element order नहीं बनता। V=Z₂×Z₂ में coordinatewise addition लें। Elements (0,0),(1,0),(0,1),(1,1) हैं। हर nonidentity element स्वयं से जुड़कर (0,0) देता है, इसलिए तीनों का order 2 है। 4, |V|=4 को divide करता है, पर order 4 का element नहीं। V abelian है पर cyclic नहीं। इसमें order 4 का subgroup स्वयं V मौजूद है; इसलिए यह उदाहरण अकेले subgroup-existence converse नहीं खारिज करता।
दूसरा: arbitrary finite group के size के हर divisor पर subgroup होना जरूरी नहीं। A₄, चार symbols के even permutations का composition group, size 12 का है पर order 6 का subgroup नहीं। आवश्यक विवरण सहित छोटा प्रमाण देखें। Elements हैं identity, आठ 3-cycles (चार में से तीन symbols चुनें और दो cyclic orientations में एक लें), तथा दो disjoint transpositions के तीन products: कुल 12। हर 3-cycle का order 3 है।
यदि |H|=6 हो तो दो left cosets होंगी। किसी g से left multiplication इन दो cosets को permute करता है: xH↦gxH। 3-cycle के लिए इस permutation को तीन बार लगाने पर identity मिलती है, क्योंकि g³=e। दो objects के permutations केवल “दोनों स्थिर” और “swap” हैं। Swap का cube फिर swap है, identity नहीं; इसलिए g दोनों cosets स्थिर रखता है। खासकर gH=H, जिससे g∈H। अतः H में सभी आठ 3-cycles और identity, यानी कम-से-कम नौ elements होंगे, |H|=6 के विरुद्ध। इसलिए 6|12 आवश्यक arithmetic होने पर भी subgroup existence की पर्याप्त शर्त नहीं। यह cyclic groups के मजबूत परिणाम का विरोध नहीं करता।
जाँच और गलतियाँ
Order निकालने से पहले operation लिखें; addition और multiplication की identities अलग हैं। Subgroup के लिए inherited operation तथा actual elements जाँचें, केवल size नहीं। Subgroup तथा coset, group size तथा element order, और “order divides n” तथा “हर divisor का order मिलता है” में अंतर रखें। Cyclic group abelian होता है क्योंकि powers commute करती हैं; abelian group cyclic होना आवश्यक नहीं, जैसा V दिखाता है। Lagrange necessary condition और उसके consequences देता है, हर प्रस्तावित subgroup की existence नहीं।
मौलिक अभ्यास: छह एकल-सही-विकल्प MCQs
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में केवल एक सही विकल्प चुनें।
GR01. Additive Z₁₂ का कौन सा subset subgroup है?
A. {0,2,4} B. {0,4,8} C. {1,5,9} D. ∅
उत्तर: B
A: 4+2=6 अनुपस्थित है; closure fail।
B: यह modulo 12 में 4 के multiples हैं, differences में closed।
C: यह coset है जिसमें additive identity 0 नहीं।
D: Subgroup में identity चाहिए; वह खाली नहीं हो सकता।
GR02. Additive Z₁₂ में residue 8 का order क्या है?
A. 8 B. 4 C. 12 D. 3
उत्तर: D
A: Element का label उसका order नहीं।
B: gcd(12,8)=4 है, पर order 12 को gcd से भाग देने पर है।
C: Group size 12 है, पर 8 केवल तीन elements generate करता है।
D: Positive multiples 8,4,0 हैं; पहली वापसी तीन बार में।
GR03. Additive Z₁₀ के सभी generators का set कौन सा है?
A. {1,3,7,9} B. {1,2,3,4,5,6,7,8,9} C. {2,4,6,8} D. {1,9}
उत्तर: A
A: ठीक ये residues 10 से coprime हैं और order 10 रखते हैं।
B: Nonzero होने से coprime नहीं; 2 तथा 5 generators नहीं।
C: Even residues का 10 से gcd कम-से-कम 2 है; odd residues generate नहीं होंगे।
D: 3 तथा 7 भी 10 से coprime हैं; सूची अधूरी।
GR04. Finite group में 18 elements हैं। Lagrange theorem से कौन सा element order असंभव है?
A. 1 B. 3 C. 6 D. 8
उत्तर: D
A: Identity का order हमेशा 1 है।
B: 3, 18 को divide करता है; Lagrange इसे exclude नहीं करता।
C: 6, 18 को divide करता है; theorem इसे exclude नहीं करता, केवल divisibility occurrence नहीं कहती।
D: 8, 18 को divide नहीं करता; generated cyclic subgroup का size divide करना चाहिए।
GR05. यदि ord(g)=12 है, तो ord(g⁸) क्या है?
A. 4 B. 3 C. 8 D. 12
उत्तर: B
A: 4 gcd है; order देने वाला quotient नहीं।
B: 12|8t का न्यूनतम positive t=3; अर्थात 12/gcd(12,8)=3।
C: Power exponent 8 नए element का order नहीं।
D: gcd(12,8)≠1, इसलिए g⁸ proper subgroup generate करता है।
GR06. कौन सा कथन Lagrange theorem की सीमा सही बताता है?
A. |G| का हर divisor element order है। B. जिस subset का size |G| को divide करे वह subgroup है। C. Subgroup orders, |G| को divide करते हैं, पर arbitrary group में हर divisor subgroup order के रूप में होना आवश्यक नहीं। D. हर finite abelian group cyclic है।
उत्तर: C
A: Z₂×Z₂ का size 4 है पर order 4 का element नहीं।
B: Z₁₂ में {0,2,4} का size 3 है पर closure नहीं।
C: Coset partition divisibility सिद्ध करता है; size 12 के A₄ में order 6 का subgroup नहीं।
D: Z₂×Z₂ abelian है पर पूरे चार elements का generator नहीं।
स्रोत और दायरा
यह सीमित विस्तार GATE 2026 CS syllabus के Section 1 में relations, lattices या groups की गहराई बढ़ाता है। यह संपूर्ण Discrete Mathematics coverage का दावा नहीं है। परिभाषाएँ, उदाहरण, प्रमाण और अभ्यास मौलिक प्रस्तुति हैं।
Official GATE 2026 CS syllabus, Section 1
स्रोत जाँचा गया: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन