6.1 Groups, Subgroups and Cyclic Groups
The group axioms and the standard examples $\mathbb{Z}_n$, $U(n)$, $S_n$, $D_n$, $GL(n,F)$ and $Q_8$; subgroups and orders of elements; cyclic groups and their subgroups; cosets, Lagrange's theorem and the size of a product $HK$.
A group is what is left of arithmetic when we keep only one operation and insist that it can be undone. The integers under addition, the nonzero rationals under multiplication, the residues modulo $n$, the invertible matrices, the symmetries of a square and the shuffles of a deck of cards all obey the same three rules — associativity, an identity, inverses — and every theorem proved from those rules alone holds in all of them at once. This economy is the reason group theory runs through the whole of mathematics: Galois used groups to decide which polynomial equations are solvable by radicals (Chapter 8), crystallographers use them to classify the $230$ possible symmetry types of a crystal, and the Diffie–Hellman key exchange that protects web traffic is a computation in a cyclic group.
This section builds the vocabulary that the rest of the chapter uses: the axioms and their first consequences, a catalogue of standard groups, subgroups and the tests for them, the order of an element, the complete description of cyclic groups and their subgroups, cosets, Lagrange's theorem, and the size of a product set $HK$. CSIR NET draws on this material in almost every paper — "how many elements of order $d$?", "how many subgroups or generators?", "is $U(n)$ cyclic?", "which of these subsets is a subgroup?", "what can $|H\cap K|$ be?" — and the wrong options are always built from the same few counterexamples, which we collect in the ⚠️ box.
Groups: Axioms and First Examples
A binary operation on a set $G$ is a map $G\times G\to G$, $(a,b)\mapsto a*b$. A group is a set $G$ with a binary operation $*$ such that
- (associativity) $(a*b)*c=a*(b*c)$ for all $a,b,c\in G$;
- (identity) there is $e\in G$ with $e*a=a*e=a$ for all $a\in G$;
- (inverses) for each $a\in G$ there is $b\in G$ with $a*b=b*a=e$.
$G$ is abelian if moreover $a*b=b*a$ for all $a,b$. The order $|G|$ of $G$ is its number of elements (finite or infinite). We usually write $ab$ for $a*b$, $a^{-1}$ for the inverse, $a^0=e$, $a^n=a\cdots a$ ($n$ factors) and $a^{-n}=(a^{-1})^n$. Abelian groups are often written additively: $a+b$, $0$, $-a$, $na$.
Let $G$ be a group and $a,b,c\in G$.
- The identity is unique, and each element has exactly one inverse.
- $(a^{-1})^{-1}=a$ and $(ab)^{-1}=b^{-1}a^{-1}$ (the order reverses).
- Cancellation: $ab=ac\Rightarrow b=c$ and $ba=ca\Rightarrow b=c$.
- The equations $ax=b$ and $ya=b$ have the unique solutions $x=a^{-1}b$, $y=ba^{-1}$. Hence in the multiplication table (Cayley table) of a finite group every element occurs exactly once in each row and once in each column.
- $a^ma^n=a^{m+n}$ and $(a^m)^n=a^{mn}$ for all $m,n\in\mathbb{Z}$. If $G$ is abelian, $(ab)^n=a^nb^n$.
Proof. (1) If $e,e'$ are identities then $e=ee'=e'$. If $b,b'$ are inverses of $a$ then $b=be=b(ab')=(ba)b'=eb'=b'$. (2) $a$ satisfies the defining property of an inverse of $a^{-1}$, so by uniqueness $(a^{-1})^{-1}=a$; and $(ab)(b^{-1}a^{-1})=a(bb^{-1})a^{-1}=aa^{-1}=e$, similarly $(b^{-1}a^{-1})(ab)=e$. (3) Multiply $ab=ac$ on the left by $a^{-1}$; multiply $ba=ca$ on the right by $a^{-1}$. (4) $x=a^{-1}b$ is a solution, and any two solutions are equal by (3). The row of $a$ in the Cayley table lists $ax$ for $x\in G$; by (4) each $b$ appears there exactly once. Columns are similar. (5) For $m,n\ge0$ this is counting factors; the cases with negative exponents follow by cancelling $aa^{-1}=e$, and for abelian $G$ the factors of $(ab)^n$ can be rearranged. ∎
- Let $G\ne\varnothing$ have an associative operation, an element $e$ with $ea=a$ for all $a$ (a left identity), and for each $a$ an element $a'$ with $a'a=e$ (a left inverse). Then $G$ is a group.
- A finite nonempty set with an associative operation in which both cancellation laws hold is a group.
- Neither hypothesis can be weakened carelessly: on any set with at least two elements, $a*b=b$ is associative, every element is a left identity and every element has a "right inverse" ($a*e=e$), yet there is no two-sided identity. And $(\mathbb{N},+)$ is associative and cancellative but not a group.
Proof. (1) Given $a$, let $a'a=e$ and $a''a'=e$. Then $aa'=e(aa')=(a''a')(aa')$ $=a''(a'a)a'=a''ea'$ $=a''a'=e$, so $a'$ is a two-sided inverse. Then $ae=a(a'a)=(aa')a=ea=a$, so $e$ is a two-sided identity.
(2) Fix $a\in G$. Left cancellation makes $x\mapsto ax$ injective, hence (as $G$ is finite) bijective; likewise $x\mapsto xa$. So there is $e$ with $ae=a$. Any $b$ can be written $b=ya$, and then $be=y(ae)=ya=b$: $e$ is a right identity for every element. Also $b(eb)=(be)b=bb$, so $eb=b$ by left cancellation: $e$ is an identity. Finally pick $a'$ with $aa'=e$; then $a(a'a)=(aa')a=a=ae$, and cancelling gives $a'a=e$. (3) $(a*b)*c=c=a*(b*c)$; $e*a=a$; $a*e=e$; an identity $u$ would need $a*u=u=a$ for all $a$. ∎
For $n\ge1$, $\mathbb{Z}_n=\{\bar0,\bar1,\dots,\overline{n-1}\}$ is the set of residue classes modulo $n$ (§5.2) with addition $\bar a+\bar b=\overline{a+b}$. It is an abelian group of order $n$ with identity $\bar0$ and $-\bar a=\overline{n-a}$. We usually drop the bars.
$U(n)=\{\bar a\in\mathbb{Z}_n:\gcd(a,n)=1\}$ with multiplication $\bar a\,\bar b=\overline{ab}$ is an abelian group of order $\varphi(n)$ (Euler's function, §5.3), the group of units modulo $n$; it is also written $U_n$ or $\mathbb{Z}_n^{\times}$. It is closed because $\gcd(a,n)=\gcd(b,n)=1\Rightarrow\gcd(ab,n)=1$, and $\bar a$ has an inverse because $ax\equiv1\pmod n$ is solvable when $\gcd(a,n)=1$ (the theorem on linear congruences, §5.2). (In §1.1, $U_n$ meant the $n$-th roots of unity; in this chapter we write $\mu_n=\{z\in\mathbb{C}:z^n=1\}$ for those.)
Other groups to keep at hand: $(\mathbb{Z},+)$, $(\mathbb{Q},+)$, $(\mathbb{R},+)$, $(\mathbb{C},+)$; the multiplicative groups $\mathbb{Q}^*$, $\mathbb{R}^*$, $\mathbb{C}^*$ of nonzero numbers, $\mathbb{R}_{\gt0}$, the circle $S^1=\{z:|z|=1\}$ and $\mu_n$; and $(\mathcal{P}(X),\triangle)$, the subsets of a set under symmetric difference. Non-examples: $(\mathbb{Z},\cdot)$ and $(\mathbb{Z}_n,\cdot)$ for $n\ge2$ (no inverse of $0$), $(\mathbb{N},+)$ (no identity in $\mathbb{N}$, no inverses).
For a set $X$, the bijections $X\to X$ under composition form the symmetric group $S_X$; for $X=\{1,\dots,n\}$ we write $S_n$, a group of order $n!$. Products are composites read right to left: $\sigma\tau$ means "first $\tau$, then $\sigma$". A cycle $(a_1\,a_2\,\dots\,a_k)$ sends $a_1\mapsto a_2\mapsto\cdots\mapsto a_k\mapsto a_1$ and fixes everything else; cycle notation is developed fully in §6.3.
For $n\ge3$, $S_n$ is not abelian: $(1\,2)(1\,3)=(1\,3\,2)$ but $(1\,3)(1\,2)=(1\,2\,3)$. (Check: in $(1\,2)(1\,3)$, $1\mapsto3\mapsto3$, $3\mapsto1\mapsto2$, $2\mapsto2\mapsto1$.)
For $n\ge3$ the dihedral group $D_n$ is the group of the $2n$ rigid symmetries of a regular $n$-gon: the rotations $e,r,r^2,\dots,r^{n-1}$ ($r$ = rotation through $2\pi/n$) and the $n$ reflections $s,rs,\dots,r^{n-1}s$ ($s$ = a fixed reflection). It is determined by the relations
$$r^n=e,\qquad s^2=e,\qquad srs^{-1}=r^{-1},$$so that $sr^k=r^{-k}s$ and every product can be brought to the form $r^is^a$ ($0\le i\lt n$, $a\in\{0,1\}$):
$$(r^is^a)(r^js^b)=r^{\,i+(-1)^aj}\,s^{\,a+b}.$$Every $r^ks$ is a reflection, so it has order $2$. $D_n$ is non-abelian ($sr=r^{-1}s\ne rs$ since $r^2\ne e$). Notation: many books write $D_{2n}$ for this group of order $2n$; here $|D_n|=2n$. (The derangement number $D_n$ of §5.1 is unrelated.)
The order of $GL(2,\mathbb{Z}_p)$: the first column can be any of the $p^2-1$ nonzero vectors, and the second any vector that is not one of the $p$ multiples of the first. Multiplying the first row by $c\ne0$ is a bijection from $\{\det=1\}$ onto $\{\det=c\}$, so the $p-1$ possible determinants are equally frequent and $|SL(2,\mathbb{Z}_p)|=|GL(2,\mathbb{Z}_p)|/(p-1)$.
Subgroups and the Order of an Element
Let $H$ be a nonempty subset of a group $G$.
- One-step test. $H\le G$ if and only if $ab^{-1}\in H$ for all $a,b\in H$.
- Two-step test. $H\le G$ if and only if $H$ is closed under products and under inverses.
- Finite test. If $H$ is finite and closed under products, then $H\le G$.
Proof. Necessity in (1) and (2) is clear. (1) Take $a\in H$; then $e=aa^{-1}\in H$, so $b^{-1}=eb^{-1}\in H$ for every $b\in H$, and $ab=a(b^{-1})^{-1}\in H$. Associativity is inherited from $G$. (2) follows from (1), since closure under products and inverses gives $ab^{-1}\in H$. (3) Let $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$. If $j-i=1$ then $a=e$ and $a^{-1}=e\in H$; otherwise $a^{-1}=a^{j-i-1}\in H$. Now apply (2). ∎
The finite test is false for infinite subsets: $\mathbb{N}$ is closed under addition in $\mathbb{Z}$ but is not a subgroup.
- For $a\in G$, $\langle a\rangle=\{a^k:k\in\mathbb{Z}\}$ is the cyclic subgroup generated by $a$. For $S\subseteq G$, $\langle S\rangle$ is the intersection of all subgroups containing $S$; it consists of all finite products $s_1^{\pm1}s_2^{\pm1}\cdots s_m^{\pm1}$ with $s_i\in S$ (and $e$).
- The centre of $G$ is $Z(G)=\{z\in G: zg=gz\text{ for all }g\in G\}$; the centraliser of $a$ is $C_G(a)=\{g\in G:ga=ag\}$. Both are subgroups (if $ga=ag$ and $ha=ah$ then $gh^{-1}a=gah^{-1}=agh^{-1}$), $Z(G)=\bigcap_{a\in G}C_G(a)$, and $G$ is abelian iff $Z(G)=G$.
Proof. (1) Every subgroup contains $e$, and if $a,b$ lie in all of them so does $ab^{-1}$. (2) If neither inclusion holds, pick $h\in H\setminus K$ and $k\in K\setminus H$. If $hk\in H$ then $k=h^{-1}(hk)\in H$; if $hk\in K$ then $h=(hk)k^{-1}\in K$. Both are false, so $hk\notin H\cup K$ and the union is not closed. (3) If $G=H\cup K$, then $H\cup K$ is a subgroup, so one of them contains the other and equals $G$. ∎
Let $a,b,g\in G$.
- If $o(a)=\infty$, the powers $a^k$ ($k\in\mathbb{Z}$) are pairwise distinct. If $o(a)=n$, then $a^i=a^j\iff i\equiv j\pmod n$; so $a^k=e\iff n\mid k$, and $\langle a\rangle=\{e,a,\dots,a^{n-1}\}$ has exactly $n$ elements: $o(a)=|\langle a\rangle|$.
- If $o(a)=n$ and $k\in\mathbb{Z}$, then $$o(a^k)=\frac{n}{\gcd(n,k)}.$$
- $o(a^{-1})=o(a)$, $\ o(gag^{-1})=o(a)$ and $o(ab)=o(ba)$.
- If $ab=ba$ and $o(a)=m$, $o(b)=n$ are finite, then $o(ab)$ divides $\operatorname{lcm}(m,n)$. If in addition $\langle a\rangle\cap\langle b\rangle=\{e\}$ — in particular if $\gcd(m,n)=1$ — then $o(ab)=\operatorname{lcm}(m,n)$.
Proof. (1) If $a^i=a^j$ with $i\lt j$ then $a^{j-i}=e$, so $o(a)$ is finite. If $o(a)=n$, write $k=qn+r$ with $0\le r\lt n$; then $a^k=(a^n)^qa^r=a^r$, which is $e$ iff $r=0$ by minimality of $n$. Applying this to $k=i-j$ gives the criterion, and the $n$ powers $e,a,\dots,a^{n-1}$ are distinct and exhaust $\langle a\rangle$.
(2) Let $d=\gcd(n,k)$. By (1), $(a^k)^m=e\iff n\mid km$ $\iff \tfrac nd\mid \tfrac kd\,m\iff\tfrac nd\mid m$, the last step by Euclid's lemma (§5.2), because $\gcd(\tfrac nd,\tfrac kd)=1$. The least such $m\ge1$ is $n/d$.
(3) $(a^{-1})^k=e\iff a^k=e$. Conjugation $x\mapsto gxg^{-1}$ is a bijection with $(gag^{-1})^k=ga^kg^{-1}$, which is $e$ iff $a^k=e$. Finally $ab=a(ba)a^{-1}$ is a conjugate of $ba$.
(4) Let $l=\operatorname{lcm}(m,n)$. Since $a,b$ commute, $(ab)^l=a^lb^l=e$, so $o(ab)\mid l$ by (1). Suppose $\langle a\rangle\cap\langle b\rangle=\{e\}$ and $(ab)^k=e$. Then $a^k=b^{-k}$ lies in both cyclic subgroups, so $a^k=b^k=e$, hence $m\mid k$ and $n\mid k$, so $l\mid k$. If $\gcd(m,n)=1$ and $x\in\langle a\rangle\cap\langle b\rangle$, then $x^m=e$ and $x^n=e$ (as $x$ is a power of $a$ and of $b$), so $o(x)$ divides $\gcd(m,n)=1$ and $x=e$. ∎
Proof. (1) The map $a\mapsto a^{-1}$ is a bijection of $G$ equal to its own inverse, so it splits $G$ into pairs $\{a,a^{-1}\}$ with $a\ne a^{-1}$ and fixed points $a=a^{-1}$, i.e. $a^2=e$. The fixed points are $e$ and the elements of order $2$; the elements of order $\gt2$ come in pairs, so there is an even number of them. If $|G|$ is even, the number of fixed points $|G|-(\text{even})$ is even, and removing $e$ leaves an odd number of elements of order $2$. (2) For all $a,b$: $ab=(ab)^{-1}=b^{-1}a^{-1}=ba$. ∎
Cyclic Groups
Proof. $a^ia^j=a^{i+j}=a^ja^i$. If $G$ is infinite, $o(a)=\infty$ (otherwise $\langle a\rangle$ would be finite), so $k\mapsto a^k$ is injective by Theorem 6.5(1), onto by definition, and $a^{i+j}=a^ia^j$. If $|G|=n$, then $o(a)=n$, and $\bar k\mapsto a^k$ is well defined and injective because $a^i=a^j\iff i\equiv j\pmod n$; it is onto and turns addition modulo $n$ into multiplication. ∎
Let $G=\langle a\rangle$.
- Every subgroup of $G$ is cyclic: if $H\ne\{e\}$, then $H=\langle a^m\rangle$, where $m$ is the least positive integer with $a^m\in H$.
- If $|G|=n$, the order of every subgroup divides $n$, and for each positive divisor $d$ of $n$ there is exactly one subgroup of order $d$, namely $\langle a^{n/d}\rangle$.
- If $|G|=n$, then $\langle a^k\rangle=\langle a^{\gcd(n,k)}\rangle$, and $\langle a^i\rangle\subseteq\langle a^j\rangle\iff\gcd(n,j)\mid\gcd(n,i)$. Thus $d\mapsto\langle a^{d}\rangle$ ($d\mid n$) matches the divisors of $n$ with the subgroups of $G$, reversing divisibility.
- If $G$ is infinite, its subgroups are $\langle a^m\rangle$, $m=0,1,2,\dots$, all distinct, and $\langle a^m\rangle\subseteq\langle a^k\rangle\iff k\mid m$. In $\mathbb{Z}$: the subgroups are the $m\mathbb{Z}$.
Proof. (1) Every element of $H$ is some $a^k$. Divide: $k=qm+r$ with $0\le r\lt m$. Then $a^r=a^k(a^m)^{-q}\in H$, and the minimality of $m$ forces $r=0$. So $a^k=(a^m)^q\in\langle a^m\rangle$; the reverse inclusion is clear.
(2) Since $a^n=e\in H$, the argument of (1) shows $m\mid n$, and $|H|=o(a^m)=n/\gcd(n,m)=n/m$ divides $n$. A subgroup of order $d$ is therefore $\langle a^m\rangle$ with $m\mid n$ and $n/m=d$, i.e. $m=n/d$: it is unique. And $\langle a^{n/d}\rangle$ does have order $n/\gcd(n,n/d)=d$.
(3) $\langle a^k\rangle$ and $\langle a^{\gcd(n,k)}\rangle$ both have order $n/\gcd(n,k)$ by Theorem 6.5(2), so they coincide by uniqueness in (2). Write $g_i=\gcd(n,i)$. The group $\langle a^j\rangle$ is cyclic of order $n/g_j$, so by (2) applied to it, it contains a subgroup of order $n/g_i$ iff $n/g_i$ divides $n/g_j$, i.e. iff $g_j\mid g_i$; and such a subgroup, being a subgroup of $G$ of order $n/g_i$, is $\langle a^i\rangle$. (4) Here $o(a)=\infty$; by (1) the subgroups are the $\langle a^m\rangle$, $m\ge0$, and $a^m\in\langle a^k\rangle\iff a^m=a^{kt}$ for some $t\iff m=kt$. ∎
- If $G=\langle a\rangle$ has order $n$, then $a^k$ generates $G$ iff $\gcd(n,k)=1$. So $G$ has exactly $\varphi(n)$ generators.
- If $|G|=n$ is cyclic and $d\mid n$, then $G$ has exactly $\varphi(d)$ elements of order $d$, and no elements of other orders. Counting all elements by their orders gives Gauss's identity $\sum_{d\mid n}\varphi(d)=n$ (§5.3).
- An infinite cyclic group $\langle a\rangle$ has exactly two generators, $a$ and $a^{-1}$.
- In any group, the number of elements of order $d$ equals $\varphi(d)$ times the number of cyclic subgroups of order $d$. In particular it is a multiple of $\varphi(d)$, hence even if $d\ge3$.
Proof. (1) $o(a^k)=n/\gcd(n,k)$ equals $n$ iff $\gcd(n,k)=1$, and there are $\varphi(n)$ such $k$ in $\{0,\dots,n-1\}$. (2) An element of order $d$ generates a subgroup of order $d$, which by Theorem 6.8(2) is the unique subgroup $C_d$ of order $d$; so the elements of order $d$ are the generators of the cyclic group $C_d$, of which there are $\varphi(d)$ by (1). Orders not dividing $n$ do not occur by Theorem 6.8(2). (3) $a^k$ generates iff $a=(a^k)^t$ for some $t$ iff $kt=1$ iff $k=\pm1$. (4) Each element of order $d$ generates exactly one cyclic subgroup of order $d$, and each such subgroup contains exactly $\varphi(d)$ elements of order $d$ (its generators). And $\varphi(d)$ is even for $d\ge3$ (§5.3). ∎
Cosets and Lagrange's Theorem
Why should the order of a subgroup divide the order of the group? Because the group can be cut into translated copies of the subgroup, all of the same size. These copies are the cosets.
Let $H\le G$ and $a,b\in G$.
- $a\in aH$, and $aH=bH\iff a^{-1}b\in H\iff b\in aH$. Similarly $Ha=Hb\iff ab^{-1}\in H$.
- Two left cosets are either equal or disjoint, so the left cosets form a partition of $G$; likewise the right cosets.
- $|aH|=|H|=|Ha|$.
- $aH=Ha\iff aHa^{-1}=H$; and $aH=H\iff a\in H$.
- $aH\mapsto Ha^{-1}$ is a well-defined bijection from the left cosets onto the right cosets; so the numbers of left and of right cosets are equal.
Proof. Define $a\sim b\iff a^{-1}b\in H$. It is reflexive ($a^{-1}a=e\in H$), symmetric ($b^{-1}a=(a^{-1}b)^{-1}$) and transitive ($a^{-1}c=(a^{-1}b)(b^{-1}c)$), so it is an equivalence relation, and the class of $a$ is $\{b: a^{-1}b\in H\}=\{ah:h\in H\}=aH$. This gives (1), and (2) is the fact that equivalence classes partition a set (Unit 1, §1.1). (3) $h\mapsto ah$ is a bijection $H\to aH$, with inverse $x\mapsto a^{-1}x$. (4) Multiply $aH=Ha$ on the right by $a^{-1}$; and $aH=eH$ iff $a=e^{-1}a\in H$. (5) $aH=bH\iff a^{-1}b\in H$ $\iff (a^{-1})(b^{-1})^{-1}\in H$ $\iff Ha^{-1}=Hb^{-1}$, so the map is well defined and injective; it is onto because $Hc$ is the image of $c^{-1}H$. ∎
Proof. By Theorem 6.10 the $[G:H]$ left cosets are pairwise disjoint, cover $G$, and each has exactly $|H|$ elements. Adding up, $|G|=|H|\,[G:H]$. ∎
Let $G$ be a finite group of order $n$.
- $o(a)$ divides $n$ for every $a\in G$; hence $a^n=e$.
- If $n=p$ is prime, $G$ is cyclic, each of its $p-1$ non-identity elements is a generator, and its only subgroups are $\{e\}$ and $G$. Thus every group of prime order is $\cong\mathbb{Z}_p$.
- Euler and Fermat. If $\gcd(a,m)=1$ then $a^{\varphi(m)}\equiv1\pmod m$; if $p$ is prime and $p\nmid a$ then $a^{p-1}\equiv1\pmod p$.
- Tower law. If $K\le H\le G$ then $[G:K]=[G:H]\,[H:K]$.
- If $H,K\le G$ and $\gcd(|H|,|K|)=1$, then $H\cap K=\{e\}$.
Proof. (1) $o(a)=|\langle a\rangle|$ divides $n$ by Lagrange; write $n=o(a)t$, then $a^n=(a^{o(a)})^t=e$. (2) If $a\ne e$, then $o(a)\gt1$ divides $p$, so $o(a)=p$ and $\langle a\rangle=G$; a subgroup has order $1$ or $p$. Theorem 6.7 gives $G\cong\mathbb{Z}_p$. (3) Apply (1) to $\bar a$ in $U(m)$, a group of order $\varphi(m)$; for $m=p$, $\varphi(p)=p-1$. (4) $|G|=|H|[G:H]$ and $|H|=|K|[H:K]$, so $|G|=|K|[H:K][G:H]$; compare with $|G|=|K|[G:K]$. (For infinite $G$ the same holds when the indices are finite: if $a_iH$ are the distinct left cosets of $H$ in $G$ and $b_jK$ those of $K$ in $H$, the $a_ib_jK$ are the distinct left cosets of $K$ in $G$.) (5) $|H\cap K|$ divides both $|H|$ and $|K|$. ∎
Lagrange's theorem also explains the bound in Theorem 6.3(3): the powers of $a$ in a finite group must repeat within $|G|$ steps. And it lets us close a gap in the theory of cyclic groups: we can now recognise a cyclic group by counting.
Proof. (1) If $G$ is cyclic, Theorem 6.8(2) gives uniqueness. Conversely let $\psi(d)$ be the number of elements of order $d$. Every element has order dividing $n$ (Theorem 6.12), so $\sum_{d\mid n}\psi(d)=n$. By Theorem 6.9(4) and the hypothesis, $\psi(d)$ is $0$ or $\varphi(d)$. Hence $n=\sum_{d\mid n}\psi(d)\le\sum_{d\mid n}\varphi(d)=n$, so equality holds termwise; in particular $\psi(n)=\varphi(n)\ge1$, and an element of order $n$ generates $G$. For the "for instance": two different cyclic subgroups of order $d$ would give more than $d$ elements with $x^d=e$ (all elements of both satisfy it, by Theorem 6.12(1) applied inside them).
(2) If $G\le F^*$ is finite, the solutions of $x^d=1$ in $G$ are roots of the polynomial $x^d-1$, which has at most $d$ roots in a field (factor theorem, §7.3). Apply (1). A finite subgroup $G$ of $\mathbb{C}^*$ of order $n$ satisfies $z^n=1$ for all $z\in G$, so $G\subseteq\mu_n$, and $|\mu_n|=n$ forces $G=\mu_n$. ∎
About the proof. For $n=p$ this is Theorem 6.13(2); the prime-power cases and the non-existence for other $n$ are proved in §5.3. The "only if" direction has a one-line group-theoretic reason: if $n=ab$ with $\gcd(a,b)=1$ and $a,b\ge3$, then $U(n)$ contains at least the four distinct square roots of $1$ given by the Chinese Remainder Theorem ($x\equiv\pm1\bmod a$, $x\equiv\pm1\bmod b$), whereas a cyclic group has at most two solutions of $x^2=e$ (Theorem 6.8(2)). The same count kills $U(2^k)$, $k\ge3$: $\pm1$ and $2^{k-1}\pm1$ all square to $1$.
Products of Subgroups: $HK$
Proof. The map $\mu:H\times K\to HK$, $(h,k)\mapsto hk$, is onto. We show that every fibre has exactly $|H\cap K|$ elements. If $hk=h'k'$, then $t=h^{-1}h'=k(k')^{-1}$ lies in $H\cap K$, and $(h',k')=(ht,t^{-1}k)$. Conversely every pair $(ht,t^{-1}k)$ with $t\in H\cap K$ is in $H\times K$ and has product $hk$, and different $t$ give different pairs. So $|H||K|=|H\times K|=|HK|\cdot|H\cap K|$. For the consequence: $|HK|\le|G|$, so $|H\cap K|\ge|H||K|/|G|\gt1$. ∎
Proof. If $HK\le G$ then it is closed under inverses, so $HK=(HK)^{-1}=\{k^{-1}h^{-1}\}=KH$. Conversely suppose $HK=KH$. Then $HK\ni e$, and for $h,h'\in H$, $k,k'\in K$: $(hk)(h'k')^{-1}=h\,(k k'^{-1})\,h'^{-1}$. The element $(kk'^{-1})h'^{-1}$ lies in $KH=HK$, say it equals $h''k''$; then $(hk)(h'k')^{-1}=(hh'')k''\in HK$. By the one-step test, $HK\le G$. If $kH=Hk$ for all $k\in K$, then $KH=\bigcup_k kH=\bigcup_k Hk=HK$. ∎
- Is it a group? Check closure first (the most frequent failure), then look for the identity by solving $e*a=a$; transport the structure along a bijection when you can see one ($a*b=(1+a)(1+b)-1$).
- Order of an element. In $\mathbb{Z}_n$: $o(k)=n/\gcd(n,k)$. For a product of commuting elements with trivially intersecting cyclic subgroups: the lcm. In $U(n)$: only divisors of $\varphi(n)$ are possible — test them from the largest proper divisor down. In $S_n$: lcm of the cycle lengths (§6.3).
- Counting in a cyclic group of order $n$. Subgroups: $\tau(n)$, one for each divisor. Generators: $\varphi(n)$. Elements of order $d\mid n$: $\varphi(d)$. Solutions of $x^m=e$: $\gcd(m,n)$.
- Is it cyclic? Find an element of order $|G|$; or show it is not by exhibiting two elements of order $2$ (a cyclic group has at most one), a non-abelian pair, or a maximum order smaller than $|G|$. For $U(n)$ use Theorem 6.14.
- Subgroup orders and intersections. Lagrange restricts possible orders to divisors; $|HK|=|H||K|/|H\cap K|\le|G|$ forces intersections to be large; coprime orders force trivial intersections.
- The converse of Lagrange is false. $A_4$ has order $12$ and no subgroup of order $6$ (Example 6). It holds for cyclic groups.
- Finite orders, infinite product. In $GL(2,\mathbb{R})$, $o(A)=4$, $o(B)=3$ and $o(AB)=\infty$ (Example 2). Even in finite groups $o(ab)$ need not divide $\operatorname{lcm}(o(a),o(b))$ unless $ab=ba$.
- Commuting is not enough for $o(ab)=\operatorname{lcm}$. $a$ and $a^{-1}$ commute, both have order $n$, and $o(aa^{-1})=1$. One needs $\langle a\rangle\cap\langle b\rangle=\{e\}$, e.g. coprime orders.
- A union of subgroups is rarely a subgroup. $2\mathbb{Z}\cup3\mathbb{Z}$ is not closed ($2+3=5$). $H\cup K\le G$ only if one contains the other.
- $HK$ need not be a subgroup. $\langle(1\,2)\rangle\langle(1\,3)\rangle$ has $4$ elements in $S_3$.
- Left cosets are not right cosets. In $S_3$, $(1\,3)\langle(1\,2)\rangle=\{(1\,3),(1\,2\,3)\}$ but $\langle(1\,2)\rangle(1\,3)=\{(1\,3),(1\,3\,2)\}$.
- $U(n)$ is not always cyclic. $U(8)$, $U(12)$, $U(15)$, $U(16)$, $U(20)$ are not; $U(9)$, $U(18)$, $U(25)$, $U(54)$ are. Cyclic iff $n=1,2,4,p^k,2p^k$.
- Same order, different groups. $\mathbb{Z}_4\not\cong V_4$; $D_4$, $Q_8$, $U(15)$, $\mathbb{Z}_8$ are pairwise non-isomorphic groups of order $8$.
- All proper subgroups cyclic does not make $G$ cyclic: $V_4$, $S_3$, $Q_8$.
- Infinite abelian groups can be very non-cyclic. $(\mathbb{Q},+)$ is not cyclic although every finitely generated subgroup is; $\mathbb{Q}^*$ has $-1$ of order $2$, so it is not $\cong\mathbb{Z}$ and not cyclic.
- Closed under products is enough only for finite subsets. $\mathbb{N}\subseteq\mathbb{Z}$, and $\{2^k:k\ge0\}\subseteq\mathbb{Q}^*$, are closed but not subgroups.
- Left identity + right inverses is not a group. $a*b=b$ on a two-element set (Theorem 6.2(3)).
- Singular matrices can form a group. $\left\{\left(\begin{smallmatrix}a&a\\a&a\end{smallmatrix}\right):a\ne0\right\}$ is a group under multiplication with identity $\left(\begin{smallmatrix}1/2&1/2\\1/2&1/2\end{smallmatrix}\right)$ — it is not a subgroup of $GL(2,\mathbb{R})$ (Exercise I.2).
- Notation. $|D_n|=2n$ here; some sources write $D_{2n}$ for the same group. Read the order from the problem before counting.
Exercises
- 1 Show that $\mathbb{R}\setminus\{1\}$ with $a*b=a+b-ab$ is a group. Find the identity and the inverse of $3$.
- 2 Which are groups? (a) the odd integers under $+$; (b) $\{2^k:k\in\mathbb{Z}\}$ under $\times$; (c) $\{a+b\sqrt2\ne0:a,b\in\mathbb{Q}\}$ under $\times$; (d) the real $n\times n$ matrices with $\det A=\pm1$ under $\times$; (e) the matrices $\left(\begin{smallmatrix}a&a\\a&a\end{smallmatrix}\right)$, $a\in\mathbb{R}\setminus\{0\}$, under $\times$.
- 3 Write out the Cayley table of $U(12)$. Is $U(12)\cong U(8)$? Is $U(12)\cong\mathbb{Z}_4$?
- 4 In $D_6$ (order $12$) write $r^4\,s\,r^{-1}\,s\,r^3$ in the form $r^is^a$.
- 5 Compute $|GL(2,\mathbb{Z}_p)|$ and $|SL(2,\mathbb{Z}_p)|$ for $p=2,3,5$.
- 6 Using the matrices of Definition 6.5, check that $ij=k$ and $ji=-k$ in $Q_8$, and find $Z(Q_8)$.
- 7 Prove that if $(ab)^2=a^2b^2$ for all $a,b$ in a group $G$, then $G$ is abelian.
- 8 Give a group of order $6$ with exactly one element of order $2$, and one with exactly three. Explain why no group of order $6$ has exactly two.
- 1 Which are subgroups? (a) $\mathbb{R}_{\gt0}\le\mathbb{R}^*$; (b) $\{x\in\mathbb{R}^*:|x|\ge1\}\le\mathbb{R}^*$; (c) the invertible upper triangular matrices in $GL(2,\mathbb{R})$; (d) $\{\sigma\in S_4:\sigma(1)=1\}$; (e) $\{\sigma\in S_4:\sigma(1)=2\}$; (f) the elements of finite order in $\mathbb{C}^*$.
- 2 List all subgroups of $\mathbb{Z}_{18}$ with their orders, and draw the inclusion diagram.
- 3 Find the order of: $14$ in $\mathbb{Z}_{35}$; $(1\,2\,3)(4\,5)$ in $S_5$; $7$ in $U(20)$; $r^4$ in $D_{10}$.
- 4 Find $Z(D_4)$, $Z(D_5)$, $Z(S_3)$, $C_{D_4}(r)$ and $C_{D_4}(s)$. Conjecture $Z(D_n)$ in general and prove it.
- 5 Prove that if $G$ has exactly one element $t$ of order $2$, then $t\in Z(G)$.
- 6 Let $a,b\in G$ commute, with $o(a)=4$ and $o(b)=6$. Prove that $o(ab)=12$.
- 7 Show that $U(8)$ is the union of three proper subgroups, and that no group is the union of two.
- 8 Let $G$ be abelian. Prove that $T=\{a\in G:o(a)\lt\infty\}$ is a subgroup. Show by an example that this fails for non-abelian $G$.
- 1 List the generators of $\mathbb{Z}_{20}$ and of $U(14)$.
- 2 How many elements of order $8$ are there in $\mathbb{Z}_{48}$? Of order $10$ in $\mathbb{Z}_{40}$? Of order $5$ in $\mathbb{Z}_{48}$?
- 3 In $\mathbb{Z}_{72}$ find $\langle12\rangle\cap\langle30\rangle$ and the smallest subgroup containing $12$ and $30$.
- 4 Prove that a group with only finitely many subgroups is finite.
- 5 Decide whether $U(27)$, $U(16)$, $U(18)$, $U(50)$ are cyclic, and find a generator of $U(18)$.
- 6 Prove that in a cyclic group of order $n$ the equation $x^m=e$ has exactly $\gcd(m,n)$ solutions.
- 7 Prove that $(\mathbb{Q},+)\not\cong(\mathbb{Q}_{\gt0},\times)$.
- 8 Find all finite subgroups of $\mathbb{R}^*$ and of $\mathbb{C}^*$.
- 1 List the left and the right cosets of $H=\langle(1\,2)\rangle$ in $S_3$.
- 2 Explain why every proper subgroup of a group of order $15$ is cyclic.
- 3 Prove that every group of order $4$ is isomorphic to $\mathbb{Z}_4$ or to $V_4$.
- 4 Let $[G:H]=2$. Prove that every left coset of $H$ is a right coset and that $g^2\in H$ for every $g\in G$.
- 5 Find all subgroups of $A_4$ (Example 6) and their number for each order.
- 6 $|G|=60$ and $H,K\le G$ with $|H|=10$, $|K|=15$. Find $|H\cap K|$ and $|HK|$, and give an example where this happens.
- 7 Prove: if $p$ is prime and $p^2\gt|G|$, then $G$ has at most one subgroup of order $p$. What does this say for groups of order $21$ and $p=7$?
- 8 Use Euler's theorem to compute $3^{100}\bmod28$.
- 9 Let $G$ be finite and $H,K\le G$ with $\gcd([G:H],[G:K])=1$. Prove that $G=HK$ and $[G:H\cap K]=[G:H][G:K]$.
E1. CSIR Part B GATE MA Which of the following groups is cyclic? (A) $U(16)$; (B) $U(20)$; (C) $U(54)$; (D) $U(15)$.
E2. CSIR Part B The number of elements of order $2$ in the dihedral group $D_8$ of order $16$ is (A) $1$; (B) $8$; (C) $9$; (D) $10$.
E3. CSIR Part B Let $a,b$ be commuting elements of a group with $o(a)=6$ and $o(b)=10$. Which of the following is a possible value of $o(ab)$? (A) $2$; (B) $6$; (C) $10$; (D) $15$.
E4. CSIR Part C Let $G$ be a finite group. Which of the following statements are true? (One or more options may be correct.) (A) If $|G|$ is prime, then $G$ is cyclic. (B) If every proper subgroup of $G$ is cyclic, then $G$ is cyclic. (C) If $G$ is abelian and $|G|=6$, then $G$ is cyclic. (D) There is a finite group with exactly two elements of order $2$.
E5. CSIR Part C Which of the following are true? (A) $U(2^k)$ is cyclic for every $k\ge1$. (B) $U(p)$ is cyclic for every prime $p$. (C) For every $n\ge3$, $U(n)$ has an element of order $2$. (D) $\varphi(n)$ is even for every $n\ge3$.
E6. CSIR Part C Let $H$ and $K$ be subgroups of a group $G$. Which of the following are necessarily true? (A) $H\cup K$ is a subgroup if and only if $H\subseteq K$ or $K\subseteq H$. (B) $HK$ is a subgroup of $G$. (C) If $|H|=7$ and $|K|=11$, then $H\cap K=\{e\}$. (D) If $G$ is finite and $|H|,|K|\gt\sqrt{|G|}$, then $H\cap K\ne\{e\}$.
Suggested plan — 3 lectures × 60 min.
- Axioms and the zoo. Definition 6.1 and Theorem 6.1 (ten minutes); Theorem 6.2(3) as a puzzle ("is a left identity plus right inverses enough?"). Build the catalogue on the board: $\mathbb{Z}_n$, $U(n)$, $S_3$, $D_4$ with a cardboard square, $Q_8$, $V_4$. Example 1. End with Example 3 — counting elements of each order to tell the groups of order $8$ apart.
- Subgroups, orders, cyclic groups. Theorems 6.3–6.5 with Example 2 (the matrices $A$, $B$ are a memorable shock). Theorems 6.7–6.9; project Interactive 2 and let the class predict $\langle k\rangle$ before the path closes, then read the divisor lattice. Example 4 live.
- Cosets and Lagrange. Project Interactive 1 on $S_3$ with $H=\langle(1\,2)\rangle$ (left and right cosets differ), then on $\mathbb{Z}_{12}$ (they always agree). Theorems 6.10–6.13, Example 6 ($A_4$) and Example 7. Close with E4 and E6 of the Exam corner.
Discussion questions. (1) Lagrange says $|H|$ divides $|G|$. Which "converse" statements are true: for every divisor? for prime divisors (Cauchy, §6.4)? for cyclic groups? (2) Why does a cyclic group have at most one subgroup of each order, and what does this have to do with polynomials having at most $d$ roots? (3) Is the group of all rotations of the plane about the origin cyclic? Which of its subgroups are cyclic?
Misconceptions to watch for. "$o(ab)=\operatorname{lcm}(o(a),o(b))$" (needs commuting and trivial intersection); "$HK$ is always a subgroup"; "every divisor of $|G|$ is the order of a subgroup"; confusing $\mathbb{Z}_n$ under $\times$ with $U(n)$; reading $D_n$ as a group of order $n$; forgetting the half-turn $r^{n/2}$ when counting involutions in $D_n$.
Suggested homework. I(1, 2, 4, 8), II(3, 4, 6, 8), III(1, 3, 5, 7), IV(1, 3, 5, 6, 9); Exam corner E2, E3, E5.
Research question. How common are generators of the cyclic group $U(p)$, how can a computer find one quickly, and why do cryptographers prefer primes $p$ for which $(p-1)/2$ is also prime?
Why it matters. The Diffie–Hellman key exchange, used in secure web and messaging protocols worldwide, lets two parties agree on a secret by publishing $g^a\bmod p$ and $g^b\bmod p$ for a public $g\in U(p)$. Its security depends on the subgroup $\langle g\rangle$ being large and having no small subgroups to hide in — exactly the structure described by Theorems 6.8 and 6.9.
What to do.
- For every prime $p\lt 500$, compute the orders of all elements of $U(p)$ and check that the number of elements of order $d$ is $\varphi(d)$ for each $d\mid p-1$ (Theorem 6.9(2)).
- Record the proportion $\varphi(p-1)/(p-1)$ of generators. Which primes give the smallest proportion? Relate it to the prime factors of $p-1$.
- Prove and then use the test: $g$ generates $U(p)$ iff $g^{(p-1)/q}\not\equiv1$ for every prime $q\mid p-1$. Find the least generator for each $p\lt500$.
- For "safe primes" $p=2q+1$ with $q$ prime, show that the possible orders are only $1,2,q,2q$, list the subgroups, and explain why a random $g\ne\pm1$ has order $q$ or $2q$.
Tools: Python (the built-in pow(g, e, p) does fast modular powers); a plotting library for proportion vs $p$.
Hand in: A table of least generators, a plot of $\varphi(p-1)/(p-1)$, and a half-page proof of the generator test with a worked example.
Going further. Artin's conjecture predicts that $2$ is a generator of $U(p)$ for about $37.4\%$ of all primes (Artin's constant); test this numerically up to $10^5$ and read about what is known.
🧪 Self-check quiz
Q1. The order of $10$ in $\mathbb{Z}_{25}$ is
Q2. The number of generators of $\mathbb{Z}_{36}$ is
Q3. Which of these groups is not cyclic?
Q4. A group of order $30$ cannot have a subgroup of order
Q5. $H,K\le G$ with $|H|=6$, $|K|=4$ and $|H\cap K|=2$. Then $|HK|$ equals