Finite groups: subgroups, generators and Lagrange’s theorem

Finite groups: subgroups, generators and Lagrange's theorem

Objectives and prerequisite

Build on the existing identity/inverse and elementary order examples. Test subgroups, compute cyclic generators and element orders efficiently, prove Lagrange's divisibility statement by cosets, and reject its false converses. A group operation is already known to be associative; subgroups use that same operation. All applications of Lagrange here are to finite groups. We write e for a multiplicative identity and 0 for an additive identity.

1. A subgroup is a group inside the given group

A subset H⊆G is a subgroup, written H≤G, when it is itself a group under the inherited operation. The reliable subgroup test is: H is nonempty and ab⁻¹∈H for every a,b∈H.

Proof of sufficiency: choose h∈H; hh⁻¹=e∈H. Then for b∈H, eb⁻¹=b⁻¹∈H. For a,b∈H, apply the test to a and b⁻¹ to obtain a(b⁻¹)⁻¹=ab∈H. Associativity is inherited from G, so the group axioms hold. Necessity follows from closure and inverses in any subgroup. In additive notation the test is a−b∈H.

In Z₁₂ under addition modulo 12, H={0,4,8} is a subgroup: differences of multiples of 4 remain multiples of 4 modulo 12. The subset K={0,2,4} is not: 4+2=6∉K. Its size 3 divides 12, but that arithmetic fact does not make this particular subset a subgroup.

For a finite nonempty subset of a group, closure under multiplication alone suffices: powers of h repeat, so hⁱ=hʲ for some i<j, yielding hʲ⁻ⁱ=e; positive powers then supply an inverse (if h=e, its inverse is e). Closure puts these powers in H. This shortcut fails for infinite subsets: positive integers inside (Z,+) are closed under addition but contain neither identity nor additive inverses. Nonemptiness is essential in either test.

2. Cyclic subgroups and element order

The subgroup generated by g is ⟨g⟩={gᵏ:k∈Z}. Multiplying powers adds exponents and inversion negates them, proving it is a subgroup. In a finite group, powers must repeat, so some positive power is e. The smallest such positive exponent is ord(g)=m. Then e,g,…,gᵐ⁻¹ are distinct, and every power reduces modulo m; hence |⟨g⟩|=m.

Moreover gᵗ=e exactly when m divides t. For t≥0, divide t=qm+r, 0≤r<m. Then gᵗ=gʳ; minimality of m forces r=0 if this equals e. Negative exponents follow by inverses. Thus order is a least positive exponent, not any exponent giving identity.

In additive Zₙ, the order of residue k is n/gcd(n,k): the smallest positive t with tk≡0 mod n. Write n=d n′ and k=d k′ with gcd(n′,k′)=1. Then n|tk iff n′|t, whose smallest positive solution is n′. Residue k generates Zₙ exactly when gcd(n,k)=1.

For Z₁₂, generator 5 visits 0,5,10,3,8,1,6,11,4,9,2,7 and then 0. Its order is 12. The complete generator list is {1,5,7,11}; residue 8 instead has order 12/gcd(12,8)=3 and generates {0,8,4}. There are φ(n) generators of Zₙ, where φ counts residues coprime to n; the gcd test, not memorizing φ, finds the actual generators.

More generally if ord(g)=m, then ord(gᵏ)=m/gcd(m,k), by the same divisibility argument applied to m|kt. In a cyclic group of order n every subgroup is cyclic, and for each positive divisor d of n there is exactly one subgroup of order d, namely ⟨gⁿ⁄ᵈ⟩. To see the subgroup form, choose the least positive exponent r with gʳ∈H (allow r=n for H={e}); division with remainder shows every exponent represented in H is divisible by r. Since gⁿ=e∈H, r|n and H=⟨gʳ⟩. This extra existence/uniqueness belongs to cyclic groups, not arbitrary groups.

3. Cosets explain Lagrange's theorem

For H≤G and a∈G, its left coset is aH={ah:h∈H}. The map h↦ah is bijective, with inverse x↦a⁻¹x, so |aH|=|H|. Two cosets are disjoint or equal: if ah₁=bh₂, then b⁻¹a=h₂h₁⁻¹∈H, which lets every element of aH be written in bH and conversely. Each element a lies in aH because e∈H. Therefore left cosets partition G into equally sized blocks.

If there are k blocks and G is finite, |G|=k|H|. Thus |H| divides |G|; k=[G:H] is the index. No commutativity assumption is used. In Z₁₂ with H={0,4,8}, the additive cosets are {0,4,8}, {1,5,9}, {2,6,10}, {3,7,11}. Four blocks of size three account for all twelve residues. A coset need not be a subgroup: {1,5,9} omits identity 0.

Apply Lagrange to ⟨g⟩ to obtain ord(g)||G| and therefore g^|G|=e. A group of prime order p is cyclic: choose g≠e; its order divides p and is not 1, so it is p and generates all elements. For a composite group size, divisibility only lists possibilities.

4. Two false converses, two precise counterexamples

First, a divisor of |G| need not be an element order. In V=Z₂×Z₂ under coordinatewise addition, the four elements are (0,0),(1,0),(0,1),(1,1). Every nonidentity element added to itself gives (0,0), so all three have order 2. Although 4 divides |V|=4, no element has order 4; V is abelian but not cyclic. It does have a subgroup of order 4, namely itself, so this example alone does not disprove the subgroup-existence converse.

Second, an arbitrary finite group need not have a subgroup for every divisor of its size. A₄, the even permutations of four symbols under composition, has order 12 but no subgroup of order 6. Here is a short proof, including the needed structure. Its elements are identity, eight 3-cycles (choose three of four symbols and one of two cyclic orientations), and three products of two disjoint transpositions, totaling 12. Each 3-cycle has order 3.

If H had size 6, it would have two left cosets. Left multiplication by any element g permutes those two cosets: xH maps to gxH. For a 3-cycle, applying this permutation three times is the identity because g³=e. The only permutations of two objects are “fix both” and “swap”; a swap cubed is still a swap, so g must fix both. In particular gH=H, which implies g∈H. Hence H would contain all eight 3-cycles and identity, at least nine elements, contradicting |H|=6. Thus 6|12 is necessary arithmetic but insufficient for subgroup existence. This does not contradict the stronger result proved for cyclic groups.

Checklist and common traps

Write the operation before computing orders; repeated addition and multiplication have different identities. For subgroups, check the inherited operation and actual elements, not just cardinality. Distinguish a subgroup from its coset, a group's size from an element's order, and “order divides n” from “every divisor occurs.” A cyclic group is abelian because powers commute; an abelian group need not be cyclic, as V shows. Lagrange proves a necessary condition and strong consequences, but not the general existence of every proposed subgroup.

Original practice: six single-correct MCQs

These are original questions, not previous-year questions. Choose exactly one option.

GR01. Which subset is a subgroup of additive Z₁₂?

A. {0,2,4} B. {0,4,8} C. {1,5,9} D. ∅

Answer: B

A: 4+2=6 is missing, so closure fails.

B: It is the set of multiples of 4 modulo 12, closed under differences.

C: This is a coset without additive identity 0.

D: A subgroup must contain an identity and cannot be empty.

GR02. What is the order of residue 8 in additive Z₁₂?

A. 8 B. 4 C. 12 D. 3

Answer: D

A: The element label is not its order.

B: gcd(12,8)=4, but the order is 12 divided by this gcd.

C: The group has twelve elements, but 8 generates only three.

D: 8,4,0 are the successive positive multiples, so the first return takes three.

GR03. Which is the complete set of generators of additive Z₁₀?

A. {1,3,7,9} B. {1,2,3,4,5,6,7,8,9} C. {2,4,6,8} D. {1,9}

Answer: A

A: Exactly these residues are coprime to 10 and therefore have order 10.

B: Nonzero does not imply coprime; 2 and 5 cannot generate the group.

C: Even residues have gcd at least 2 with 10 and cannot generate odd residues.

D: 3 and 7 are also coprime to 10, so this list is incomplete.

GR04. A finite group has 18 elements. Which proposed element order is impossible by Lagrange’s theorem?

A. 1 B. 3 C. 6 D. 8

Answer: D

A: The identity always has order 1.

B: 3 divides 18, so Lagrange does not exclude it.

C: 6 divides 18, so Lagrange does not exclude it; divisibility alone does not assert occurrence.

D: 8 does not divide 18, while the generated cyclic subgroup must have size dividing 18.

GR05. If ord(g)=12, what is ord(g⁸)?

A. 4 B. 3 C. 8 D. 12

Answer: B

A: 4 is the gcd, not the quotient giving the order.

B: The least positive t with 12|8t is 3; equivalently 12/gcd(12,8)=3.

C: The power exponent 8 is not the new element’s order.

D: g⁸ generates a proper subgroup, since gcd(12,8) is not 1.

GR06. Which claim correctly describes the limits of Lagrange’s theorem?

A. Every divisor of |G| is an element order. B. Every subset whose size divides |G| is a subgroup. C. Subgroup orders divide |G|, but not every divisor must occur as a subgroup order in an arbitrary group. D. Every finite abelian group is cyclic.

Answer: C

A: Z₂×Z₂ has size 4 but no element of order 4.

B: For example {0,2,4} in Z₁₂ has size 3 but is not closed.

C: Coset partition proves divisibility; A₄ of size 12 lacks a subgroup of order 6.

D: Z₂×Z₂ is abelian but has no generator for all four elements.

Source and scope

This bounded extension develops relations, lattices or groups under Section 1 of the GATE 2026 CS syllabus. It does not claim complete Discrete Mathematics coverage. Definitions, worked examples, proofs and practice are original.

Official GATE 2026 CS syllabus, Section 1

Source checked: 2026-10-14.