Chapter 6 · Groups

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

📘 Definition 6.1 — Group

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

  1. (associativity) $(a*b)*c=a*(b*c)$ for all $a,b,c\in G$;
  2. (identity) there is $e\in G$ with $e*a=a*e=a$ for all $a\in G$;
  3. (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$.

📐 Theorem 6.1 — First consequences of the axioms

Let $G$ be a group and $a,b,c\in G$.

  1. The identity is unique, and each element has exactly one inverse.
  2. $(a^{-1})^{-1}=a$ and $(ab)^{-1}=b^{-1}a^{-1}$ (the order reverses).
  3. Cancellation: $ab=ac\Rightarrow b=c$ and $ba=ca\Rightarrow b=c$.
  4. 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.
  5. $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. ∎

📐 Theorem 6.2 — When fewer axioms suffice
  1. 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.
  2. A finite nonempty set with an associative operation in which both cancellation laws hold is a group.
  3. 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$. ∎

📘 Definition 6.2 — The groups $\mathbb{Z}_n$ and $U(n)$

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).

📘 Definition 6.3 — Symmetric groups

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$.)

📘 Definition 6.4 — Dihedral groups

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.)

📘 Definition 6.5 — Matrix groups, the quaternion group and the Klein four-group
General and special linear groupsFor a field $F$ ($\mathbb{Q},\mathbb{R},\mathbb{C}$ or $\mathbb{Z}_p$): $GL(n,F)$ = invertible $n\times n$ matrices under multiplication; $SL(n,F)=\{A:\det A=1\}$. Over $\mathbb{Z}_p$: $|GL(2,\mathbb{Z}_p)|=(p^2-1)(p^2-p)$ and $|SL(2,\mathbb{Z}_p)|=p(p^2-1)$.
Quaternion group $Q_8$$\{\pm1,\pm i,\pm j,\pm k\}$ with $i^2=j^2=k^2=-1$, $ij=k=-ji$, $jk=i=-kj$, $ki=j=-ik$. It is realised in $GL(2,\mathbb{C})$ by $i\mapsto\left(\begin{smallmatrix}i&0\\0&-i\end{smallmatrix}\right)$, $j\mapsto\left(\begin{smallmatrix}0&1\\-1&0\end{smallmatrix}\right)$, $k\mapsto\left(\begin{smallmatrix}0&i\\i&0\end{smallmatrix}\right)$.
Klein four-group $V_4$$\{e,a,b,c\}$ with $a^2=b^2=c^2=e$ and $ab=c$, $bc=a$, $ca=b$: abelian, every non-identity element of order $2$. Examples: $U(8)=\{1,3,5,7\}$, $U(12)$, the symmetries of a non-square rectangle.

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)$.

📘 Definition 6.6 — Isomorphism
Groups $G$ and $H$ are isomorphic, $G\cong H$, if there is a bijection $\phi:G\to H$ with $\phi(ab)=\phi(a)\phi(b)$ for all $a,b$. Isomorphic groups share every property defined by the operation alone: order, being abelian or cyclic, the number of elements of each order, the number of subgroups of each order. To show $G\not\cong H$, find such a property that differs. (Homomorphisms, which drop "bijection", are the subject of §6.2.)
✏️ Example 1 — Group or not?
Decide which of the following are groups. (a) $\mathbb{Z}$ with $a*b=a+b-1$. (b) $\mathbb{R}\setminus\{-1\}$ with $a*b=a+b+ab$. (c) $\mathbb{R}$ with $a*b=|a|\,b$. (d) $\{1,3,5,7\}$ under multiplication modulo $8$. (e) $\{1,2,3,4,5\}$ under multiplication modulo $6$. (f) all $2\times2$ real matrices under multiplication.
(a) Yes $(a*b)*c=a+b+c-2=a*(b*c)$; the identity is $1$ ($a+1-1=a$) and the inverse of $a$ is $2-a$. In fact $\phi(a)=a-1$ is an isomorphism onto $(\mathbb{Z},+)$: $\phi(a*b)=a+b-2=\phi(a)+\phi(b)$.
(b) Yes The trick is $a*b=(1+a)(1+b)-1$. Closure: $(1+a)(1+b)\ne0$, so $a*b\ne-1$. Then $a\mapsto1+a$ turns $*$ into ordinary multiplication on $\mathbb{R}^*$, so associativity is inherited; the identity is $0$ and the inverse of $a$ is $\tfrac1{1+a}-1=-\tfrac{a}{1+a}$. The group is isomorphic to $\mathbb{R}^*$.
(c) No It is associative, $(|a|b)*c=|a||b|c=a*(b*c)$, and both $1$ and $-1$ are left identities ($|\pm1|\,b=b$). But an identity $e$ must satisfy $|e|b=b$ for all $b$, so $e=\pm1$, and also $a*e=|a|e=a$ for all $a$, which fails for $a=-e$. No identity, no group. (A non-unique left identity is already a warning sign: a group has exactly one identity.)
(d) Yes This is $U(8)$: $3^2=9\equiv1$, $5^2=25\equiv1$, $7^2=49\equiv1$ and $3\cdot5=15\equiv7$, $3\cdot7=21\equiv5$, $5\cdot7=35\equiv3\pmod8$. It is a Klein four-group.
(e) No Not closed: $2\cdot3=6\equiv0$, which is not in the set. Only the classes coprime to $6$, namely $\{1,5\}=U(6)$, form a group under multiplication.
(f) No Associative with identity $I$, but singular matrices have no inverse. Restricting to invertible matrices gives $GL(2,\mathbb{R})$.

Subgroups and the Order of an Element

📘 Definition 6.7 — Subgroup
A nonempty subset $H$ of a group $G$ is a subgroup, written $H\le G$, if $H$ is a group under the operation of $G$ restricted to $H$. $\{e\}$ and $G$ are the trivial and the improper subgroup; $H\lt G$ means $H\le G$, $H\ne G$. The identity of a subgroup is automatically the identity $e$ of $G$ (from $e_He_H=e_H=e_He$, cancel in $G$), and inverses in $H$ are inverses in $G$.
📐 Theorem 6.3 — Subgroup tests

Let $H$ be a nonempty subset of a group $G$.

  1. One-step test. $H\le G$ if and only if $ab^{-1}\in H$ for all $a,b\in H$.
  2. Two-step test. $H\le G$ if and only if $H$ is closed under products and under inverses.
  3. 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.

📘 Definition 6.8 — Generated subgroups, centre and centralisers
  • 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$.
📐 Theorem 6.4 — Intersections and unions of subgroups
(1) The intersection of any family of subgroups of $G$ is a subgroup. (2) For $H,K\le G$, the union $H\cup K$ is a subgroup if and only if $H\subseteq K$ or $K\subseteq H$. (3) Consequently no group is the union of two proper subgroups — although a group can be the union of three (for example $V_4$ is the union of its three subgroups of order $2$).

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$. ∎

📘 Definition 6.9 — Order of an element
The order $o(a)$ (also written $|a|$) of $a\in G$ is the least $n\ge1$ with $a^n=e$, or $\infty$ if no such $n$ exists. Only $e$ has order $1$. In additive notation, $o(a)$ is the least $n\ge1$ with $na=0$.
📐 Theorem 6.5 — Properties of the order

Let $a,b,g\in G$.

  1. 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|$.
  2. If $o(a)=n$ and $k\in\mathbb{Z}$, then $$o(a^k)=\frac{n}{\gcd(n,k)}.$$
  3. $o(a^{-1})=o(a)$, $\ o(gag^{-1})=o(a)$ and $o(ab)=o(ba)$.
  4. 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$. ∎

✏️ Example 2 — Two elements of finite order with a product of infinite order
In $GL(2,\mathbb{R})$ let $A=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$ and $B=\begin{pmatrix}0&1\\-1&-1\end{pmatrix}$. Find $o(A)$, $o(B)$, $o(AB)$ and $o(BA)$. What does this show about Theorem 6.5(4)?
$A$ $A$ is the rotation through $90^\circ$: $A^2=-I$, $A^3=-A$, $A^4=I$, so $o(A)=4$.
$B$ $B^2=\begin{pmatrix}-1&-1\\1&0\end{pmatrix}$ and $B^3=B^2B=\begin{pmatrix}1&0\\0&1\end{pmatrix}$, so $o(B)=3$.
$AB$ $AB=\begin{pmatrix}1&1\\0&1\end{pmatrix}$, and by induction $(AB)^k=\begin{pmatrix}1&k\\0&1\end{pmatrix}\ne I$ for every $k\ge1$. So $o(AB)=\infty$; likewise $BA=\begin{pmatrix}1&0\\-1&1\end{pmatrix}$ has infinite order, as Theorem 6.5(3) predicts.
Lesson Without $ab=ba$, the order of a product is not controlled by the orders of the factors at all. Even in finite groups: in $S_3$ the transpositions $(1\,2)$, $(1\,3)$ have order $2$, and their product $(1\,3\,2)$ has order $3$, which does not divide $\operatorname{lcm}(2,2)$.
📐 Theorem 6.6 — Elements of order 2
(1) In a finite group $G$ the number of elements of order greater than $2$ is even. Hence if $|G|$ is even, $G$ has an odd number — in particular at least one — of elements of order $2$. (2) If $a^2=e$ for every $a\in G$, then $G$ is abelian.

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$. ∎

✏️ Example 3 — Orders as fingerprints: $U(8)$, $U(10)$, $U(15)$, $D_4$, $Q_8$
List the orders of all elements of $U(8)$, $U(10)$, $U(15)$, $D_4$ and $Q_8$. Which of these groups are cyclic, and which pairs are isomorphic?
$U(8)$, $U(10)$ In $U(8)=\{1,3,5,7\}$ every $x\ne1$ has $x^2\equiv1$: orders $1,2,2,2$. In $U(10)=\{1,3,7,9\}$: $3^2=9$, $3^3=27\equiv7$, $3^4=81\equiv1$, so $o(3)=4$ and $U(10)=\langle3\rangle\cong\mathbb{Z}_4$; also $o(7)=4$, $o(9)=2$. So $U(10)$ is cyclic and $U(8)$ is not; $U(8)\not\cong U(10)$, although both have order $4$.
$U(15)$ $U(15)=\{1,2,4,7,8,11,13,14\}$. Squares: $4^2=16\equiv1$, $11^2=121\equiv1$, $14^2=196\equiv1$; and $2^2=4$, $7^2=49\equiv4$, $8^2=64\equiv4$, $13^2=169\equiv4$, so these four have order $4$. Orders: one of order $1$, three of order $2$, four of order $4$. No element of order $8$: not cyclic.
$D_4$, $Q_8$ In $D_4$: $r,r^3$ have order $4$; $r^2$ and the four reflections $s,rs,r^2s,r^3s$ have order $2$ — five elements of order $2$. In $Q_8$: $-1$ is the only element of order $2$ (since $(\pm i)^2=(\pm j)^2=(\pm k)^2=-1$), and the six elements $\pm i,\pm j,\pm k$ have order $4$.
Verdict The three groups of order $8$ — $U(15)$ (abelian; $3$ elements of order $2$), $D_4$ (non-abelian; $5$), $Q_8$ (non-abelian; $1$) — are pairwise non-isomorphic, and none is cyclic. Counting elements of each order is the quickest isomorphism test there is.

Cyclic Groups

📘 Definition 6.10 — Cyclic group
A group $G$ is cyclic if $G=\langle a\rangle$ for some $a\in G$; such an $a$ is a generator of $G$. Examples: $\mathbb{Z}=\langle1\rangle=\langle-1\rangle$; $\mathbb{Z}_n=\langle1\rangle$; $\mu_n=\langle e^{2\pi i/n}\rangle$; $U(10)=\langle3\rangle$; the rotation subgroup $\langle r\rangle$ of $D_n$.
📐 Theorem 6.7 — Classification of cyclic groups
Every cyclic group is abelian. If $G=\langle a\rangle$ is infinite, $k\mapsto a^k$ is an isomorphism $\mathbb{Z}\to G$; if $|G|=n$, then $\bar k\mapsto a^k$ is an isomorphism $\mathbb{Z}_n\to G$. So, up to isomorphism, the cyclic groups are exactly $\mathbb{Z}$ and $\mathbb{Z}_n$ ($n\ge1$), and two cyclic groups are isomorphic iff they have the same order.

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. ∎

📐 Theorem 6.8 — Fundamental theorem of cyclic groups

Let $G=\langle a\rangle$.

  1. 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$.
  2. 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$.
  3. 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.
  4. 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$. ∎

📐 Theorem 6.9 — Generators and elements of each order
  1. 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.
  2. 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).
  3. An infinite cyclic group $\langle a\rangle$ has exactly two generators, $a$ and $a^{-1}$.
  4. 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). ∎

✏️ Example 4 — Inside $\mathbb{Z}_{60}$
In $\mathbb{Z}_{60}$: (a) how many generators and how many subgroups are there? (b) List the elements of order $12$. (c) Identify $\langle18\rangle$, $\langle45\rangle$, $\langle18\rangle\cap\langle45\rangle$ and the smallest subgroup containing $18$ and $45$. (d) How many solutions has $12x=0$?
(a) Generators: $\varphi(60)=60\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45=16$. Subgroups: one for each divisor of $60=2^2\cdot3\cdot5$, so $\tau(60)=3\cdot2\cdot2=12$.
(b) They are the $\varphi(12)=4$ generators of the unique subgroup of order $12$, which is $\langle5\rangle=\{0,5,10,\dots,55\}$: the multiples $5k$ with $\gcd(k,12)=1$, i.e. $5,25,35,55$. Check: $o(25)=60/\gcd(60,25)=60/5=12$.
(c) $\langle18\rangle=\langle\gcd(60,18)\rangle=\langle6\rangle$, of order $10$; $\langle45\rangle=\langle15\rangle$, of order $4$. In the divisor picture of Theorem 6.8(3), $\langle i\rangle\cap\langle j\rangle=\langle\operatorname{lcm}(i,j)\rangle$ and the subgroup generated by both is $\langle\gcd(i,j)\rangle$ (for divisors $i,j$ of $n$). So $\langle6\rangle\cap\langle15\rangle=\langle30\rangle=\{0,30\}$, of order $2=\gcd(10,4)$, and $\langle18,45\rangle=\langle3\rangle$, of order $20=\operatorname{lcm}(10,4)$.
(d) $12x\equiv0\pmod{60}\iff5\mid x$: the $12$ elements $0,5,\dots,55$. In general $mx=0$ has $\gcd(m,n)$ solutions in $\mathbb{Z}_n$ (Exercise III.6).
Interactive 2 — Subgroups of $\mathbb{Z}_n$ on a Clock and in the Divisor Lattice

The residues $0,1,\dots,n-1$ sit round a clock. Starting at $0$, keep adding $k$: the points you visit form the cyclic subgroup $\langle k\rangle$, and the path closes after $o(k)=n/\gcd(n,k)$ steps. On the right, every divisor $d$ of $n$ is a node labelled by the subgroup $\langle d\rangle$ of order $n/d$; lines join $d$ to $dp$ ($p$ prime). The highlighted node is the subgroup you generated — always $\langle\gcd(n,k)\rangle$. Press Play to run $k$ through $0,1,\dots,n-1$.

249
gcd(n, k)—
⟨k⟩ = ⟨gcd⟩, order—
generator of ℤₙ?—
φ(n) generators—
τ(n) subgroups—
✏️ Example 5 — Cyclic or not? Prove or disprove
(a) $(\mathbb{Q},+)$ is not cyclic, but every finitely generated subgroup of it is cyclic. (b) $\mathbb{Q}^*$ is not cyclic. (c) If every proper subgroup of a group $G$ is cyclic, then $G$ is cyclic. (d) $U(20)$ is cyclic; $U(25)$ is cyclic.
(a) True If $\mathbb{Q}=\langle p/q\rangle$ with $p/q\ne0$, then $p/(2q)=t\cdot p/q$ for some $t\in\mathbb{Z}$, i.e. $t=\tfrac12$ — impossible. But $\langle \tfrac{p_1}{q_1},\dots,\tfrac{p_k}{q_k}\rangle\subseteq\langle\tfrac{1}{q_1\cdots q_k}\rangle$, since each generator is an integer multiple of $\tfrac1{q_1\cdots q_k}$; a subgroup of a cyclic group is cyclic (Theorem 6.8).
(b) True $-1\in\mathbb{Q}^*$ has order $2$. An infinite cyclic group is $\cong\mathbb{Z}$, whose only element of finite order is $0$. ($\mathbb{Q}^*$ is not even finitely generated: finitely many rationals involve finitely many primes.)
(c) False $V_4=U(8)$: its proper subgroups $\{1\},\{1,3\},\{1,5\},\{1,7\}$ are cyclic, but $V_4$ is not. Also $S_3$ (proper subgroups of orders $1,2,3$) and $Q_8$ (proper subgroups $\{1\}$, $\{\pm1\}$, $\langle i\rangle$, $\langle j\rangle$, $\langle k\rangle$).
(d) $U(20)=\{1,3,7,9,11,13,17,19\}$ has order $8$, but $3^4=81\equiv1$, $7^2=49\equiv9$ and $7^4\equiv81\equiv1$, $9^2\equiv1$, $11^2=121\equiv1$, $13^2=169\equiv9$, $17^2=289\equiv9$, $19^2=361\equiv1$; every element has order dividing $4$, so $U(20)$ is not cyclic. In $U(25)$ (order $20$): $2^{10}=1024\equiv24\equiv-1\pmod{25}$, so $o(2)$ divides $20$ but not $10$; and $2^4=16\not\equiv1$, so $o(2)\nmid 4$. The divisors of $20$ dividing neither $10$ nor $4$: only $20$. So $o(2)=20$ and $U(25)=\langle2\rangle$ is cyclic — as Theorem 6.14 below predicts.

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.

📘 Definition 6.11 — Cosets and index
Let $H\le G$ and $a\in G$. The left coset of $H$ containing $a$ is $aH=\{ah:h\in H\}$ and the right coset is $Ha=\{ha:h\in H\}$ (in additive notation, $a+H$). The number of left cosets is the index $[G:H]$ (possibly infinite). For example, the cosets of $3\mathbb{Z}$ in $\mathbb{Z}$ are $3\mathbb{Z}$, $1+3\mathbb{Z}$, $2+3\mathbb{Z}$ — the residue classes modulo $3$ — so $[\mathbb{Z}:3\mathbb{Z}]=3$.
📐 Theorem 6.10 — Cosets partition the group

Let $H\le G$ and $a,b\in G$.

  1. $a\in aH$, and $aH=bH\iff a^{-1}b\in H\iff b\in aH$. Similarly $Ha=Hb\iff ab^{-1}\in H$.
  2. Two left cosets are either equal or disjoint, so the left cosets form a partition of $G$; likewise the right cosets.
  3. $|aH|=|H|=|Ha|$.
  4. $aH=Ha\iff aHa^{-1}=H$; and $aH=H\iff a\in H$.
  5. $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$. ∎

📐 Theorem 6.11 — Lagrange's theorem
If $G$ is a finite group and $H\le G$, then $$|G|=|H|\cdot[G:H].$$ In particular the order of every subgroup divides the order of the group.

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]$. ∎

📐 Theorem 6.12 — Consequences of Lagrange's theorem

Let $G$ be a finite group of order $n$.

  1. $o(a)$ divides $n$ for every $a\in G$; hence $a^n=e$.
  2. 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$.
  3. 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$.
  4. Tower law. If $K\le H\le G$ then $[G:K]=[G:H]\,[H:K]$.
  5. 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.

📐 Theorem 6.13 — A counting criterion for cyclicity; finite subgroups of $F^*$
(1) A finite group $G$ of order $n$ is cyclic if and only if, for each divisor $d$ of $n$, $G$ has at most one cyclic subgroup of order $d$ — for instance if, for each $d\mid n$, the equation $x^d=e$ has at most $d$ solutions in $G$. (2) Every finite subgroup of the multiplicative group $F^*$ of a field $F$ is cyclic. In particular $U(p)=\mathbb{Z}_p^*$ is cyclic for every prime $p$, and the finite subgroups of $\mathbb{C}^*$ are exactly the groups $\mu_n$.

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$. ∎

📐 Theorem 6.14 — When is $U(n)$ cyclic?
$U(n)$ is cyclic if and only if $n=1,2,4,p^k$ or $2p^k$ with $p$ an odd prime and $k\ge1$. A generator of $U(n)$ is exactly a primitive root modulo $n$, so this is the primitive root theorem of §5.3 in group language. For $k\ge3$, $U(2^k)$ is not cyclic; it is generated by $-1$ and $5$, with $o(5)=2^{k-2}$.

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$.

Interactive 1 — Cosets Tile the Group

Choose a group and one of its proper subgroups $H$. Left: each row is one left coset $gH$ — all rows have the same length $|H|$, so $|G|=|H|\cdot[G:H]$ (Lagrange). Right: the right cosets $Hg$, with every element keeping the colour of its left coset. If each right row is a single colour, every left coset is also a right coset ($gH=Hg$). Press Play to run through all subgroups.

|G|—
|H|—
[G : H]—
|H| · [G : H]—
left = right cosets?—
✏️ Example 6 — The converse of Lagrange's theorem fails: $A_4$
Let $A_4\le S_4$ consist of the identity, the three double transpositions $(1\,2)(3\,4)$, $(1\,3)(2\,4)$, $(1\,4)(2\,3)$, and the eight $3$-cycles $(a\,b\,c)$ — the twelve even permutations of $\{1,2,3,4\}$ (§6.3), or equivalently the rotation group of a regular tetrahedron. Show that $A_4$ is a group of order $12$ with no subgroup of order $6$.
Subgroup Even permutations are closed under composition (§6.3), and $A_4$ is finite, so it is a subgroup by the finite test (Theorem 6.3(3)). It has $1+3+8=12$ elements.
Index 2 forces squares Suppose $H\le A_4$ with $|H|=6$, so $[A_4:H]=2$ and the left cosets are $H$ and $A_4\setminus H$. Let $g\notin H$. If $g^2\notin H$, then $g^2$ lies in the coset $gH=A_4\setminus H$, so $g^2=gh$ for some $h\in H$, giving $g=h\in H$ — a contradiction. Hence $g^2\in H$ for every $g\in A_4$ (trivially also for $g\in H$).
Too many 3-cycles A $3$-cycle $\sigma$ has $\sigma^3=e$, so $\sigma=\sigma^4=(\sigma^2)^2$ is a square, and therefore $\sigma\in H$. Then $H$ contains all eight $3$-cycles plus $e$: at least $9\gt6$ elements. Contradiction.
Moral $6$ divides $12$, yet there is no subgroup of order $6$. The converse of Lagrange does hold for cyclic groups (Theorem 6.8), and Sylow's theorems (§6.4) give a partial converse for prime powers. Interactive 1 lets you inspect every proper subgroup of $A_4$: their orders are $1,2,3,4$ — never $6$.

Products of Subgroups: $HK$

📘 Definition 6.12 — Product set
For subsets $H,K$ of a group $G$, $HK=\{hk:h\in H,\ k\in K\}$. In additive notation it is $H+K$. Even when $H$ and $K$ are subgroups, $HK$ need not be one.
📐 Theorem 6.15 — The size of $HK$
If $H,K$ are finite subgroups of a group $G$, then $$|HK|=\frac{|H|\,|K|}{|H\cap K|}.$$ Consequently, if $G$ is finite and $|H|\,|K|\gt|G|$, then $H\cap K\ne\{e\}$.

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$. ∎

📐 Theorem 6.16 — When is $HK$ a subgroup?
For $H,K\le G$: $HK$ is a subgroup if and only if $HK=KH$. In particular $HK\le G$ whenever $G$ is abelian, or whenever $kH=Hk$ for every $k\in K$ (e.g. when $H$ is a normal subgroup, §6.2).

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$. ∎

✏️ Example 7 — Using $|HK|$: prove or disprove
(a) In $S_3$ let $H=\langle(1\,2)\rangle$, $K=\langle(1\,3)\rangle$. Compute $HK$ and $KH$; is $HK$ a subgroup? (b) $G$ has order $36$ and subgroups $H$, $K$ of orders $12$ and $18$. Find $|H\cap K|$ and show that $G=HK$. (c) Prove that a group of order $20$ has at most one subgroup of order $5$.
(a) $HK=\{e,(1\,2),(1\,3),(1\,2)(1\,3)\}=\{e,(1\,2),(1\,3),(1\,3\,2)\}$ and $KH=\{e,(1\,3),(1\,2),(1\,3)(1\,2)\}=\{e,(1\,2),(1\,3),(1\,2\,3)\}$. They differ, so by Theorem 6.16 neither is a subgroup — as Lagrange also shows, since $|HK|=\tfrac{2\cdot2}{1}=4\nmid6$.
(b) $H\cap K$ is a subgroup of both, so $|H\cap K|$ divides $\gcd(12,18)=6$. And $|HK|=\tfrac{12\cdot18}{|H\cap K|}=\tfrac{216}{|H\cap K|}\le36$ forces $|H\cap K|\ge6$. So $|H\cap K|=6$ and $|HK|=36$, i.e. $HK=G$ — a subgroup, even though we know nothing else about $G$.
(c) Let $P\ne Q$ have order $5$. Then $P\cap Q$ is a proper subgroup of $P$, so it has order $1$ (Theorem 6.12(2)), and $|PQ|=\tfrac{5\cdot5}{1}=25\gt20=|G|$ — impossible. The same argument shows: if $p$ is prime and $p^2\gt|G|$, then $G$ has at most one subgroup of order $p$.
🧭 Problem-solving strategy — orders, subgroups and cyclicity
  1. 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$).
  2. 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).
  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)$.
  4. 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.
  5. 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.
⚠️ Counterexamples and pitfalls
  1. The converse of Lagrange is false. $A_4$ has order $12$ and no subgroup of order $6$ (Example 6). It holds for cyclic groups.
  2. 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$.
  3. 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.
  4. 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.
  5. $HK$ need not be a subgroup. $\langle(1\,2)\rangle\langle(1\,3)\rangle$ has $4$ elements in $S_3$.
  6. 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)\}$.
  7. $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$.
  8. 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$.
  9. All proper subgroups cyclic does not make $G$ cyclic: $V_4$, $S_3$, $Q_8$.
  10. 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.
  11. 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.
  12. Left identity + right inverses is not a group. $a*b=b$ on a two-element set (Theorem 6.2(3)).
  13. 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).
  14. Notation. $|D_n|=2n$ here; some sources write $D_{2n}$ for the same group. Read the order from the problem before counting.

Exercises

I
Axioms and examples.
  • 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 $a*b=1-(1-a)(1-b)$, so $a\mapsto1-a$ carries $*$ to multiplication on $\mathbb{R}^*$; closure ($(1-a)(1-b)\ne0$) and associativity follow. Identity $0$; inverse of $a$ is $1-\tfrac1{1-a}=-\tfrac{a}{1-a}$, so $3^{-1}=\tfrac32$. Check: $3+\tfrac32-\tfrac92=0$.
2 (a) No: $1+1=2$ is even (and $0$ is missing). (b) Yes: $2^j2^k=2^{j+k}$, a cyclic group $\cong\mathbb{Z}$. (c) Yes: products stay of this form, and $(a+b\sqrt2)^{-1}=\tfrac{a-b\sqrt2}{a^2-2b^2}$ with $a^2-2b^2\ne0$ because $\sqrt2\notin\mathbb{Q}$. (d) Yes: $\det(AB)=\det A\det B=\pm1$ and $\det A^{-1}=\pm1$; it is a subgroup of $GL(n,\mathbb{R})$. (e) Yes: $\left(\begin{smallmatrix}a&a\\a&a\end{smallmatrix}\right)\left(\begin{smallmatrix}b&b\\b&b\end{smallmatrix}\right)=\left(\begin{smallmatrix}2ab&2ab\\2ab&2ab\end{smallmatrix}\right)$; identity at $a=\tfrac12$, inverse at $\tfrac1{4a}$; $a\mapsto2a$ is an isomorphism onto $\mathbb{R}^*$. A group of singular matrices — its identity is not $I$.
3 $U(12)=\{1,5,7,11\}$ with $5^2=25\equiv1$, $7^2=49\equiv1$, $11^2=121\equiv1$, $5\cdot7=35\equiv11$, $5\cdot11=55\equiv7$, $7\cdot11=77\equiv5$. Every non-identity element has order $2$: $U(12)\cong V_4\cong U(8)$ (match $5,7,11$ with $3,5,7$ in any order). Not $\cong\mathbb{Z}_4$, which has an element of order $4$.
4 Using $(r^is^a)(r^js^b)=r^{i+(-1)^aj}s^{a+b}$: $r^4s\cdot r^{-1}=r^{5}s$; $r^5s\cdot s=r^5$; $r^5\cdot r^3=r^8=r^2$. Answer $r^2$.
5 $(p^2-1)(p^2-p)$: $6,\ 48,\ 480$. $p(p^2-1)$: $6,\ 24,\ 120$. (For $p=2$, $GL=SL$ has order $6$; it is isomorphic to $S_3$, acting on the three nonzero vectors of $\mathbb{Z}_2^2$.)
6 $\left(\begin{smallmatrix}i&0\\0&-i\end{smallmatrix}\right)\left(\begin{smallmatrix}0&1\\-1&0\end{smallmatrix}\right)=\left(\begin{smallmatrix}0&i\\i&0\end{smallmatrix}\right)=k$ and $\left(\begin{smallmatrix}0&1\\-1&0\end{smallmatrix}\right)\left(\begin{smallmatrix}i&0\\0&-i\end{smallmatrix}\right)=\left(\begin{smallmatrix}0&-i\\-i&0\end{smallmatrix}\right)=-k$. $\pm1$ commute with everything; $\pm i$ fail to commute with $j$, $\pm j$ with $i$, $\pm k$ with $i$. So $Z(Q_8)=\{\pm1\}$.
7 $abab=aabb$; cancel $a$ on the left and $b$ on the right: $ba=ab$.
8 $\mathbb{Z}_6$: only $3$ has order $2$. $S_3$: the three transpositions. By Theorem 6.6(1) a group of even order has an odd number of elements of order $2$.
II
Subgroups and orders.
  • 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 (a) Yes. (b) No: $2$ is in it but $2^{-1}=\tfrac12$ is not. (c) Yes: products and inverses of invertible upper triangular matrices are upper triangular. (d) Yes (it is a copy of $S_3$ on $\{2,3,4\}$). (e) No: it does not contain the identity. (f) Yes: in an abelian group $(ab)^{mn}=e$ if $a^m=b^n=e$ (see 8); this subgroup is the set of all roots of unity.
2 One subgroup per divisor of $18$: $\langle0\rangle$ (order $1$), $\langle9\rangle$ ($2$), $\langle6\rangle$ ($3$), $\langle3\rangle$ ($6$), $\langle2\rangle$ ($9$), $\langle1\rangle=\mathbb{Z}_{18}$ ($18$). Inclusions reverse divisibility: $\langle9\rangle,\langle6\rangle\subseteq\langle3\rangle$; $\langle6\rangle\subseteq\langle2\rangle$; all inside $\langle1\rangle$.
3 $35/\gcd(35,14)=5$; $\operatorname{lcm}(3,2)=6$ (disjoint cycles commute and their cyclic subgroups meet trivially); $7^2=49\equiv9$, $7^4\equiv81\equiv1\pmod{20}$, so $4$; $10/\gcd(10,4)=5$.
4 $Z(D_4)=\{e,r^2\}$; $Z(D_5)=\{e\}$; $Z(S_3)=\{e\}$; $C_{D_4}(r)=\langle r\rangle$; $C_{D_4}(s)=\{e,s,r^2,r^2s\}$. In general $Z(D_n)=\{e\}$ for odd $n$ and $\{e,r^{n/2}\}$ for even $n$: a reflection $r^ks$ does not commute with $r$ (since $r(r^ks)=r^{k+1}s$ but $(r^ks)r=r^{k-1}s$ and $r^2\ne e$), and a rotation $r^j$ commutes with $s$ iff $r^{j}=r^{-j}$, i.e. $n\mid2j$.
5 For $g\in G$, $gtg^{-1}$ also has order $2$ (Theorem 6.5(3)), so $gtg^{-1}=t$, i.e. $gt=tg$.
6 $o(ab)$ divides $12$. $(ab)^6=a^6b^6=a^2\ne e$, so $o(ab)\nmid6$; $(ab)^4=a^4b^4=b^4\ne e$, so $o(ab)\nmid4$. The only divisor of $12$ dividing neither $6$ nor $4$ is $12$.
7 $U(8)=\{1,3\}\cup\{1,5\}\cup\{1,7\}$. Two subgroups: Theorem 6.4(3).
8 $e\in T$; if $a^m=e$ and $b^n=e$ then $(ab^{-1})^{mn}=(a^m)^n(b^{n})^{-m}=e$ because the elements commute. In $GL(2,\mathbb{R})$ the matrices $A,B$ of Example 2 have finite order but $AB$ does not.
III
Cyclic groups.
  • 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 $\mathbb{Z}_{20}$: the $\varphi(20)=8$ residues $1,3,7,9,11,13,17,19$. $U(14)=\{1,3,5,9,11,13\}$ is cyclic of order $6$ with $\varphi(6)=2$ generators: $3$ ($3,9,13,11,5,1$) and $5$ ($5,11,13,9,3,1$).
2 $8\mid48$: $\varphi(8)=4$. $10\mid40$: $\varphi(10)=4$. $5\nmid48$: none.
3 $\langle12\rangle=\langle\gcd(72,12)\rangle=\langle12\rangle$ (order $6$) and $\langle30\rangle=\langle6\rangle$ (order $12$). Since $6\mid12$, $\langle12\rangle\subseteq\langle6\rangle$: the intersection is $\langle12\rangle$, of order $6$, and the subgroup generated by both is $\langle6\rangle$, of order $12$.
4 $G=\bigcup_{a\in G}\langle a\rangle$. If some $\langle a\rangle$ were infinite it would be $\cong\mathbb{Z}$, which has infinitely many subgroups $m\mathbb{Z}$. So each $\langle a\rangle$ is finite, there are finitely many of them, and $G$ is a finite union of finite sets.
5 $27=3^3$: cyclic. $16=2^4$: not. $18=2\cdot3^2$: cyclic. $50=2\cdot5^2$: cyclic. In $U(18)=\{1,5,7,11,13,17\}$: $5,7,17,13,11,1$ are the powers of $5$, so $o(5)=6$ and $5$ is a generator.
6 Let $G=\langle a\rangle$ and $d=\gcd(m,n)$. $(a^k)^m=e\iff n\mid km\iff\tfrac nd\mid k$ (Euclid's lemma, as $\gcd(\tfrac nd,\tfrac md)=1$). In $\{0,\dots,n-1\}$ there are exactly $d$ multiples of $n/d$.
7 In $(\mathbb{Q},+)$ every element is a double: $x=\tfrac x2+\tfrac x2$. An isomorphism $\phi$ onto $(\mathbb{Q}_{\gt0},\times)$ would make every positive rational a square: $\phi(x)=\phi(\tfrac x2)^2$. But $2$ is not the square of a rational.
8 $\mathbb{C}^*$: exactly the $\mu_n$, $n\ge1$ (Theorem 6.13(2)). $\mathbb{R}^*$: a finite subgroup is some $\mu_n$ contained in $\mathbb{R}$, and $\mu_n\cap\mathbb{R}\subseteq\{\pm1\}$; so $\{1\}$ and $\{\pm1\}$.
IV
Cosets, Lagrange and $HK$.
  • 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]$.
1 Left: $H=\{e,(1\,2)\}$, $(1\,3)H=\{(1\,3),(1\,2\,3)\}$, $(2\,3)H=\{(2\,3),(1\,3\,2)\}$. Right: $H$, $H(1\,3)=\{(1\,3),(1\,3\,2)\}$, $H(2\,3)=\{(2\,3),(1\,2\,3)\}$. Only $H$ itself is both.
2 A proper subgroup has order $1$, $3$ or $5$; groups of order $1$ or of prime order are cyclic (Theorem 6.12(2)).
3 If $G$ has an element of order $4$ it is cyclic, $\cong\mathbb{Z}_4$. Otherwise every $a\ne e$ has order $2$ (orders divide $4$), so $G$ is abelian (Theorem 6.6(2)); write $G=\{e,a,b,c\}$. Then $ab\ne e$ (else $b=a^{-1}=a$), $ab\ne a$, $ab\ne b$, so $ab=c$; similarly $bc=a$, $ca=b$: the table of $V_4$.
4 The left cosets are $H$ and $G\setminus H$, and so are the right cosets (two of them, by Theorem 6.10(5)); so $gH=Hg$ for all $g$. If $g\notin H$ and $g^2\notin H$, then $g^2\in gH$, so $g^2=gh$ and $g=h\in H$: contradiction.
5 Order $1$: $\{e\}$. Order $2$: three, $\langle(1\,2)(3\,4)\rangle$ etc. Order $3$: four, $\langle(1\,2\,3)\rangle,\langle(1\,2\,4)\rangle,\langle(1\,3\,4)\rangle,\langle(2\,3\,4)\rangle$ (eight $3$-cycles, two per subgroup). Order $4$: one, $V=\{e,(1\,2)(3\,4),(1\,3)(2\,4),(1\,4)(2\,3)\}$ (a subgroup of order $4$ has no element of order $3$, so it consists of $e$ and the three double transpositions). Order $6$: none (Example 6). Order $12$: $A_4$. Total $10$.
6 $|H\cap K|$ divides $\gcd(10,15)=5$, and $\tfrac{150}{|H\cap K|}=|HK|\le60$ forces $|H\cap K|\ge3$. So $|H\cap K|=5$ and $|HK|=30$. Example: $\mathbb{Z}_{60}$ with $H=\langle6\rangle$, $K=\langle4\rangle$: $H\cap K=\langle12\rangle$ has order $5$ and $H+K=\langle2\rangle$ has order $30$.
7 As in Example 7(c): two distinct subgroups of order $p$ meet trivially and give $|PQ|=p^2\gt|G|$. So a group of order $21$ has at most one subgroup of order $7$ ($49\gt21$).
8 $\varphi(28)=12$ and $100=8\cdot12+4$, so $3^{100}\equiv3^4=81\equiv25\pmod{28}$.
9 By the tower law $[G:H\cap K]=[G:H][H:H\cap K]$, so $[G:H]$ divides $[G:H\cap K]$; so does $[G:K]$; being coprime, their product divides it. On the other hand $|HK|=\tfrac{|H||K|}{|H\cap K|}\le|G|$ gives $[G:H\cap K]=\tfrac{|G|}{|H\cap K|}\le\tfrac{|G|^2}{|H||K|}=[G:H][G:K]$. Hence equality, and then $|HK|=|G|$, i.e. $G=HK$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

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)$.

Idea $U(n)$ is cyclic iff $n=1,2,4,p^k,2p^k$ (Theorem 6.14); a quick disproof is two different square roots of $1$ other than $1$.
Options (A) $16=2^4$: $7^2=49\equiv1$ and $15^2\equiv1$ — not cyclic. (B) $20=4\cdot5$: $9^2=81\equiv1$ and $19^2\equiv1$ — not cyclic. (C) $54=2\cdot3^3$: cyclic (indeed $5$ is a generator, of order $18=\varphi(54)$). (D) $15=3\cdot5$: $4^2\equiv1$ and $14^2\equiv1$ — not cyclic.
Answer (C).

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$.

Idea Count rotations and reflections separately.
Count Rotations $r^k$ have order $8/\gcd(8,k)$, which is $2$ only for $k=4$: one element. All $8$ reflections $r^ks$ have order $2$. Total $1+8=9$ — an odd number, as Theorem 6.6 demands.
Answer (C). (Forgetting the half-turn $r^4$ gives the trap (B).)

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$.

Idea $\langle a\rangle\cap\langle b\rangle$ has order dividing $\gcd(6,10)=2$. Look at the $3$-part and the $5$-part separately.
Bounds $o(ab)\mid30$. $(ab)^{10}=a^{10}b^{10}=a^4\ne e$, so $3\mid o(ab)$; $(ab)^6=a^6b^6=b^6\ne e$, so $5\mid o(ab)$. Hence $o(ab)\in\{15,30\}$, which rules out (A)–(C).
Realised In $\mathbb{Z}_{30}$, $a=5$ has order $6$, $b=3$ has order $10$, and $a+b=8$ has order $30/\gcd(30,8)=15$. (Here $\langle a\rangle\cap\langle b\rangle=\{0,15\}$; when the intersection is trivial, as for $(1,0)$ and $(0,1)$ in $\mathbb{Z}_6\times\mathbb{Z}_{10}$ of §6.2, the order is $30$.)
Answer (D).

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$.

(A) True Theorem 6.12(2).
(B) False $V_4$ (or $S_3$, $Q_8$): all proper subgroups cyclic, the group is not.
(C) True $|G|$ is even, so there is $a$ of order $2$ (Theorem 6.6). If no element had order $3$ or $6$, every element would satisfy $x^2=e$, and for $b\notin\{e,a\}$ the set $\{e,a,b,ab\}$ would be a subgroup of order $4\nmid6$. So there is $c$ of order $3$ (if $o(c)=6$, use $c^2$), and $o(ac)=6$ by Theorem 6.5(4).
(D) False If $|G|$ is odd there are none (orders divide $|G|$); if $|G|$ is even there is an odd number (Theorem 6.6).
Answer (A) and (C).

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$.

(A) False $U(8)\cong V_4$ is not cyclic; $U(2^k)$ is cyclic only for $k\le2$.
(B) True A finite subgroup of the multiplicative group of the field $\mathbb{Z}_p$ (Theorem 6.13(2)).
(C) True $\overline{-1}=\overline{n-1}$ satisfies $(-1)^2=1$ and $-1\not\equiv1\pmod n$ when $n\ge3$.
(D) True By (C) and Lagrange, $2$ divides $|U(n)|=\varphi(n)$.
Answer (B), (C) and (D).

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\}$.

(A) True Theorem 6.4(2).
(B) False $\langle(1\,2)\rangle\langle(1\,3)\rangle$ in $S_3$ has $4$ elements.
(C) True $|H\cap K|$ divides $\gcd(7,11)=1$.
(D) True $|H||K|\gt|G|\ge|HK|=|H||K|/|H\cap K|$, so $|H\cap K|\gt1$ (Theorem 6.15).
Answer (A), (C) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  2. 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.
  3. 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–Teaching NexusResearch-tutored · optional, about 45 minutes

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.

  1. 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)).
  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$.
  3. 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$.
  4. 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.

Instructor note: for $p=23$ (a safe prime, $q=11$) the generators are the $\varphi(22)=10$ elements $5,7,10,11,14,15,17,19,20,21$, and the least generator is $5$; for $p=41$ the least generator is $6$; the least generator modulo $p$ is $2$ for $p=3,5,11,13,19,29,37,53,59,61,67,83,\dots$. Among primes below $500$ the smallest proportion $\varphi(p-1)/(p-1)$ occurs at $p=211$ and $p=421$, where $p-1$ has the prime factors $2,3,5,7$ and the proportion is $\tfrac12\cdot\tfrac23\cdot\tfrac45\cdot\tfrac67=\tfrac{8}{35}\approx0.229$.

🧪 Self-check quiz

0/5 correct

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