7.1 Groups, Homomorphisms, Group Actions and Sylow Theorems
Groups from the axioms to the Sylow theorems — orders of elements, cyclic groups and $U(n)$, normal subgroups and quotients, homomorphisms and automorphism groups, permutations, group actions and the class equation — with the counting tools that GATE MA turns into MCQ, MSQ and NAT questions.
A group is what is left of arithmetic when only one operation is kept: a set with an associative product, an identity and inverses. That is very little structure, and yet it is enough to force surprisingly rigid conclusions. Lagrange's theorem says that the order of every subgroup divides the order of the group; Cauchy and Sylow turn this around and guarantee subgroups of prime-power order; and a few lines of counting then show, for example, that every group of order $35$ is cyclic and that no group of order $56$ is simple. Groups appear wherever there is symmetry — the symmetries of a molecule or a crystal, the shuffles of a deck of cards, the moves of a Rubik's cube, the invertible residues used in RSA encryption, the error-correcting codes in a phone — and the counting arguments of this section are the ones used in all of those places.
GATE MA asks about groups in a very characteristic way: almost every question is a count. How many elements of order $6$ does a group have? How many homomorphisms are there between two given groups, how many automorphisms does a group have, how many Sylow $5$-subgroups can it have, how many abelian groups of order $360$ are there? MSQs then list statements about normal subgroups, quotients and simple groups whose false options are standard counterexamples ($A_4$, $Q_8$, $S_3$). This section collects exactly these tools, with the key proofs; the 📚 box at the end links to the complete development in the CSIR NET course. Throughout, $\mathbb{Z}_n$ is the additive group of residues mod $n$, $U(n)$ the multiplicative group of units mod $n$, $D_n$ the dihedral group of order $2n$, and permutations are composed right to left, like functions.
Groups, Subgroups, Orders and Cyclic Groups
A group is a set $G$ with a binary operation $(a,b)\mapsto ab$ that is associative, has an identity $e$ ($ea=ae=a$ for all $a$), and in which every $a$ has an inverse $a^{-1}$ ($aa^{-1}=a^{-1}a=e$). $G$ is abelian if $ab=ba$ for all $a,b$. The order $|G|$ is the number of elements of $G$. The examples used throughout:
Proof. (a) Taking $b=a$ gives $e\in H$; then $b^{-1}=eb^{-1}\in H$, and $ab=a(b^{-1})^{-1}\in H$. (b) For $a\in H$ the powers $a,a^2,a^3,\dots$ lie in the finite set $H$, so $a^i=a^j$ for some $i\lt j$, whence $a^{j-i}=e$ and $a^{-1}=a^{j-i-1}\in H$; now use (a). (c) The first part is immediate from (a). If $h\in H\setminus K$ and $k\in K\setminus H$, then $hk\in H$ would give $k=h^{-1}(hk)\in H$, and $hk\in K$ would give $h\in K$; so $hk\notin H\cup K$. ∎
- $a^m=e\iff n\mid m$; and $a^i=a^j\iff i\equiv j\pmod n$.
- $o(a^k)=\dfrac{n}{\gcd(n,k)}$. In particular $a^k$ generates $\langle a\rangle$ iff $\gcd(k,n)=1$.
- $o(a^{-1})=o(a)$ and $o(gag^{-1})=o(a)$; hence $o(ab)=o(ba)$.
- If $ab=ba$ and $\gcd(o(a),o(b))=1$, then $o(ab)=o(a)\,o(b)$.
Proof. (1) Write $m=qn+r$ with $0\le r\lt n$: $a^m=(a^n)^qa^r=a^r$, which is $e$ iff $r=0$ by minimality of $n$. (2) $(a^k)^m=e$ $\iff$ $n\mid km$ $\iff$ $\frac{n}{d}\mid\frac kd m$ $\iff$ $\frac nd\mid m$, where $d=\gcd(n,k)$ and $\gcd(\frac nd,\frac kd)=1$. (3) $(gag^{-1})^m=ga^mg^{-1}$ is $e$ iff $a^m=e$; and $ba=a^{-1}(ab)a$. (4) Let $m=o(a)$, $k=o(b)$. Clearly $(ab)^{mk}=a^{mk}b^{mk}=e$. If $(ab)^t=e$ then $a^t=b^{-t}\in\langle a\rangle\cap\langle b\rangle$, a subgroup whose order divides both $m$ and $k$ (Lagrange, below), hence is $\{e\}$; so $a^t=b^t=e$, $m\mid t$, $k\mid t$, and $mk\mid t$. ∎
- Every subgroup of a cyclic group is cyclic.
- If $|\langle a\rangle|=n$, then for every divisor $d$ of $n$ there is exactly one subgroup of order $d$, namely $\langle a^{n/d}\rangle$, and there are no others. So $\mathbb{Z}_n$ has exactly $\tau(n)$ subgroups ($\tau$ = number of divisors).
- For $d\mid n$, $\langle a\rangle$ has exactly $\varphi(d)$ elements of order $d$; it has $\varphi(n)$ generators; and $\sum_{d\mid n}\varphi(d)=n$.
- In $\mathbb{Z}_n$ the equation $dx=0$ has exactly $\gcd(d,n)$ solutions, for every $d\ge1$.
Proof. (1) Let $H\le\langle a\rangle$, $H\ne\{e\}$, and let $k$ be the least positive integer with $a^k\in H$. For $a^m\in H$ write $m=qk+r$, $0\le r\lt k$; then $a^r=a^m(a^k)^{-q}\in H$, so $r=0$: $H=\langle a^k\rangle$. (2) By (1) a subgroup is $\langle a^k\rangle$, of order $n/\gcd(n,k)$; and $\langle a^k\rangle=\langle a^{\gcd(n,k)}\rangle$ because each is a power of the other (Bézout). So the subgroups are the $\langle a^{e}\rangle$ with $e\mid n$, one for each order $n/e$. (3) The elements of order $d$ all lie in the unique subgroup of order $d$, which is cyclic of order $d$, and there they are the generators: $\varphi(d)$ of them by Theorem 7.2(2). Counting the $n$ elements of $\langle a\rangle$ by their orders gives $\sum_{d\mid n}\varphi(d)=n$. (4) $dx\equiv0\pmod n$ iff $\frac{n}{\gcd(d,n)}\mid x$. ∎
- $o(a)$ divides $|G|$ and $a^{|G|}=e$ for every $a\in G$;
- a group of prime order $p$ is cyclic, generated by each of its $p-1$ non-identity elements;
- (Euler, Fermat) $a^{\varphi(n)}\equiv1\pmod n$ when $\gcd(a,n)=1$, and $a^p\equiv a\pmod p$ for $p$ prime;
- if $K\le H\le G$ then $[G:K]=[G:H][H:K]$.
Proof. The relation $a\sim b\iff a^{-1}b\in H$ is an equivalence relation whose classes are the left cosets, so the cosets partition $G$. Each coset has $|H|$ elements, because $h\mapsto ah$ is a bijection $H\to aH$ (its inverse is $x\mapsto a^{-1}x$). Hence $|G|$ is $|H|$ times the number of cosets. (1) Apply this to $H=\langle a\rangle$, of order $o(a)$, and use Theorem 7.2(1). (2) If $a\ne e$ then $o(a)\gt1$ divides $p$, so $o(a)=p$ and $\langle a\rangle=G$. (3) Apply (1) in $U(n)$, of order $\varphi(n)$. (4) Divide $|G|=[G:H]|H|$ by $|K|$. ∎
Proof. The map $H\times K\to HK$, $(h,k)\mapsto hk$, is onto, and $hk=h'k'$ iff $h'=ht$, $k'=t^{-1}k$ for some $t=h^{-1}h'=kk'^{-1}\in H\cap K$. So every element of $HK$ has exactly $|H\cap K|$ preimages. If $HK=KH$, then $(HK)(HK)^{-1}=HKK^{-1}H^{-1}$, which is $HKH=HHK=HK$, so $HK\le G$ by Theorem 7.1; conversely a subgroup $HK$ equals its set of inverses $K^{-1}H^{-1}=KH$. ∎
- If $\gcd(m,n)=1$ then $U(mn)\cong U(m)\times U(n)$ (Chinese remainder theorem), so $\varphi(mn)=\varphi(m)\varphi(n)$.
- For an odd prime $p$, $U(p^k)$ is cyclic of order $p^{k-1}(p-1)$. $U(2)$ and $U(4)\cong\mathbb{Z}_2$ are cyclic, and for $k\ge3$, $U(2^k)\cong\mathbb{Z}_2\times\mathbb{Z}_{2^{k-2}}$ (generated by $-1$ and $5$).
- $U(n)$ is cyclic if and only if $n\in\{1,2,4,p^k,2p^k\}$ with $p$ an odd prime. In particular $U(p)$ is cyclic for every prime $p$ — more generally every finite subgroup of the multiplicative group of a field is cyclic.
Proof (of the parts GATE uses). (1) $a\bmod mn\mapsto(a\bmod m,\ a\bmod n)$ is a bijection $\mathbb{Z}_{mn}\to\mathbb{Z}_m\times\mathbb{Z}_n$ preserving products, and $a$ is prime to $mn$ iff it is prime to $m$ and to $n$. (3), "only if": a cyclic group has at most one element of order $2$ (Theorem 7.3(3) with $d=2$). For $k\ge3$, $U(2^k)$ contains the three elements $-1$ and $2^{k-1}\pm1$ of order $2$, since $(2^{k-1}\pm1)^2=2^{2k-2}\pm2^k+1\equiv1$. If $n=mn'$ with $\gcd(m,n')=1$ and $m,n'\gt2$, then $\varphi(m)$ and $\varphi(n')$ are both even, so $U(m)\times U(n')$ contains $(-1,1)$, $(1,-1)$, $(-1,-1)$, three elements of order $2$. The remaining $n$ are exactly those listed. The cyclicity of $U(p^k)$ (existence of a primitive root) is proved in the 📚 box. ∎
- In $G=\mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_k}$ let $N(d)$ be the number of solutions of $dx=0$. By Theorem 7.3(4), $N(d)=\gcd(d,n_1)\cdots\gcd(d,n_k)$.
- The number of elements of order exactly $d$ is obtained from the $N$'s by inclusion–exclusion over the prime divisors of $d$: for $d=p^a$ it is $N(p^a)-N(p^{a-1})$; for $d=pq$ it is $N(pq)-N(p)-N(q)+N(1)$; in general $\sum_{e\mid d}\mu(d/e)N(e)$.
- The order of $(x_1,\dots,x_k)$ is $\operatorname{lcm}(o(x_1),\dots,o(x_k))$ (Theorem 7.12), so the largest order is $\operatorname{lcm}(n_1,\dots,n_k)$, and $G$ is cyclic iff that lcm equals $|G|$.
- For $U(n)$, first split it with Theorem 7.6 into a product of cyclic groups.
Normal Subgroups, Quotients, Homomorphisms and Automorphisms
- $N\trianglelefteq G$ iff $gng^{-1}\in N$ for all $g\in G$, $n\in N$; it suffices to check $g$ in a generating set of $G$ and $n$ in a generating set of $N$ when $G$ is finite.
- Every subgroup of an abelian group is normal; $Z(G)$ and $G'$ are normal in $G$.
- Every subgroup of index $2$ is normal. (E.g. $A_n\trianglelefteq S_n$, and the rotations $\langle r\rangle\trianglelefteq D_n$.)
- Kernels of homomorphisms are normal (Theorem 7.9). If $H\le G$ is the only subgroup of its order, then $H\trianglelefteq G$.
- Normality is not transitive: $K\trianglelefteq H\trianglelefteq G$ does not imply $K\trianglelefteq G$.
Proof. (1) $gNg^{-1}\subseteq N$ for all $g$ gives, applied to $g^{-1}$, $N\subseteq gNg^{-1}$. For a finite $G$, conjugation by a fixed $g$ is a bijection that maps $N$ into $N$ as soon as it maps generators of $N$ into $N$, and the set of $g$ with $gNg^{-1}=N$ is a subgroup. (2) $gzg^{-1}=z$ for $z\in Z(G)$; and $g[x,y]g^{-1}=[gxg^{-1},gyg^{-1}]$. (3) If $[G:H]=2$, the left cosets are $H$ and $G\setminus H$, and so are the right cosets; thus $gH=Hg$ for every $g$. (4) $gHg^{-1}$ is a subgroup of the same order as $H$. (5) In $D_4$: $\langle s\rangle\trianglelefteq\{e,r^2,s,r^2s\}\trianglelefteq D_4$, each of index $2$ in the next, but $rsr^{-1}=r^2s\notin\langle s\rangle$. ∎
The product is well defined exactly because $N$ is normal: if $aN=a'N$ and $bN=b'N$, then $a'b'=a n_1 b n_2=ab(b^{-1}n_1b)n_2\in abN$.
Proof. Let $G/Z=\langle gZ\rangle$, $Z=Z(G)$. Every element of $G$ has the form $g^iz$ with $z\in Z$, and $(g^iz)(g^jw)=g^{i+j}zw=(g^jw)(g^iz)$ because $z,w$ are central. If $[G:Z]$ were prime, $G/Z$ would be cyclic, hence $G$ abelian and $[G:Z]=1$. Finally, $G/N$ is abelian iff $xyN=yxN$ for all $x,y$, iff $x^{-1}y^{-1}xy\in N$ for all $x,y$, iff $G'\subseteq N$. ∎
Proof. $\phi(e)=\phi(e)^2$ gives $\phi(e)=e$, and then $\phi(a)\phi(a^{-1})=\phi(e)=e$. If $a^n=e$ then $\phi(a)^n=\phi(a^n)=e$. If $\phi(k)=e$ then $\phi(gkg^{-1})=\phi(g)\phi(g)^{-1}=e$. $\phi(a)=\phi(b)\iff ab^{-1}\in\ker\phi$. If $H$ is abelian, $\phi([x,y])=[\phi(x),\phi(y)]=e$. An isomorphism preserves orders in both directions. ∎
- First. If $\phi:G\to H$ is a homomorphism, $G/\ker\phi\cong\phi(G)$. In particular $|G|=|\ker\phi|\,|\phi(G)|$ for finite $G$, so $|\phi(G)|$ divides both $|G|$ and $|H|$.
- Second. If $H\le G$ and $N\trianglelefteq G$, then $HN\le G$, $H\cap N\trianglelefteq H$ and $HN/N\cong H/(H\cap N)$.
- Third. If $N\subseteq K$ are normal in $G$, then $K/N\trianglelefteq G/N$ and $(G/N)/(K/N)\cong G/K$.
- Correspondence. $K\mapsto K/N$ is a bijection from the subgroups of $G$ containing $N$ to the subgroups of $G/N$, preserving inclusion, index and normality.
Proof of (1). Put $K=\ker\phi$ and define $\bar\phi(gK)=\phi(g)$. It is well defined and injective because $gK=g'K\iff g^{-1}g'\in K\iff\phi(g)=\phi(g')$; it is a homomorphism because $\bar\phi(gK\,g'K)=\phi(gg')=\phi(g)\phi(g')$; and its image is $\phi(G)$. (2)–(4) follow by applying (1) to $h\mapsto hN$ on $H$, to $gN\mapsto gK$ on $G/N$, and to the projection $G\to G/N$; see the 📚 box. ∎
- A homomorphism $\phi:\mathbb{Z}_m\to H$ is determined by $h=\phi(1)$, and any $h\in H$ with $h^m=e$ (i.e. $o(h)\mid m$) gives one. So the number of homomorphisms $\mathbb{Z}_m\to H$ equals the number of solutions of $h^m=e$ in $H$; homomorphisms $\mathbb{Z}\to H$ correspond to all $h\in H$.
- The number of homomorphisms $\mathbb{Z}_m\to\mathbb{Z}_n$ is $\gcd(m,n)$. There is a surjective one iff $n\mid m$, and an injective one iff $m\mid n$.
Proof. (1) $\phi(k)=h^k$ is forced, and it is well defined on residues mod $m$ iff $h^m=e$ (Theorem 7.2(1)); it is then a homomorphism. (2) By (1) and Theorem 7.3(4), the count is the number of $x\in\mathbb{Z}_n$ with $mx=0$, which is $\gcd(m,n)$. The image is the cyclic subgroup $\langle x\rangle$, of order dividing $\gcd(m,n)$; it is all of $\mathbb{Z}_n$ only if $n\mid m$, and the kernel is trivial only if $m$ divides $n$ (conversely $x=1$, resp. $x=n/m$, works). ∎
Proof. $(g,h)^t=(g^t,h^t)=e$ iff $o(g)\mid t$ and $o(h)\mid t$, iff $\operatorname{lcm}\mid t$. The largest order in $\mathbb{Z}_m\times\mathbb{Z}_n$ is $\operatorname{lcm}(m,n)=mn/\gcd(m,n)$, which equals $mn$ iff $\gcd(m,n)=1$. ∎
- $\operatorname{Inn}(G)\trianglelefteq\operatorname{Aut}(G)$ and $\operatorname{Inn}(G)\cong G/Z(G)$.
- $\operatorname{Aut}(\mathbb{Z}_n)\cong U(n)$, of order $\varphi(n)$; $\operatorname{Aut}(\mathbb{Z})\cong\mathbb{Z}_2$.
- $\operatorname{Aut}(\mathbb{Z}_p^{\,k})\cong GL(k,\mathbb{Z}_p)$, of order $(p^k-1)(p^k-p)\cdots(p^k-p^{k-1})$. So $\operatorname{Aut}(V_4)\cong GL(2,\mathbb{Z}_2)\cong S_3$ and $|\operatorname{Aut}(\mathbb{Z}_2^{\,3})|=7\cdot6\cdot4=168$.
- For $n\ge3$, $|\operatorname{Aut}(D_n)|=n\varphi(n)$ (the automorphisms are $r\mapsto r^a$, $s\mapsto r^bs$ with $\gcd(a,n)=1$); e.g. $|\operatorname{Aut}(D_4)|=8$. $\operatorname{Aut}(Q_8)\cong S_4$. For $n\ne2,6$, $\operatorname{Aut}(S_n)=\operatorname{Inn}(S_n)\cong S_n$.
Proof. (1) $g\mapsto c_g$ is a homomorphism $G\to\operatorname{Aut}(G)$ ($c_gc_h=c_{gh}$) with image $\operatorname{Inn}(G)$ and kernel $\{g:gx=xg\ \forall x\}=Z(G)$; apply Theorem 7.10(1). Normality: $\alpha c_g\alpha^{-1}=c_{\alpha(g)}$. (2) An automorphism of $\mathbb{Z}_n$ is $x\mapsto ax$ (Theorem 7.11), and it is bijective iff $a$ generates, i.e. $a\in U(n)$; composition multiplies the $a$'s. (3) A homomorphism of $\mathbb{Z}_p^{\,k}$ satisfies $\phi(cx)=c\phi(x)$ for $c\in\mathbb{Z}_p$, so it is $\mathbb{Z}_p$-linear; automorphisms are invertible matrices. Count: the first column is any of the $p^k-1$ nonzero vectors, the second any of the $p^k-p$ vectors outside its span, and so on. (4) An automorphism of $D_n$ must send $r$ to an element of order $n$ in $\langle r\rangle$ (for $n\ge3$ the reflections have order $2$) and $s$ to a reflection (otherwise the image would lie in $\langle r\rangle$), and every such choice respects $srs^{-1}=r^{-1}$. For $Q_8$: $i$ can go to any of the $6$ elements of order $4$ and $j$ to any of the $4$ elements of order $4$ outside $\langle\phi(i)\rangle$, giving $24$ automorphisms. The statement on $S_n$ is proved in the 📚 box. ∎
Permutations, Group Actions and the Class Equation
- Every permutation is a product of disjoint cycles, unique up to order; disjoint cycles commute.
- The order of $\sigma$ is the lcm of its cycle lengths.
- A $k$-cycle is a product of $k-1$ transpositions, so it is even iff $k$ is odd; $\sigma$ is even iff it has an even number of cycles of even length.
- The number of permutations of cycle type $1^{a_1}2^{a_2}\cdots n^{a_n}$ ($a_k$ cycles of length $k$) is $$\frac{n!}{\prod_k k^{a_k}\,a_k!}.$$
Proof. (1) Follow $i\mapsto\sigma(i)\mapsto\sigma^2(i)\mapsto\cdots$ until it returns; the orbits of $\langle\sigma\rangle$ give the cycles. (2) Disjoint cycles commute, so $\sigma^t=e$ iff each cycle to the power $t$ is $e$, and a $k$-cycle has order $k$. (3) $(a_1\,\dots\,a_k)=(a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$, right to left; that the parity is well defined is proved in the 📚 box. (4) Write the $n$ symbols in the $n!$ orders into a template of the given type; each permutation arises $\prod_kk^{a_k}a_k!$ times (each $k$-cycle can start at any of its $k$ entries, and the $a_k$ cycles of length $k$ can be listed in any order). ∎
Proof. $\tau\sigma\tau^{-1}$ sends $\tau(a_i)\mapsto\tau(a_{i+1})$, so conjugation relabels the cycles. Conversely, two permutations of the same type are conjugate by the $\tau$ that matches their cycles entry by entry. The class size is $|S_n|/|C(\sigma)|$ by Theorem 7.16 below. ∎
Proof. "Being in the same orbit" is an equivalence relation ($y=g\cdot x\Rightarrow x=g^{-1}\cdot y$), so orbits partition $X$. The map $gG_x\mapsto g\cdot x$ from left cosets of $G_x$ to $Gx$ is well defined and injective because $g\cdot x=h\cdot x$ $\iff$ $h^{-1}g\in G_x$ $\iff$ $gG_x=hG_x$, and it is onto by definition of the orbit. Finally $h\cdot(g\cdot x)=g\cdot x\iff g^{-1}hg\in G_x$. ∎
- (Cayley) Every group $G$ is isomorphic to a subgroup of $\operatorname{Sym}(G)$; a group of order $n$ embeds in $S_n$.
- If $H\le G$ has index $n$, the action of $G$ on the left cosets of $H$ gives a homomorphism $G\to S_n$ whose kernel is contained in $H$. Hence, if $|G|$ does not divide $n!$, then $H$ contains a nontrivial normal subgroup of $G$. The smallest-prime case: a subgroup whose index is the smallest prime dividing $|G|$ is normal.
- (Burnside) If a finite $G$ acts on a finite $X$, the number of orbits is $\dfrac{1}{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|$.
Proof. (1) $G$ acts on itself by left multiplication, and only $e$ acts trivially. (2) $g$ acts trivially on the cosets only if $gH=H$, i.e. $g\in H$. If $|G|\nmid n!$ the kernel $K$ is not $\{e\}$ (else $G$ would embed in $S_n$). For the last claim see the 📚 box. (3) Count the pairs $(g,x)$ with $g\cdot x=x$ in two ways: $\sum_g|\operatorname{Fix}(g)|=\sum_x|G_x|=\sum_x|G|/|Gx|$, and each orbit $O$ contributes $|O|\cdot|G|/|O|=|G|$ to the last sum. ∎
Proof. The classes partition $G$; the classes of size $1$ make up $Z(G)$, and $|\operatorname{cl}(x)|=[G:C(x)]$ by Theorem 7.16. ∎
- $Z(G)\ne\{e\}$; more generally, if $G$ acts on a finite set $X$, then $|X|\equiv|\operatorname{Fix}(G)|\pmod p$, where $\operatorname{Fix}(G)$ is the set of points fixed by all of $G$.
- Every group of order $p^2$ is abelian: $\mathbb{Z}_{p^2}$ or $\mathbb{Z}_p\times\mathbb{Z}_p$.
- If $G$ is nonabelian of order $p^3$, then $|Z(G)|=p$, $G/Z(G)\cong\mathbb{Z}_p\times\mathbb{Z}_p$, every noncentral class has size $p$, and $G$ has $p^2+p-1$ conjugacy classes.
- $G$ has a normal subgroup of every order $p^j$, $0\le j\le k$.
Proof. (1) Orbits not consisting of a fixed point have size $[G:G_x]$, a power of $p$ greater than $1$; so $|X|-|\operatorname{Fix}(G)|$ is divisible by $p$. For conjugation, $\operatorname{Fix}(G)=Z(G)$, and $|Z(G)|\equiv p^k\equiv0$, so $|Z(G)|\ge p$. (2) $|Z(G)|\in\{p,p^2\}$; if it were $p$, then $G/Z(G)$ would have prime order, hence be cyclic, contradicting Theorem 7.8. So $G=Z(G)$ is abelian; it is $\mathbb{Z}_{p^2}$ if it has an element of order $p^2$, and otherwise every non-identity element has order $p$ and $G\cong\mathbb{Z}_p\times\mathbb{Z}_p$. (3) $|Z(G)|\in\{p,p^2\}$, and $p^2$ is excluded as in (2), so $|Z|=p$ and $G/Z$ has order $p^2$, not cyclic. For $x\notin Z$, $C(x)$ contains $Z$ and $x$, so $|C(x)|\ge p^2$, and $C(x)\ne G$; thus $|C(x)|=p^2$ and the class has $p$ elements. The number of classes is $p+(p^3-p)/p=p^2+p-1$. (4) Induction using a central subgroup of order $p$ (it exists by (1) and Cauchy) and the correspondence theorem. ∎
Cauchy, Sylow and Finite Abelian Groups
Proof. Let $X=\{(g_1,\dots,g_p)\in G^p:g_1g_2\cdots g_p=e\}$. The first $p-1$ entries can be chosen freely and determine $g_p$, so $|X|=|G|^{p-1}\equiv0\pmod p$. The group $\mathbb{Z}_p$ acts on $X$ by cyclically rotating the entries (if $g_1\cdots g_p=e$ then $g_2\cdots g_pg_1=g_1^{-1}eg_1=e$). By Theorem 7.19(1), the number of fixed points is $\equiv|X|\equiv0\pmod p$. The fixed points are the constant tuples $(g,\dots,g)$ with $g^p=e$; $(e,\dots,e)$ is one, so there are at least $p\ge2$, and any $g\ne e$ among them has order $p$. ∎
- (Existence) $G$ has a subgroup of order $p^j$ for every $0\le j\le a$; in particular Sylow $p$-subgroups exist. Every $p$-subgroup of $G$ is contained in a Sylow $p$-subgroup.
- (Conjugacy) Any two Sylow $p$-subgroups are conjugate.
- (Counting) $n_p=[G:N_G(P)]$ for any $P\in\operatorname{Syl}_p(G)$, so $n_p\mid m$; and $n_p\equiv1\pmod p$.
Proof (sketch; the full proof is in the 📚 box). Existence, by induction on $|G|$. If $p$ divides $|Z(G)|$, take an element $z$ of order $p$ in $Z(G)$ (Cauchy); $\langle z\rangle$ is normal, $G/\langle z\rangle$ has order $p^{a-1}m$ and by induction a subgroup of order $p^{a-1}$, whose preimage has order $p^a$. If $p\nmid|Z(G)|$, the class equation shows that some noncentral class has size $[G:C(x)]$ prime to $p$; then $p^a$ divides $|C(x)|\lt|G|$ and induction applies to $C(x)$. Conjugacy and containment: let $Q$ be a $p$-subgroup and $P$ Sylow; $Q$ acts on the $m$ left cosets of $P$ by left multiplication, and since $p\nmid m$, Theorem 7.19(1) gives a fixed coset $gP$: $QgP=gP$, so $Q\subseteq gPg^{-1}$. Counting: $G$ acts transitively on $\operatorname{Syl}_p(G)$ by conjugation with stabiliser $N_G(P)\supseteq P$, so $n_p=[G:N_G(P)]$ divides $[G:P]=m$. Now let $P$ act on $\operatorname{Syl}_p(G)$ by conjugation. If $P$ fixes $Q$, then $P\le N_G(Q)$, and $P,Q$ are Sylow subgroups of $N_G(Q)$, conjugate in it; but $Q\trianglelefteq N_G(Q)$, so $P=Q$. Thus $P$ is the only fixed point and $n_p\equiv1\pmod p$ by Theorem 7.19(1). ∎
- $n_p=1$ if and only if the Sylow $p$-subgroup is normal. In an abelian group every $n_p=1$.
- If $|P|=p$ (i.e. $a=1$), distinct Sylow $p$-subgroups meet trivially, so $G$ has exactly $n_p(p-1)$ elements of order $p$. If $a\ge2$ and $n_p\ge2$, the union of two Sylow $p$-subgroups already contains at least $2p^a-p^{a-1}$ elements.
- If $n_p=k\gt1$, conjugation on $\operatorname{Syl}_p(G)$ is a nontrivial homomorphism $G\to S_k$. So if $|G|\nmid k!$, $G$ has a proper nontrivial normal subgroup; and if $G$ is simple (Definition 7.14) of composite order, it embeds in $A_k$, so $|G|$ divides $k!/2$.
- If $G=P_1P_2\cdots P_r$ where the $P_i$ are normal Sylow subgroups for the distinct primes, then $G\cong P_1\times\cdots\times P_r$; a finite abelian group is the direct product of its Sylow subgroups.
Proof. (1) By conjugacy, $\operatorname{Syl}_p(G)=\{gPg^{-1}\}$, which is $\{P\}$ iff $P\trianglelefteq G$. (2) Two distinct subgroups of prime order intersect in a subgroup of order dividing $p$ and different from $p$, i.e. trivially; each contributes its $p-1$ elements of order $p$, and every element of order $p$ generates a Sylow $p$-subgroup. For $a\ge2$: $|P\cup Q|=2p^a-|P\cap Q|$ and $|P\cap Q|\le p^{a-1}$. (3) The action is transitive on $k\gt1$ points, so it is not trivial; its kernel is a normal subgroup, proper because the action is nontrivial and nontrivial if $|G|\gt|$image$|$, which holds when $|G|\nmid k!$. If $G$ is simple the kernel is trivial; the image meets $A_k$ in a subgroup of index $\le2$, which is normal, so (as $G$ has no subgroup of index $2$ — it would be normal) the image lies in $A_k$. (4) Normal subgroups of coprime orders commute elementwise and intersect trivially; apply Definition 7.8 repeatedly. ∎
Proof. $n_q\mid p$ and $n_q\equiv1\pmod q$; since $p\lt q$, $n_q=1$. Also $n_p\mid q$, so $n_p\in\{1,q\}$, and $n_p=q$ requires $q\equiv1\pmod p$. If $p\nmid q-1$, both Sylow subgroups are normal, so $G\cong\mathbb{Z}_p\times\mathbb{Z}_q\cong\mathbb{Z}_{pq}$ (Theorems 7.22(4), 7.12). The count when $p\mid q-1$ uses semidirect products (📚 box). ∎
Proof (sketch). By Theorem 7.22(4), $G$ is the product of its Sylow subgroups, so it suffices to treat an abelian $p$-group; one shows it splits off a cyclic subgroup generated by an element of maximal order and inducts. Uniqueness: the numbers $|\{x:p^jx=0\}|$ determine the partition of exponents. A partition of $a_i$ is exactly a choice of cyclic factors $\mathbb{Z}_{p_i^{b_1}}\times\cdots$ with $b_1+b_2+\cdots=a_i$. Full proof in the 📚 box. ∎
- Factor $n=p_1^{a_1}\cdots p_r^{a_r}$ and list, for each $p$, the divisors of $n/p^a$ that are $\equiv1\pmod p$. If for some $p$ only $1$ is possible, the Sylow $p$-subgroup is normal: not simple (orders $20,\,40,\,63,\,p^kq$ with $p^k\lt q$…).
- Embedding test: for a simple $G$, each $n_p$ must satisfy $|G|\mid n_p!/2$. Discard the values that fail (orders $36$, $48$, $72$, $80$…).
- Element counting: if every $n_p$ is at least its smallest surviving value, count elements of $p$-power order using Theorem 7.22(2); if the total exceeds $|G|$, some $n_p=1$ (orders $12$, $30$, $56$, $105$, $132$…).
- If all three tests pass (orders $60$, $120$, $168$), Sylow counting does not decide; $60$ and $168$ do have simple groups, $120$ does not.
- To show $G$ is cyclic or abelian: find all $n_p=1$, then $G\cong\prod P_i$ (Theorem 7.22(4)), and use that groups of order $p$ and $p^2$ are abelian.
| 2-part | 3-part | invariant factors |
|---|---|---|
| $\mathbb{Z}_8$ | $\mathbb{Z}_9$ | $\mathbb{Z}_{360}$ |
| $\mathbb{Z}_8$ | $\mathbb{Z}_3^{\,2}$ | $\mathbb{Z}_3\times\mathbb{Z}_{120}$ |
| $\mathbb{Z}_4\times\mathbb{Z}_2$ | $\mathbb{Z}_9$ | $\mathbb{Z}_2\times\mathbb{Z}_{180}$ |
| $\mathbb{Z}_4\times\mathbb{Z}_2$ | $\mathbb{Z}_3^{\,2}$ | $\mathbb{Z}_6\times\mathbb{Z}_{60}$ |
| $\mathbb{Z}_2^{\,3}$ | $\mathbb{Z}_9$ | $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_{90}$ |
| $\mathbb{Z}_2^{\,3}$ | $\mathbb{Z}_3^{\,2}$ | $\mathbb{Z}_2\times\mathbb{Z}_6\times\mathbb{Z}_{30}$ |
| order | groups (up to isomorphism) | number |
|---|---|---|
| $p$ prime | $\mathbb{Z}_p$ | 1 |
| $p^2$ | $\mathbb{Z}_{p^2}$, $\mathbb{Z}_p\times\mathbb{Z}_p$ | 2 |
| $2p$, $p$ odd | $\mathbb{Z}_{2p}$, $D_p$ | 2 |
| 8 | $\mathbb{Z}_8$, $\mathbb{Z}_4\times\mathbb{Z}_2$, $\mathbb{Z}_2^{\,3}$, $D_4$, $Q_8$ | 5 |
| 12 | $\mathbb{Z}_{12}$, $\mathbb{Z}_2\times\mathbb{Z}_6$, $A_4$, $D_6$, $\mathbb{Z}_3\rtimes\mathbb{Z}_4$ | 5 |
| 15, 33, 35, … | cyclic only ($pq$ with $p\nmid q-1$) | 1 |
| 16 | 5 abelian and 9 nonabelian | 14 |
Telling groups of order $8$ apart: elements of order $2$ — $\mathbb{Z}_8$: $1$; $\mathbb{Z}_4\times\mathbb{Z}_2$: $3$; $\mathbb{Z}_2^{\,3}$: $7$; $D_4$: $5$; $Q_8$: $1$ (and $Q_8$ is nonabelian with six elements of order $4$). In $D_n$ the elements of order $2$ number $n$ for odd $n$ and $n+1$ for even $n$.
- The converse of Lagrange's theorem is false. $A_4$ has order $12$ but no subgroup of order $6$: such an $H$ would have index $2$, so $g^2\in H$ for every $g$ (as $A_4/H\cong\mathbb{Z}_2$); every $3$-cycle $c$ equals $(c^2)^2$, so all eight $3$-cycles would lie in $H$, which has only six elements. It is true for abelian groups and for prime-power divisors (Sylow).
- Cauchy is only for primes. $4\mid|V_4|$ but $V_4$ has no element of order $4$; $S_3$ has no element of order $6$.
- All subgroups normal does not mean abelian: every subgroup of $Q_8$ is normal. Normality is not transitive: $\langle s\rangle\trianglelefteq\langle r^2,s\rangle\trianglelefteq D_4$ but $\langle s\rangle\not\trianglelefteq D_4$.
- $o(ab)$ is not determined by $o(a)$ and $o(b)$. In $S_3$, $(1\,2)(2\,3)=(1\,2\,3)$: two elements of order $2$ with product of order $3$. Theorem 7.2(4) needs both commuting and coprime orders: $a=b$ of order $2$ commute, but $ab=e$.
- $\mathbb{Z}_m\times\mathbb{Z}_n$ is cyclic only when $\gcd(m,n)=1$ — $\mathbb{Z}_2\times\mathbb{Z}_2$ is not $\mathbb{Z}_4$. And $U(n)$ is usually not $\mathbb{Z}_{\varphi(n)}$: $U(8)\cong V_4$.
- The same quotient does not mean the same subgroup, and isomorphic subgroups can have different quotients. In $\mathbb{Z}_4\times\mathbb{Z}_2$, $H=\langle(2,0)\rangle\cong K=\langle(0,1)\rangle\cong\mathbb{Z}_2$, but the quotient by $H$ is $V_4$ while the quotient by $K$ is $\mathbb{Z}_4$.
- $N$ and $G/N$ abelian does not make $G$ abelian: $A_3\trianglelefteq S_3$. $[G:Z(G)]$ is never prime (Theorem 7.8).
- Counting elements of each order does not determine a group. $\mathbb{Z}_4\times\mathbb{Z}_4$ and $\mathbb{Z}_2\times Q_8$ both have $1$, $3$ and $12$ elements of orders $1$, $2$, $4$, but one is abelian and the other is not.
- Sylow's conditions are necessary, not sufficient. For $|G|=66$ they allow $n_3=22$, yet every group of order $66$ has $n_3=1$: the normal Sylow $11$-subgroup and a Sylow $3$-subgroup generate a cyclic subgroup of order $33$ and index $2$ that contains every element of order $3$.
- "Not decided by Sylow counting" is not "simple". Orders $60$ and $168$ have simple groups, $120$ does not ($S_5$, $SL(2,\mathbb{Z}_5)$ and the other groups of order $120$ all have proper normal subgroups).
- Conventions change products. Right to left $(1\,2)(1\,3)=(1\,3\,2)$; left to right the same symbols give $(1\,2\,3)$. Check which convention a question uses.
- CSIR Unit 2 · §6.1 Groups, Subgroups and Cyclic Groups — the axioms and their weak forms, subgroup tests, the fundamental theorem of cyclic groups, Lagrange's theorem, the product formula, and the complete proof of when $U(n)$ is cyclic (primitive roots).
- CSIR Unit 2 · §6.2 Normal Subgroups, Quotients and Homomorphisms — all four isomorphism theorems with proofs, commutator subgroups, internal direct products, $\operatorname{Inn}(G)\cong G/Z(G)$, $\operatorname{Aut}(\mathbb{Z}_n)\cong U(n)$ and homomorphisms out of cyclic groups.
- CSIR Unit 2 · §6.3 Permutation Groups, Group Actions and the Class Equation — the proof that parity is well defined, generators of $S_n$, splitting of classes in $A_n$, Cayley's theorem, Burnside's lemma, and $p$-groups.
- CSIR Unit 2 · §6.4 Sylow Theorems and Finite Abelian Groups — complete proofs of the three Sylow theorems, groups of order $pq$, the simplicity of $A_5$, normal subgroups of $S_n$, and the fundamental theorem of finite abelian groups.
Two Labs
Exercises
- 1 How many elements of order $10$ does $\mathbb{Z}_{100}$ have? How many subgroups does it have?
- 2 Find the order of $(4,6)$ in $\mathbb{Z}_{12}\times\mathbb{Z}_{15}$.
- 3 How many elements of order $5$ are there in $\mathbb{Z}_{25}\times\mathbb{Z}_5$? Is the group cyclic?
- 4 Show that $U(18)$ is cyclic and find a generator.
- 5 Show that $U(15)$ is not cyclic, and identify it as a product of cyclic groups.
- 6 Prove that a group in which every non-identity element has order $2$ is abelian.
- 7 Prove that $o(ab)=o(ba)$ in every group, and give an example where $o(ab)\ne\operatorname{lcm}(o(a),o(b))$.
- 8 $H,K$ are subgroups of a group of order $120$ with $|H|=12$ and $|K|=20$. Find the possible orders of $H\cap K$.
- 9 Give an example of an infinite group in which every element has finite order, and of an infinite group in which every non-identity element has infinite order.
- 1 How many homomorphisms $\mathbb{Z}_{20}\to\mathbb{Z}_{30}$ are there? How many are injective?
- 2 How many homomorphisms $\mathbb{Z}_4\to\mathbb{Z}_2\times\mathbb{Z}_2$ are there? How many are onto?
- 3 How many homomorphisms $S_3\to\mathbb{Z}_3$ are there?
- 4 Show that $\{e,(1\,2)\}$ is not normal in $S_3$, but $A_3$ is.
- 5 Find $|\operatorname{Aut}(\mathbb{Z}_{15})|$. Is $\operatorname{Aut}(\mathbb{Z}_{15})$ cyclic?
- 6 Find $Z(Q_8)$, identify $Q_8/Z(Q_8)$, and show that every subgroup of $Q_8$ is normal.
- 7 Identify $(\mathbb{Z}_4\times\mathbb{Z}_4)/\langle(2,2)\rangle$.
- 8 Prove that no group $G$ has $|G/Z(G)|=7$; give a group with $|G/Z(G)|=4$.
- 9 Show that $\operatorname{Aut}(S_3)\cong S_3$ using Theorem 7.13(1) and a count of the possible images of $(1\,2)$ and $(1\,2\,3)$.
- 1 Write $(1\,2\,3\,4)(2\,4\,5)$ as a product of disjoint cycles (right to left) and find its order and sign.
- 2 How many elements of order $3$ does $S_6$ have?
- 3 Find the largest order of an element of $S_8$, and of $S_7$.
- 4 How many elements of order $2$ does $A_6$ have?
- 5 Find the size of the conjugacy class of $(1\,2\,3\,4)$ in $S_6$ and the order of its centraliser.
- 6 $D_6$ acts on the six vertices of a regular hexagon. Find the orbit and the stabiliser of a vertex, and verify the orbit–stabiliser theorem.
- 7 Prove that every group of order $25$ is abelian, and list them.
- 8 Which of these are class equations of some group: $21=1+3+3+7+7$; $12=1+1+2+2+3+3$; $15=1+1+1+3+3+6$?
- 9 Use Burnside's lemma to count the colourings of the four vertices of a square with $2$ colours, up to rotation.
- 1 List the values of $n_2$, $n_3$, $n_5$ allowed by the Sylow theorems for a group of order $60$, and give the actual values for $A_5$.
- 2 Prove that every group of order $45$ is abelian.
- 3 Prove that no group of order $20$ is simple.
- 4 Prove that no group of order $48$ is simple.
- 5 Show that a group of order $105$ has a normal Sylow $5$- or Sylow $7$-subgroup.
- 6 How many elements of order $5$ does a group of order $35$ have?
- 7 How many abelian groups of order $1000$ are there?
- 8 Which abelian groups of order $72$ have exactly three elements of order $2$?
- 9 (Research-flavoured) Show that $S_5$ has no subgroup of order $30$, using Theorem 7.17(2) and the normal subgroups of $S_5$.
E1. GATE MA · MCQ The group $U(40)$ of units modulo $40$ is isomorphic to (A) $\mathbb{Z}_{16}$; (B) $\mathbb{Z}_2\times\mathbb{Z}_8$; (C) $\mathbb{Z}_4\times\mathbb{Z}_4$; (D) $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_4$.
E2. GATE MA · MCQ The number of group homomorphisms from $\mathbb{Z}_6$ to $S_4$ is (A) $6$; (B) $12$; (C) $18$; (D) $24$.
E3. GATE MA · MSQ CSIR Part C Let $G$ be a group of order $63$. Which of the following is/are necessarily true? (One or more options may be correct.) (A) $G$ has a normal subgroup of order $7$. (B) $G$ is abelian. (C) $G$ has an element of order $3$. (D) $G$ has exactly $6$ elements of order $7$.
E4. GATE MA · MSQ Which of the following statements about $S_5$ and $A_5$ is/are true? (One or more options may be correct.) (A) $S_5$ has an element of order $6$. (B) $A_5$ has an element of order $6$. (C) $S_5$ has exactly $6$ Sylow $5$-subgroups. (D) $S_5$ has a subgroup of order $30$.
E5. GATE MA · NAT The number of elements of order $6$ in the symmetric group $S_6$ is ______.
E6. GATE MA · NAT Let $G$ be a nonabelian group of order $27$. The number of conjugacy classes of $G$ is ______.
Suggested plan — 3 lectures × 60 min.
- Orders and cyclic groups. Definition 7.1 with the rule cards (fix the right-to-left convention now). Theorems 7.2–7.4 with proofs; the counting strategy box and Example 1 on the board. Project Interactive 1 on $\mathbb{Z}_{12}$, then $\mathbb{Z}_2\times\mathbb{Z}_6$: same order, different profile. Theorem 7.6 and Example 2 (let students find the three square roots of $1$ in $U(20)$).
- Normal subgroups and homomorphisms. Theorem 7.7, quotients and Theorem 7.8, the first isomorphism theorem with proof, Theorem 7.11 and Example 3 as a quick-fire GATE drill. Automorphism groups (Theorem 7.13) with Example 4. Then permutations: Theorems 7.14–7.15 and Example 5(a), (b).
- Actions and Sylow. Orbit–stabiliser and the class equation (Theorems 7.16–7.19), the Cauchy proof by rotating tuples, the Sylow theorems (Theorem 7.21, sketch) and Theorem 7.22. Project Interactive 2 and run through $12$, $30$, $36$, $60$, $120$. Examples 6 and 7, the table of small groups, and GATE corner E3 and E5.
Discussion questions. (1) Interactive 1 shows that the number of elements of order $d$ is always a multiple of $\varphi(d)$. Why? (Group the elements of order $d$ by the cyclic subgroup they generate.) (2) Why does the existence of a subgroup of index $2$ rule out simplicity, while a subgroup of index $5$ in a group of order $60$ does not? (3) The Sylow sieve leaves $60$, $120$ and $168$ undecided. What extra information settles $120$?
Misconceptions to watch for. Believing the converse of Lagrange's theorem; thinking $o(ab)=\operatorname{lcm}(o(a),o(b))$ always; reading $U(n)$ as cyclic of order $\varphi(n)$; treating "allowed by Sylow III" as "occurs"; forgetting that $n_p\mid m$, not $n_p\mid|G|$; composing permutations in the wrong order; assuming that groups with the same order profile are isomorphic.
Suggested homework. I(1, 3, 5, 8), II(1, 3, 6, 7), III(1, 2, 4, 8, 9), IV(2, 4, 5, 8, 9); GATE corner E1, E4, E6.
Research question. How many different chlorobenzenes are there — molecules obtained from benzene, C₆H₆, by replacing some of the six hydrogen atoms with chlorine — and how does the symmetry group of the hexagon answer this without drawing every molecule?
Why it matters. Chemists counting isomers, crystallographers classifying patterns and engineers enumerating network designs all face the same problem: many configurations are "the same" up to a symmetry. Burnside's lemma (Theorem 7.17(3)) turns the count into an average of fixed points, and its refinement by Pólya underlies software used to enumerate chemical structures.
What to do.
- The symmetry group of the hexagonal ring is $D_6$, of order $12$, acting on the $2^6=64$ ways to put H or Cl on the six positions. List the $12$ elements by cycle type as permutations of the six positions: the identity, rotations by $\pm60^\circ$, $\pm120^\circ$, $180^\circ$, three reflections through opposite vertices and three through opposite edges.
- A labelling is fixed by $g$ iff it is constant on each cycle of $g$, so $|\operatorname{Fix}(g)|=2^{c(g)}$ with $c(g)$ the number of cycles. Compute the twelve values and apply Burnside's lemma.
- Refine the count by the number $k$ of chlorine atoms: count the orbits on labellings with exactly $k$ chlorines for $k=0,\dots,6$ (again with Burnside, now counting fixed labellings with $k$ chlorines). Name the three dichlorobenzenes (the ortho, meta and para isomers).
- Repeat for three substituents (H, Cl, Br): how many orbits on the $3^6$ labellings?
Tools: pencil and paper; optionally a short Python script that applies all twelve permutations to the $64$ labellings and counts orbits directly, as a check.
Hand in: the table of cycle types and fixed-point counts, the total number of chlorobenzenes, the counts for each $k$, and the answer for three substituents, each checked by computer.
Going further. Read about Pólya's enumeration theorem and the cycle index, which produces all the counts of step 3 at once as the coefficients of a polynomial, and about its use in counting isomers of alkanes.
🧪 Self-check quiz
Q1. The number of generators of the cyclic group $\mathbb{Z}_{20}$ is
Q2. Which of the following groups is cyclic?
Q3. The number of conjugacy classes of $S_5$ is
Q4. In a group of order $40$, the number of Sylow $5$-subgroups is
Q5. The number of abelian groups of order $72$, up to isomorphism, is