Formula & theorem reference

B \subset A is false only when B contains some element that A lacks. Take B = \varnothing: it contains no elements at all, so there is nothing it could possibly contain that A doesn't also contain. The condition for B \subset A to fail can never be met, so \varnothing \subset A holds automatically — for every set A, including A = \varnothing itself.

Existence. Define f^{-1}(b) for b \in B as follows: since f is onto, some a \in A satisfies f(a) = b; since f is one-to-one, that a is the only one. So b \mapsto a is a well-defined rule, and it is total since every b \in B has such an a. Call this rule f^{-1}. By construction f(f^{-1}(b)) = f(a) = b, and f^{-1}(f(a)) = f^{-1}(b) = a.

Uniqueness. Suppose h: B \to A is another function with h(f(a)) = a for every a and f(h(b)) = b for every b. Fix b \in B and let a = f^{-1}(b), so f(a) = b. Then h(b) = h(f(a)) = a = f^{-1}(b). Since b was arbitrary, h = f^{-1}.

Two things must be shown: g \circ f is one-to-one, and g \circ f is onto.

One-to-one. Suppose (g\circ f)(a_1) = (g\circ f)(a_2), i.e. g(f(a_1)) = g(f(a_2)). Since g is one-to-one, this forces f(a_1) = f(a_2). Since f is one-to-one, this forces a_1 = a_2. So g\circ f sends distinct inputs to distinct outputs.

Onto. Let c \in C be arbitrary. Since g is onto, there is some b \in B with g(b) = c. Since f is onto, there is some a \in A with f(a) = b. Then (g\circ f)(a) = g(f(a)) = g(b) = c, so every c \in C is hit.

Both properties hold, so g \circ f is a bijection.

Every a\in A satisfies a\sim a by reflexivity, so a\in[a] and the classes cover A. Suppose two classes [a] and [b] share an element c, so c\sim a and c\sim b. By symmetry a\sim c, and by transitivity a\sim c and c\sim b give a\sim b. Then for any x\in[a], x\sim a and a\sim b give x\sim b, so x\in[b], and the same argument in reverse gives [b]\subseteq[a]. Hence [a]=[b]: two classes that share even one element are the same class, so distinct classes never overlap. Combined with the classes covering A, this makes the collection of distinct classes a partition of A.

Reflexivity: every x\in A lies in whichever block contains it, so x shares that block with itself, giving x\sim x. Symmetry: if x and y share a block, that same fact says y and x share a block, so x\sim y implies y\sim x. Transitivity: if x,y share block A_i and y,z share block A_j, then y lies in both A_i and A_j; since the blocks of a partition are pairwise disjoint, A_i=A_j, so x and z share that same block and x\sim z. Thus \sim is an equivalence relation. For any x\in A_i, an element y satisfies x\sim y exactly when y\in A_i too, so the equivalence class [x] is precisely the block A_i containing x.

This principle isn't derived from something more basic in this course — it's taken as one of the foundational properties of the integers themselves (equivalent to the well-ordering principle: every nonempty set of integers bounded below has a least element, a fact from set theory this course doesn't build). The domino-chain intuition is a genuine guide to why it's believable — P(n_0) is true, and the inductive step means each true case knocks over the next one — but making that intuition airtight for infinitely many dominoes is exactly what the well-ordering principle supplies, and that belongs to a foundations-of-mathematics course, not this one. It's used freely here because every course that reaches integers uses it freely.

Rather than taking this as a second, separate axiom alongside the Principle of Mathematical Induction, it can be built from that ordinary principle directly — the only genuinely new idea is what statement to induct on.

Given P(n) satisfying strong induction's two hypotheses, define a new statement Q(n): "P(n_0), P(n_0+1), \ldots, P(n) are all true." Q(n_0) holds because that's exactly the base case. And if Q(k) holds — every one of P(n_0) through P(k) is true — then the strong inductive step says P(k+1) is true too, so Q(k+1) (everything through P(k+1)) holds as well. That's the base case and inductive step of the ordinary Principle of Mathematical Induction, applied to Q instead of P — so Q(n) is true for every n \ge n_0. Since Q(n) includes P(n) as one of its conjuncts, P(n) is true for every n \ge n_0 too.

This principle is taken as a foundational property of the natural numbers, not derived from something more basic in this course — it is equivalent to the Principle of Mathematical Induction, and either one can be taken as the starting axiom with the other proved from it.

Sketch of the equivalence. Suppose the Principle of Mathematical Induction holds, and let S be a nonempty set of natural numbers with no least element. Let P(n) be the statement "0, 1, \ldots, n are all not in S." P(0) holds, since if 0 \in S it would trivially be the least element. If P(k) holds (none of 0 through k are in S) and k+1 \in S, then k+1 would be S's least element, contradicting the assumption — so k+1 \notin S either, giving P(k+1). By induction, P(n) holds for every n, meaning no natural number is ever in S — contradicting S nonempty. So every nonempty S must have a least element after all.

Existence. Consider the set of nonnegative integers of the form a - bk for integer k: \{\ldots, a-2b,\ a-b,\ a,\ a+b,\ a+2b,\ \ldots\} \cap \{0, 1, 2, \ldots\}. This set is nonempty — for k negative enough, a-bk grows without bound in the positive direction — so by the well-ordering principle it has a least element; call it r, achieved at some k=q, so r = a-bq, i.e. a = bq+r. If r \ge b, then r-b = a-b(q+1) \ge 0 would be a smaller nonnegative element of the same set, contradicting that r was least. So 0 \le r < b.

Uniqueness. Suppose a = bq_1+r_1 = bq_2+r_2 with both remainders in [0,b). Subtracting gives b(q_1-q_2) = r_2-r_1, so b divides r_2-r_1. But -b < r_2-r_1 < b, and the only multiple of b strictly between -b and b is 0, so r_1=r_2, which forces q_1=q_2 as well.

Existence. Consider the set of nonnegative integers of the form a - bk for integer k: \{\ldots, a-2b,\ a-b,\ a,\ a+b,\ a+2b,\ \ldots\} \cap \{0, 1, 2, \ldots\}. This set is nonempty — for k negative enough, a-bk grows without bound in the positive direction — so by the well-ordering principle it has a least element; call it r, achieved at some k=q, so r = a-bq, i.e. a = bq+r. If r \ge b, then r-b = a-b(q+1) \ge 0 would be a smaller nonnegative element of the same set, contradicting that r was least. So 0 \le r < b.

Uniqueness. Suppose a = bq_1+r_1 = bq_2+r_2 with both remainders in [0,b). Subtracting gives b(q_1-q_2) = r_2-r_1, so b divides r_2-r_1. But -b < r_2-r_1 < b, and the only multiple of b strictly between -b and b is 0, so r_1=r_2, which forces q_1=q_2 as well.

Structure. The powers g^0, g^1, \ldots, g^{n-1} are the n distinct elements of G (established when cyclic groups were introduced), so k \mapsto g^k is a bijection from \{0, 1, \ldots, n-1\} onto G. Because g^n = e, multiplying two powers reduces the exponents mod n: g^i \cdot g^j = g^{i+j} = g^{(i+j) \bmod n}. That right-hand rule — add the exponents, then reduce mod n — is exactly \mathbb{Z}_n's own addition performed on i and j. So the bijection k \mapsto g^k turns every product in G into the matching sum in \mathbb{Z}_n: the two groups run on identical bookkeeping, only the labels on the elements differ. (Chapter 10 gives this precise notion of "same bookkeeping, different labels" a formal name — an isomorphism — and proves this fact as one case of a general theorem; nothing here depends on that later vocabulary, since the correspondence above can be checked by hand on any single finite cyclic group.)

Subgroups. Let H \le G. If H = \{e\}, it is cyclic (generated by e). Otherwise H contains some g^k with k \ne 0; since H is closed under inverses, it contains g^{-k} too, so H contains at least one positive power of g. By the well-ordering principle, let m be the smallest positive integer with g^m \in H. Claim: H = \langle g^m \rangle.

Certainly \langle g^m \rangle \subseteq H, since H is closed under the operation and contains g^m. For the reverse inclusion, take any g^k \in H. By the division algorithm, k = mq + r with 0 \le r < m. Then g^r = g^{k - mq} = g^k \cdot (g^m)^{-q} \in H, a product of two elements already known to be in H. Since m was chosen as the smallest positive exponent putting a power of g in H, and 0 \le r < m, the only way g^r \in H is r = 0. So k = mq, which means g^k = (g^m)^q \in \langle g^m \rangle. Hence H \subseteq \langle g^m \rangle as well, giving H = \langle g^m \rangle — cyclic, generated by g^m.

Work with n distinct indeterminates x_1,\ldots,x_n and set \Delta = \prod_{1 \le i < j \le n} (x_i - x_j). For any permutation \pi \in S_n, define \Delta_\pi = \prod_{1 \le i < j \le n} \bigl(x_{\pi(i)} - x_{\pi(j)}\bigr). \pi is a bijection on \{1,\ldots,n\}. So it matches each unordered pair \{i,j\} to a unique unordered pair \{\pi(i),\pi(j)\}. \Delta_\pi is therefore built from exactly the same factors as \Delta, each appearing once, up to sign. Hence \Delta_\pi = \pm \Delta for every \pi. In particular, \Delta_e = \Delta for the identity.

Key lemma: composing with one transposition always flips the sign. Fix \pi \in S_n and a transposition \tau = (a\ b) with a < b, and let \rho = \pi \circ \tau, so \rho(a) = \pi(b), \rho(b) = \pi(a), and \rho(k) = \pi(k) for every other k. Split \Delta_\rho's factors into three groups and compare each to the matching group in \Delta_\pi:

• Pairs \{i,j\} with i,j \notin \{a,b\}: \rho and \pi agree there, so these factors are identical in \Delta_\rho and \Delta_\pi.
• The pair \{a,b\} itself: its factor in \Delta_\pi is (x_{\pi(a)} - x_{\pi(b)}); in \Delta_\rho it becomes (x_{\rho(a)} - x_{\rho(b)}) = (x_{\pi(b)} - x_{\pi(a)}), exactly -1 times the \Delta_\pi factor.
• Pairs \{i,a\} and \{i,b\} for some other index i: whichever of a,b is larger than i (or smaller) is the same fact on both sides, since only a's and b's images swapped, not their positions relative to i. The two factors these pairs contribute in \Delta_\pi are (x_{\pi(i)}-x_{\pi(a)}) and (x_{\pi(i)}-x_{\pi(b)}) (in whichever order the indices demand); in \Delta_\rho the same two pairs contribute (x_{\pi(i)}-x_{\pi(b)}) and (x_{\pi(i)}-x_{\pi(a)}) — the same two factors, only swapped with each other. Their product is unchanged.

Multiplying all three groups together, every factor matches except the single \{a,b\} factor, which flipped sign. So \Delta_{\pi \circ \tau} = -\Delta_\pi for every \pi and every transposition \tau.

Assembling a decomposition. Suppose \sigma = \tau_1 \circ \tau_2 \circ \cdots \circ \tau_k. Build the partial products e_0 = e (the identity) and e_i = e_{i-1} \circ \tau_i for i=1,\ldots,k, so e_k = \sigma. The lemma applies at each step: \Delta_{e_i} = -\Delta_{e_{i-1}}. Chaining all k steps from \Delta_{e_0} = \Delta_e = \Delta gives \Delta_\sigma = \Delta_{e_k} = (-1)^k \Delta.

The left-hand side, \Delta_\sigma, is computed directly from \sigma itself — it makes no reference to \tau_1,\ldots,\tau_k or to how many of them there were. So the ratio \Delta_\sigma / \Delta \in \{+1,-1\} is a fixed number once \sigma is fixed, and the equation above says that number equals (-1)^k for any decomposition of \sigma into k transpositions. Two decompositions of the same \sigma, using k and k' transpositions respectively, therefore satisfy (-1)^k = (-1)^{k'}, which forces k and k' to have the same parity.

Define \operatorname{sgn}(\sigma) = \Delta_\sigma/\Delta. A permutation is called even when \operatorname{sgn}(\sigma)=+1 and odd when \operatorname{sgn}(\sigma)=-1; by the argument above, every decomposition of \sigma into transpositions uses an even number of them when \sigma is even, and an odd number when \sigma is odd — never a mix.

Setup. Every element of D_n is uniquely r^k (a rotation) or r^k s (a reflection), for some k \in \{0,1,\ldots,n-1\}. So there are exactly 2n symmetries to check. Write down the permutation each one induces on the vertex labels. Rotating by k steps sends vertex i to whichever label sits k positions further around the ring. Reflecting across the fixed axis through vertex 1, then rotating by k, sends vertex i to the label k positions past vertex 1's mirror image of i. Work in mod-n arithmetic on the labels 0,\ldots,n-1, with label i standing for vertex i+1. This gives exactly \rho_k(i) = i + k \pmod n \qquad\text{and}\qquad \sigma_k(i) = k - i \pmod n.

The match is one-to-one. Two rotations \rho_j and \rho_k agree as permutations exactly when i+j \equiv i+k \pmod n for every i. That forces j \equiv k \pmod n. So the n rotations are pairwise distinct permutations. The same argument shows the n reflections \sigma_k are pairwise distinct too. What remains is ruling out a rotation ever matching a reflection. Suppose \rho_j = \sigma_k as permutations. Then i + j \equiv k - i \pmod n for every i at once. Compare this equation at i and at i+1. The left side increases by exactly 1 (mod n). The right side decreases by exactly 1 (mod n). Both can't hold for every i: incrementing i by 1 would have to change the shared value by both +1 and -1 \pmod n at once, which forces n \mid 2. That's impossible once n \ge 3. So no rotation induces the same permutation as any reflection, and all 2n induced permutations are distinct. The map D_n \to S_n is therefore one-to-one.

Composition matches composition. This follows straight from how the permutations were built. Each one directly records, vertex by vertex, where that symmetry sends every label. Performing symmetry g and then symmetry h moves vertex i exactly where h's permutation sends g's permutation's image of i. The combined motion and the combined permutation track the identical sequence of label changes, by construction.

Conclusion. The 2n permutations obtained this way are closed under composition: composing two of them gives the permutation of another symmetry in D_n, which is itself one of the 2n. They contain the identity permutation. They contain each other's inverses too, since undoing a symmetry undoes its permutation. That's exactly the subgroup test from chapter 2, applied inside S_n. Combined with the one-to-one match above, D_n is a subgroup of S_n of order 2n — not just a group that happens to resemble one. Chapter 10 gives this precise idea a formal name: the same group, realized inside a bigger one, with composition matching exactly, is called an isomorphism onto its image. It also proves a general statement, due to Cayley, that every finite group embeds in some S_n this same way. Nothing here depends on those later terms. The one-to-one match above, which also preserves composition, can be checked by hand for any single D_n.

Structure. The powers g^0, g^1, \ldots, g^{n-1} are the n distinct elements of G (established when cyclic groups were introduced), so k \mapsto g^k is a bijection from \{0, 1, \ldots, n-1\} onto G. Because g^n = e, multiplying two powers reduces the exponents mod n: g^i \cdot g^j = g^{i+j} = g^{(i+j) \bmod n}. That right-hand rule — add the exponents, then reduce mod n — is exactly \mathbb{Z}_n's own addition performed on i and j. So the bijection k \mapsto g^k turns every product in G into the matching sum in \mathbb{Z}_n: the two groups run on identical bookkeeping, only the labels on the elements differ. (Chapter 10 gives this precise notion of "same bookkeeping, different labels" a formal name — an isomorphism — and proves this fact as one case of a general theorem; nothing here depends on that later vocabulary, since the correspondence above can be checked by hand on any single finite cyclic group.)

Subgroups. Let H \le G. If H = \{e\}, it is cyclic (generated by e). Otherwise H contains some g^k with k \ne 0; since H is closed under inverses, it contains g^{-k} too, so H contains at least one positive power of g. By the well-ordering principle, let m be the smallest positive integer with g^m \in H. Claim: H = \langle g^m \rangle.

Certainly \langle g^m \rangle \subseteq H, since H is closed under the operation and contains g^m. For the reverse inclusion, take any g^k \in H. By the division algorithm, k = mq + r with 0 \le r < m. Then g^r = g^{k - mq} = g^k \cdot (g^m)^{-q} \in H, a product of two elements already known to be in H. Since m was chosen as the smallest positive exponent putting a power of g in H, and 0 \le r < m, the only way g^r \in H is r = 0. So k = mq, which means g^k = (g^m)^q \in \langle g^m \rangle. Hence H \subseteq \langle g^m \rangle as well, giving H = \langle g^m \rangle — cyclic, generated by g^m.

(Direct/constructive.) The left cosets of H partition G: fix a full list of distinct left cosets g_1H, g_2H, \ldots, g_kH (already shown to be pairwise disjoint and exhaustive, since "same coset" is an equivalence relation on G). Each coset g_iH has exactly |H| elements, since h \mapsto g_ih is a bijection from H to g_iH (injective: g_ih_1=g_ih_2 \Rightarrow h_1=h_2 by left-cancellation; surjective by the coset's own definition). Summing the sizes of the k pairwise disjoint cosets that together make up all of G: |G| = \underbrace{|H| + |H| + \cdots + |H|}_{k \text{ times}} = k \cdot |H|. By definition k = [G:H], giving |G| = [G:H]\cdot|H|; in particular |H| divides |G|.

Let g \in G with g \ne e, and let H = \langle g \rangle be the cyclic subgroup it generates. Since g \ne e, |H| \ge 2. By Lagrange's theorem, |H| divides |G|=p; since p is prime, its only divisors are 1 and p, and |H|\ge2 rules out 1. So |H| = p = |G|, and a subgroup with the same size as the whole (finite) group must equal it: H = G. So \langle g \rangle = G -- g generates all of G, for every choice of non-identity g.

\gcd(a,n)=1 means the residue of a mod n is a unit, i.e. an element of U(n) (group-theory chapter 3), a group of order \varphi(n) under multiplication mod n. Let m = |a| be a's order as an element of U(n) -- the smallest positive integer with a^m \equiv 1 \pmod n. The cyclic subgroup \langle a \rangle \le U(n) generated by a has exactly m elements (a^0=1,a^1,\ldots, a^{m-1}, all distinct by minimality of m, and a^m=1 closes the list). By Lagrange's theorem applied to U(n), m = |\langle a\rangle| divides |U(n)| = \varphi(n); write \varphi(n) = mq for an integer q. Then a^{\varphi(n)} = a^{mq} = (a^m)^q \equiv 1^q = 1 \pmod n.

Direct corollary of Euler's theorem. When p is prime, \varphi(p) = p-1 (every integer from 1 to p-1 is coprime to p, since p has no divisors besides 1 and itself). If p \nmid a, then \gcd(a,p)=1, so Euler's theorem gives a^{\varphi(p)} = a^{p-1} \equiv 1 \pmod p; multiplying both sides by a gives a^p \equiv a \pmod p. If p \mid a, then a \equiv 0 \pmod p, so both sides of a^p\equiv a reduce to 0 \equiv 0, true trivially. Either way, a^p \equiv a \pmod p for every integer a.

Direct. Let g \in G and h \in H be arbitrary. Since G is abelian, gh = hg, so ghg^{-1} = hgg^{-1} = h. Every conjugate of an element of H by any g \in G is that same element of H, unchanged. Hence gHg^{-1} = H for every g \in G, which is exactly the definition of normality.

Direct, using left and right cosets. Since [G:H]=2, G splits into exactly two left cosets. One of them is H itself (eH=H); since the two left cosets partition G and are disjoint, the other one must be exactly the complement G \setminus H. The identical argument for right cosets shows G also splits into exactly the two right cosets H and G \setminus H.

Now check gH=Hg for every g \in G. If g \in H, then gH = H = Hg (closure). If g \notin H, then gH is the OTHER left coset (it cannot equal H, since g \in gH but g \notin H), so gH = G \setminus H -- and by the identical reasoning, Hg = G \setminus H too. Either way gH = Hg, so H \trianglelefteq G.

Direct. Let g \in G and z \in Z(G). By definition of the center, z commutes with every element of G, so in particular zg = gz, giving gzg^{-1} = zgg^{-1} = z. So every conjugate of an element of Z(G) is that same element, and gZ(G)g^{-1} = Z(G) for every g \in G.

\overline f is well-defined. If g_1\ker(f) = g_2\ker(f) (the same coset), then g_1^{-1}g_2 \in \ker(f), so f(g_1^{-1}g_2) = e_H, giving f(g_1)^{-1}f(g_2) = e_H and hence f(g_1) = f(g_2) — the output doesn't depend on which coset representative was chosen.

\overline f is a homomorphism. Immediate from f's own homomorphism property: \overline f\big((g_1\ker f)(g_2\ker f)\big) = \overline f\big((g_1g_2)\ker f\big) = f(g_1g_2) = f(g_1)f(g_2) = \overline f(g_1\ker f)\,\overline f(g_2\ker f).

\overline f is one-to-one. Suppose \overline f(g\ker f) = e_H. Then f(g) = e_H, so g \in \ker(f), so g\ker(f) is the identity element of G/\ker(f) (the coset \ker(f) itself). A homomorphism with trivial kernel is injective (the kernel criterion), so \overline f is one-to-one.

\overline f is onto \operatorname{im}(f). Every element of \operatorname{im}(f) is f(g) for some g \in G, and \overline f(g\ker f) = f(g) by definition — so every element of \operatorname{im}(f) is hit.

A homomorphism that is both one-to-one and onto is an isomorphism, so G/\ker(f) \cong \operatorname{im}(f). \blacksquare

A corollary for finite groups. When G is finite, Lagrange's theorem gives |G/\ker(f)| = |G|/|\ker(f)|, and the isomorphism just proved forces |G/\ker(f)| = |\operatorname{im}(f)|. Combining these: |G| = |\ker(f)| \cdot |\operatorname{im}(f)| — a finite homomorphism's domain size always splits exactly into how much collapses (the kernel) times how much survives (the image).

Since N \trianglelefteq G, hN = Nh for every h \in H, so HN = NH; chapter 6's own criterion for a product of two subgroups being a subgroup then makes HN \le G.

Let \pi: G \to G/N be the natural quotient map, and restrict it to H: \varphi: H \to G/N, \varphi(h) = hN. Restricting a homomorphism to a subgroup of its domain is still a homomorphism.

\ker(\varphi) = \{h \in H : hN = N\} = \{h \in H : h \in N\} = H \cap N, so the First Isomorphism Theorem's own kernel-normality fact gives H \cap N \trianglelefteq H directly, with no separate conjugation check.

\operatorname{im}(\varphi) = \{hN : h \in H\} = HN/N: every element of HN has the form hn for h \in H, n \in N, and hnN = hN since n \in N.

Applying the First Isomorphism Theorem to \varphi: H/\ker(\varphi) \cong \operatorname{im}(\varphi) \quad\Longrightarrow\quad H/(H\cap N) \cong HN/N. \qquad \blacksquare

A counting corollary. For finite H, N: applying Lagrange's theorem to both sides gives |H|/|H\cap N| = |HN|/|N|, so |HN| = \frac{|H|\cdot|N|}{|H\cap N|}.

Define \varphi: G/N \to G/M by \varphi(gN) = gM.

Well-defined. If g_1N = g_2N, then g_1^{-1}g_2 \in N; since N \subseteq M, g_1^{-1}g_2 \in M too, so g_1M = g_2M.

Homomorphism. \varphi\big((g_1N)(g_2N)\big) = \varphi\big((g_1g_2)N\big) = (g_1g_2)M = (g_1M)(g_2M), directly from how both quotient operations are defined.

Surjective. Every coset gM \in G/M equals \varphi(gN) for that same g.

\ker(\varphi) = M/N. \varphi(gN) = M (the identity of G/M) exactly when gM = M, i.e. g \in M — so \ker(\varphi) is exactly the cosets gN with g \in M, which is M/N. The First Isomorphism Theorem's kernel-normality fact then gives M/N \trianglelefteq G/N automatically.

Applying the First Isomorphism Theorem to \varphi: (G/N)/\ker(\varphi) \cong \operatorname{im}(\varphi) \quad\Longrightarrow\quad (G/N)/(M/N) \cong G/M. \qquad \blacksquare

Two general facts about any homomorphism f: G \to H. If K \le G, then f(K) is a subgroup of H (the same closure/ identity/inverse argument as \operatorname{im}(f) itself, restricted to K). If L \le H, then f^{-1}(L) = \{g \in G : f(g) \in L\} is a subgroup of G: it contains e_G (since f(e_G) = e_H \in L); it's closed (if f(g_1), f(g_2) \in L then f(g_1g_2) = f(g_1)f(g_2) \in L); and it contains inverses (if f(g) \in L then f(g^{-1}) = f(g)^{-1} \in L).

Applying both to \pi: G \to G/N. For K \le G with N \subseteq K, \pi(K) = K/N \le G/N. For L \le G/N, \pi^{-1}(L) \le G, and it contains N automatically: L contains G/N's identity coset N, and \pi^{-1}(N) = N.

Mutually inverse. \pi\big(\pi^{-1}(L)\big) = L for any L \le G/N, since \pi is surjective. \pi^{-1}\big(\pi(K)\big) = K needs N \subseteq K: if g \in \pi^{-1}(\pi(K)), then gN = kN for some k \in K, so g = kn for some n \in N \subseteq K, giving g = kn \in K since K is closed. So K \mapsto K/N and L \mapsto \pi^{-1}(L) undo each other exactly, giving a genuine bijection.

Inclusion. K_1 \subseteq K_2 (both containing N) exactly when K_1/N \subseteq K_2/N, directly from how cosets of the same N nest.

Index. [G:K] = [G/N:K/N], since the cosets of K in G correspond exactly, one for one, to the cosets of K/N in G/N.

Normality. (gN)(K/N)(gN)^{-1} = (gKg^{-1})N/N, which equals K/N for every g \in G exactly when gKg^{-1} = K for every g \in G — so K \trianglelefteq G iff K/N \trianglelefteq G/N. \blacksquare

Direct computation from the definition of the product operation. Since (g,h) is combined componentwise, (g,h)^k = (g^k, h^k) for every integer k \ge 1. So (g,h)^k = (e_G, e_H) \iff g^k = e_G \text{ and } h^k = e_H \iff m \mid k \text{ and } n \mid k, using that an element's order divides exactly the exponents that return it to the identity. The condition "m \mid k and n \mid k" says k is a common multiple of m and n; the smallest positive integer satisfying it is, by definition, \operatorname{lcm}(m,n). So the smallest positive k with (g,h)^k=(e_G,e_H) is \operatorname{lcm}(m,n) — exactly |(g,h)|.

Both directions lean on the previous formula card: |(a,b)| = \operatorname{lcm}(|a|,|b|).

(\Leftarrow) Suppose \gcd(m,n)=1. Let g=(1,1) \in \mathbb{Z}_m \times \mathbb{Z}_n, where 1 is a generator of each factor, so |1|=m in \mathbb{Z}_m and |1|=n in \mathbb{Z}_n. Then |(1,1)| = \operatorname{lcm}(m,n) = \frac{mn}{\gcd(m,n)} = mn, using the identity \operatorname{lcm}(m,n)\cdot\gcd(m,n)=mn (this chapter's own section 2). An element whose order equals the size of the whole group generates the whole group, so \mathbb{Z}_m \times \mathbb{Z}_n = \langle (1,1) \rangle is cyclic, of order mn — hence isomorphic to \mathbb{Z}_{mn} by the classification of finite cyclic groups (chapter 3).

(\Rightarrow) Suppose \gcd(m,n)=d>1. Take any (a,b) \in \mathbb{Z}_m \times \mathbb{Z}_n. By Lagrange's theorem (chapter 7), |a| divides m and |b| divides n, so \operatorname{lcm}(|a|,|b|) divides \operatorname{lcm}(m,n) = mn/d. Every element of \mathbb{Z}_m \times \mathbb{Z}_n therefore has order at most mn/d, which is strictly less than mn since d>1. No element reaches order mn, so no element generates the whole group, and \mathbb{Z}_m \times \mathbb{Z}_n is not cyclic.

Elements of H and K commute. For h \in H, k \in K, look at the commutator hkh^{-1}k^{-1}. Grouping it as (hkh^{-1})k^{-1}: since K \trianglelefteq G, hkh^{-1} \in K, so the whole product is in K. Grouping it instead as h(kh^{-1}k^{-1}): since H \trianglelefteq G, kh^{-1}k^{-1} \in H, so the whole product is also in H. An element in both H and K is in H \cap K = \{e\} by hypothesis 2, so hkh^{-1}k^{-1}=e, which rearranges to hk=kh.

Every element of G has a unique hk representation. Hypothesis 3 gives existence. For uniqueness, suppose h_1k_1 = h_2k_2 with h_1,h_2 \in H, k_1,k_2 \in K. Then h_2^{-1}h_1 = k_2k_1^{-1}; the left side is in H, the right side is in K, so both sides lie in H \cap K = \{e\}. Hence h_1=h_2 and k_1=k_2.

The map \varphi: H \times K \to G, \varphi(h,k) = hk, is an isomorphism. Well-defined and surjective: immediate from hypothesis 3. Injective: immediate from the uniqueness just shown. Homomorphism: using that H- and K-elements commute (first part of this proof), \varphi\big((h_1,k_1)(h_2,k_2)\big) = \varphi(h_1h_2, k_1k_2) = h_1h_2k_1k_2 = h_1k_1h_2k_2 = \varphi(h_1,k_1)\varphi(h_2,k_2). A bijective homomorphism is an isomorphism, so G \cong H \times K.

Cited in outline. This is one of the deepest results a first course in group theory reaches, so only its shape is given here. Chapter 3's classification-of-finite-cyclic-groups theorem took this same posture toward isomorphism, before chapter 10 built it formally.

Reducing to one prime at a time. Every finite abelian group G of order n = p_1^{e_1} \cdots p_r^{e_r} splits as an internal direct product of subgroups G \cong G_{p_1} \times G_{p_2} \times \cdots \times G_{p_r}, one for each prime dividing n, with |G_{p_i}| = p_i^{e_i}. This is the abelian case of a fact called "Sylow subgroups," proven in full generality in a second course in abstract algebra. Granting that split, classifying finite abelian groups reduces to a single question: classify every abelian group of order p^e, for one prime p at a time.

One prime at a time. A finite abelian group of order p^e is itself isomorphic to a direct product of cyclic p-groups \mathbb{Z}_{p^{a_1}} \times \cdots \times \mathbb{Z}_{p^{a_j}}, with a_1 + \cdots + a_j = e. This is proven by induction on |G|: at each step, peel off one cyclic factor generated by an element of maximal order, then show what remains is again a smaller abelian p-group. The induction is routine once set up, but long, and is not reproduced here.

Uniqueness. Two such factorizations are isomorphic only if their multisets of prime-power factors agree exactly. This follows by counting, for each possible order d, how many elements of order d each side has. Using this chapter's own \operatorname{lcm} order formula, a \operatorname{lcm} of prime-power factors is sensitive enough to the exact list of exponents that the counts only match when the factor lists do.

Section 7 shows how to use this theorem without redoing any of the above: turn the exponent e in p^e into a partition of e, and each distinct partition names one non-isomorphic abelian group of order p^e.

(Direct, via a bijection to cosets.) First, \operatorname{Stab}(x) is a subgroup of G: e \cdot x = x puts e in it; if g,h both fix x then (gh)\cdot x = g\cdot(h\cdot x) = g\cdot x = x, so it's closed; and g\cdot x=x forces x = g^{-1}\cdot x, so it contains every needed inverse.

Define a map \phi from the set of left cosets of \operatorname{Stab}(x) in G to \operatorname{Orb}(x) by \phi(g\operatorname{Stab}(x)) = g\cdot x.

Well-defined. If g\operatorname{Stab}(x) = h\operatorname{Stab}(x) then h^{-1}g \in \operatorname{Stab}(x), so (h^{-1}g)\cdot x = x; applying h to both sides and simplifying the left side via the action's own compatibility axiom, h\cdot((h^{-1}g)\cdot x) = (h h^{-1}g)\cdot x = g\cdot x, gives g\cdot x = h\cdot x. So the same coset always produces the same output.

Injective. Run the same equivalence backward: g\cdot x = h\cdot x \implies (h^{-1}g)\cdot x = x \implies h^{-1}g \in \operatorname{Stab}(x) \implies g\operatorname{Stab}(x) = h\operatorname{Stab}(x). Two different cosets never produce the same output.

Surjective. Every element of \operatorname{Orb}(x) is g\cdot x for some g \in G, by the orbit's own definition -- and that g's coset is exactly what \phi sends there.

\phi is therefore a bijection between the left cosets of \operatorname{Stab}(x) and \operatorname{Orb}(x), so [G:\operatorname{Stab}(x)] = |\operatorname{Orb}(x)|. Lagrange's theorem (chapter 7) gives |G| = |\operatorname{Stab}(x)| \cdot [G:\operatorname{Stab}(x)]; substituting the bijection's count in place of the index gives |G| = |\operatorname{Stab}(x)| \cdot |\operatorname{Orb}(x)|.

(Construction, then verify the three things an isomorphism onto its image needs: a homomorphism, injective, and its image sits inside \operatorname{Sym}(G).)

For each g \in G, define \lambda_g : G \to G by \lambda_g(x) = gx -- left multiplication by g. Each \lambda_g is a bijection from G to itself: \lambda_{g^{-1}} undoes it in both directions (\lambda_{g^{-1}}(\lambda_g(x)) = g^{-1}(gx) = x and symmetrically), so \lambda_g \in \operatorname{Sym}(G) for every g.

Define \varphi: G \to \operatorname{Sym}(G) by \varphi(g) = \lambda_g.

\varphi is a homomorphism. For any x \in G, \lambda_{gh}(x) = (gh)x = g(hx) = \lambda_g(\lambda_h(x)) = (\lambda_g \circ \lambda_h)(x), so \lambda_{gh} = \lambda_g \circ \lambda_h as functions, i.e. \varphi(gh) = \varphi(g)\varphi(h).

\varphi is injective. \lambda_g(e) = ge = g, so the single value \lambda_g(e) already recovers g. If \varphi(g) = \varphi(h), i.e. \lambda_g = \lambda_h as functions, then in particular \lambda_g(e) = \lambda_h(e), which says g = h. Distinct elements of G always produce distinct permutations.

An injective homomorphism is automatically an isomorphism onto its own image: \varphi: G \to \varphi(G) is a bijective homomorphism, since injectivity plus the definition of \varphi(G) as \varphi's image already gives surjectivity onto that image for free. So G \cong \varphi(G) \le \operatorname{Sym}(G).

When G is finite with |G| = n, labeling G's n elements 1, \ldots, n turns \operatorname{Sym}(G) into literally S_n, giving G \cong \varphi(G) \le S_n. The map \varphi -- G acting on itself by left multiplication -- is called the left regular representation of G.

The proof counts the set S = \{(g,x) \in G\times X : g\cdot x = x\} two different ways.

Row by row. Fix g first. The number of x\in X with g\cdot x=x is |\text{Fix}(g)|, by definition. Summing over every g\in G: |S| = \sum_{g\in G}|\text{Fix}(g)|.

Column by column. Fix x first instead. The number of g\in G with g\cdot x=x is |\text{Stab}(x)|, by definition. Summing over every x\in X: |S| = \sum_{x\in X}|\text{Stab}(x)|.

By the orbit-stabilizer theorem, |\text{Stab}(x)| = |G|/|\text{orbit}(x)| for every x\in X. Substituting and regrouping the sum by orbit: fix one orbit O with |O|=m elements. Each of those m elements x\in O contributes the identical term |G|/|\text{orbit}(x)| = |G|/m, so the whole orbit contributes m\cdot(|G|/m) = |G| to the sum -- exactly |G|, no matter which orbit or how large it is. Summing this one-|G|-per-orbit contribution across every orbit gives \sum_{x\in X}|\text{Stab}(x)| = |G|\cdot(\text{number of orbits}).

Both expressions count the same set S, so they're equal: \sum_{g\in G}|\text{Fix}(g)| = |G|\cdot(\text{number of orbits}). Dividing both sides by |G| gives the theorem exactly.

Sanity check: C_4 acting on 4-bead, 2-color colorings has |\text{Fix}(g)| values 16,2,4,2, summing to 24 = 4\times6 -- confirming 6 distinct orbits, matching a direct enumeration of this small case.

(Direct, via a bijection to cosets.) First, \operatorname{Stab}(x) is a subgroup of G: e \cdot x = x puts e in it; if g,h both fix x then (gh)\cdot x = g\cdot(h\cdot x) = g\cdot x = x, so it's closed; and g\cdot x=x forces x = g^{-1}\cdot x, so it contains every needed inverse.

Define a map \phi from the set of left cosets of \operatorname{Stab}(x) in G to \operatorname{Orb}(x) by \phi(g\operatorname{Stab}(x)) = g\cdot x.

Well-defined. If g\operatorname{Stab}(x) = h\operatorname{Stab}(x) then h^{-1}g \in \operatorname{Stab}(x), so (h^{-1}g)\cdot x = x; applying h to both sides and simplifying the left side via the action's own compatibility axiom, h\cdot((h^{-1}g)\cdot x) = (h h^{-1}g)\cdot x = g\cdot x, gives g\cdot x = h\cdot x. So the same coset always produces the same output.

Injective. Run the same equivalence backward: g\cdot x = h\cdot x \implies (h^{-1}g)\cdot x = x \implies h^{-1}g \in \operatorname{Stab}(x) \implies g\operatorname{Stab}(x) = h\operatorname{Stab}(x). Two different cosets never produce the same output.

Surjective. Every element of \operatorname{Orb}(x) is g\cdot x for some g \in G, by the orbit's own definition -- and that g's coset is exactly what \phi sends there.

\phi is therefore a bijection between the left cosets of \operatorname{Stab}(x) and \operatorname{Orb}(x), so [G:\operatorname{Stab}(x)] = |\operatorname{Orb}(x)|. Lagrange's theorem (chapter 7) gives |G| = |\operatorname{Stab}(x)| \cdot [G:\operatorname{Stab}(x)]; substituting the bijection's count in place of the index gives |G| = |\operatorname{Stab}(x)| \cdot |\operatorname{Orb}(x)|.

Let g \in G with g \ne e, and let H = \langle g \rangle be the cyclic subgroup it generates. Since g \ne e, |H| \ge 2. By Lagrange's theorem, |H| divides |G|=p; since p is prime, its only divisors are 1 and p, and |H|\ge2 rules out 1. So |H| = p = |G|, and a subgroup with the same size as the whole (finite) group must equal it: H = G. So \langle g \rangle = G -- g generates all of G, for every choice of non-identity g.

The argument has two stages: first show Z(G) can't be too small, then show Z(G) can't be a proper subgroup either.

Stage 1 -- Z(G) is nontrivial. Let G act on itself by conjugation (chapter 12), so its orbits are exactly the conjugacy classes (chapter 12, section 7). By the orbit-stabilizer theorem, the conjugacy class of g\in G has size [G:C_G(g)], where C_G(g) is the stabilizer of g under this action. Every subgroup of G has order dividing |G|=p^2 by Lagrange's theorem, so [G:C_G(g)] is 1, p, or p^2; it equals 1 exactly when g \in Z(G) (conjugating g by everything leaves it fixed), and otherwise it's at least p. Partitioning G into conjugacy classes and counting elements gives the class equation: |G| = |Z(G)| + \sum_i [G:C_G(g_i)], summed over one representative g_i of each conjugacy class of size >1. Every term in that sum is divisible by p (each is p or p^2), and |G|=p^2 is divisible by p, so |Z(G)| -- the leftover -- must also be divisible by p. Since Z(G) always contains e, |Z(G)|\ge1, and now p \mid |Z(G)| forces |Z(G)|\ge p.

Stage 2 -- Z(G) can't be a proper subgroup of order exactly p. By Lagrange, |Z(G)| divides p^2, so Stage 1 leaves two options: |Z(G)|=p^2 or |Z(G)|=p. Suppose toward a contradiction that |Z(G)|=p. Since Z(G) \trianglelefteq G always (chapter 8), the quotient G/Z(G) is a group of order p^2/p=p, hence cyclic (this chapter's own section 1) -- generated, say, by the coset gZ(G).

A cyclic quotient G/Z(G) forces G itself to be abelian: every coset of Z(G) is some power g^iZ(G), so every element of G has the form g^i z for some integer i and some z\in Z(G). Take two arbitrary elements g^iz_1 and g^jz_2 of G. Since z_1,z_2\in Z(G) commute with everything, (g^iz_1)(g^jz_2) = g^ig^jz_1z_2 = g^{i+j}z_1z_2 = g^jg^iz_2z_1 = (g^jz_2)(g^iz_1). So G is abelian -- but an abelian group's center is the whole group, Z(G)=G, contradicting |Z(G)|=p<p^2=|G|.

The contradiction rules out |Z(G)|=p, leaving |Z(G)|=p^2=|G|: Z(G)=G, i.e. G is abelian.

The two isomorphism types. Chapter 11's classification of finite abelian groups, applied to |G|=p^2, allows exactly two prime-power factorizations of the exponent 2: the single factor \mathbb{Z}_{p^2}, or the two-factor product \mathbb{Z}_p\times\mathbb{Z}_p. They aren't isomorphic to each other since only the first has an element of order p^2.

Cited in outline -- like chapter 11's classification of finite abelian groups, the full argument leans on machinery this course reaches only in the next two chapters, and only its shape is given here.

Why a subgroup of order q exists, and is normal. Cauchy's theorem (cited; a special case of the Sylow theory in chapter 15) guarantees G has an element of order q, hence a subgroup Q=\langle x\rangle of order q. Because q>p, Q has the smallest index above 1 that |G|=pq allows, namely p; chapter 15's Sylow theory shows a subgroup at that extreme is forced to be G's unique, hence normal, subgroup of its order. Cauchy's theorem also produces an element of order p, giving a second subgroup P of order p.

Building G from P and Q. Since Q \trianglelefteq G, P\cap Q=\{e\} (their orders share no common factor besides 1, by Lagrange), and |P||Q|=|G|, every element of G is a unique product qp with q\in Q, p\in P -- G is built from P and Q the way chapter 11's internal direct product builds a group from two subgroups, except here conjugation by P need not fix Q pointwise. What's left to pin down is exactly how conjugation by P acts on Q -- a homomorphism P \to \operatorname{Aut}(Q) (chapter 10's automorphism group) that chapter 16 studies as the data defining a semidirect product Q\rtimes P.

Counting the possibilities. \operatorname{Aut}(Q)\cong\operatorname{Aut}(\mathbb{Z}_q) is cyclic of order q-1 (a fact about a cyclic group's own automorphisms). A homomorphism from the order-p group P into this order-(q-1) group is either trivial -- giving the direct product \mathbb{Z}_q\times\mathbb{Z}_p \cong\mathbb{Z}_{pq}, cyclic because \gcd(p,q)=1 (this chapter's own direct-product tools from chapter 11) -- or, when p\mid(q-1), one specific nontrivial homomorphism up to relabeling P's generator, producing exactly one further isomorphism class, genuinely nonabelian since conjugation by P then acts on Q non-trivially. When p\nmid(q-1), no nontrivial homomorphism P\to\operatorname{Aut}(Q) exists at all (its image's order would have to divide both p and q-1, and \gcd(p,q-1)=1 in that case), so the trivial one is the only option and G\cong\mathbb{Z}_{pq} is forced.

Cited in outline. This is one of the deepest results a first course in group theory reaches, so only its shape is given here. Chapter 3's classification-of-finite-cyclic-groups theorem took this same posture toward isomorphism, before chapter 10 built it formally.

Reducing to one prime at a time. Every finite abelian group G of order n = p_1^{e_1} \cdots p_r^{e_r} splits as an internal direct product of subgroups G \cong G_{p_1} \times G_{p_2} \times \cdots \times G_{p_r}, one for each prime dividing n, with |G_{p_i}| = p_i^{e_i}. This is the abelian case of a fact called "Sylow subgroups," proven in full generality in a second course in abstract algebra. Granting that split, classifying finite abelian groups reduces to a single question: classify every abelian group of order p^e, for one prime p at a time.

One prime at a time. A finite abelian group of order p^e is itself isomorphic to a direct product of cyclic p-groups \mathbb{Z}_{p^{a_1}} \times \cdots \times \mathbb{Z}_{p^{a_j}}, with a_1 + \cdots + a_j = e. This is proven by induction on |G|: at each step, peel off one cyclic factor generated by an element of maximal order, then show what remains is again a smaller abelian p-group. The induction is routine once set up, but long, and is not reproduced here.

Uniqueness. Two such factorizations are isomorphic only if their multisets of prime-power factors agree exactly. This follows by counting, for each possible order d, how many elements of order d each side has. Using this chapter's own \operatorname{lcm} order formula, a \operatorname{lcm} of prime-power factors is sensitive enough to the exact list of exponents that the counts only match when the factor lists do.

Section 7 shows how to use this theorem without redoing any of the above: turn the exponent e in p^e into a partition of e, and each distinct partition names one non-isomorphic abelian group of order p^e.

Cited in outline, in the same spirit as this chapter's own classification-of-groups-of-order-pq theorem -- a fully general proof is standard second-course material, built on a lemma (the Zassenhaus "butterfly" lemma) this course doesn't develop, but its shape and the reason it's believable are both within reach here.

Existence. A finite group has a composition series simply because the process "find a proper normal subgroup, refine, repeat" cannot continue forever: each step's subgroup is strictly smaller than the last, and a proper subgroup has index at least 2, so after at most \log_2|G| steps the process bottoms out at a chain whose links H_{i+1}/H_i have no further proper normal subgroup left to peel off. Having no further proper normal subgroup to peel off is exactly this chapter's own definition of simple, so the resulting chain is a composition series.

Uniqueness of the factor multiset. Two different composition series for the same G can look completely different subgroup-by-subgroup -- different subgroups, a different number of steps along the way -- while still producing the same simple pieces in the end. The general argument (not carried out here) compares the two series' subgroups pairwise, refining each series by intersecting it against the other's terms, and shows every such refinement's own composition factors must already match, because both refine down to the same simple building blocks. What survives to the reader at this level is the conclusion rather than the intersection argument: however a finite group is broken all the way down into simple pieces, the multiset of pieces obtained is an invariant of the group itself, not of the choices made while breaking it down.

Section 7's worked constructions already illustrate the phenomenon directly: building two different-looking composition series for the same group, by peeling off subgroups in a different order, still produces the same multiset of composition factors both times.

(Strong induction on |G|, via the class equation.) If a = 0 the trivial subgroup already has order p^0=1, so assume a \ge 1 and that the theorem holds for every group of order smaller than |G|.

Case 1: p divides |Z(G)|. Z(G) is abelian and normal in G (chapter 8). By the classification of finite abelian groups (chapter 11), Z(G) is a direct product of cyclic groups of prime-power order; since p divides |Z(G)|, one of those cyclic factors has order divisible by p and so (chapter 6, subgroups of a cyclic group) contains a subgroup of order exactly p. Call it N. Every element of N lies in the center, so it commutes with all of G, giving gNg^{-1}=N for every g \in G: N is normal in G. Form the quotient G/N, of order |G|/p = p^{a-1}m; by the induction hypothesis G/N has a subgroup \bar H of order p^{a-1}. The correspondence theorem (chapter 10) lifts \bar H to a subgroup H of G with N \le H and H/N \cong \bar H, so |H| = |N|\cdot|\bar H| = p\cdot p^{a-1} = p^a.

Case 2: p does not divide |Z(G)|. The conjugation action of G on itself (chapter 12) gives the class equation |G| = |Z(G)| + \sum_i [G:C_G(x_i)], one term per noncentral conjugacy class, each term's size being [G:C_G(x_i)] by the orbit-stabilizer theorem applied to that action. If every term in the sum were divisible by p, the whole sum |G|-|Z(G)| would be too, forcing p \mid |Z(G)| -- contradicting this case's assumption. So some term [G:C_G(x_i)] is not divisible by p. Since [G:C_G(x_i)]\cdot|C_G(x_i)| = |G| = p^a m and p divides none of the index, the entire p^a must divide |C_G(x_i)| -- so C_G(x_i) has order p^a m' for some m' dividing m. Because x_i is noncentral, C_G(x_i) \ne G, so |C_G(x_i)| < |G|, and the induction hypothesis (applied to C_G(x_i)) supplies a subgroup of C_G(x_i) -- hence of G -- of order p^a.

Either case produces a subgroup of order p^a, completing the induction.

(Direct, via a coset action.) Fix a Sylow p-subgroup P (order p^a, guaranteed to exist by the First Sylow Theorem) and let Q be any other Sylow p-subgroup, also of order p^a. Let Q act on the set of left cosets G/P -- which has m=[G:P] elements, and p \nmid m -- by left multiplication: q \cdot (gP) = (qg)P. This is a genuine group action of Q, since it's just Q's elements multiplying on the left, compatible with Q's own operation by associativity.

By the orbit-stabilizer theorem (chapter 12) applied to this action, every orbit's size divides |Q|=p^a, so every orbit has size 1 or a size divisible by p. The orbits partition all m cosets, and p \nmid m, so it's impossible for every orbit to have a p-divisible size (their sizes would then sum to a multiple of p, but the total is m). So at least one orbit has size exactly 1: some coset gP is fixed by every q \in Q, meaning q(gP)=gP for all q \in Q, i.e. g^{-1}qg \in P for every q \in Q -- equivalently g^{-1}Qg \subseteq P. Since |g^{-1}Qg|=|Q|=p^a=|P|, a subset of P with the same size as P must equal P outright: g^{-1}Qg = P, i.e. Q = gPg^{-1}.

So Q is conjugate to P -- and since Q was an arbitrary Sylow p-subgroup, every Sylow p-subgroup of G is conjugate to the fixed P, hence any two are conjugate to each other.

(Two applications of orbit-stabilizer to the same set, under two different acting groups.) Fix a Sylow p-subgroup P and let X be the set of all Sylow p-subgroups of G. By the Second Sylow Theorem, every element of X is conjugate to P, so X is exactly the orbit of P under G's conjugation action on its own subgroups; hence |X|=n_p.

n_p \mid m. By the orbit-stabilizer theorem applied to G acting on X by conjugation, n_p = |X| = [G:\operatorname{Stab}_G(P)], and the stabilizer of P under conjugation is by definition its normalizer N_G(P) (chapter 8). Since P \le N_G(P) \le G, chaining Lagrange's theorem (chapter 7) across both steps gives [G:P] = [G:N_G(P)]\cdot [N_G(P):P], so [G:N_G(P)] = n_p divides [G:P] = m.

n_p \equiv 1 \pmod p. Now let P itself (instead of all of G) act on X by conjugation. By orbit-stabilizer, every orbit of this smaller action has size dividing |P|=p^a, so every orbit size is a power of p. A subgroup Q \in X is a fixed point of this action exactly when P \subseteq N_G(Q); when that holds, both P and Q are Sylow p-subgroups of N_G(Q) itself, and Q is normal inside N_G(Q) by the normalizer's own definition -- making Q the only Sylow p-subgroup N_G(Q) has (the Second Sylow Theorem, applied inside N_G(Q), would conjugate any other one to Q, but a normal subgroup's only conjugate is itself). P is a Sylow p-subgroup of N_G(Q) too, so it must be that same unique one: P=Q. So P is the only fixed point of this restricted action, giving exactly one orbit of size 1, with every remaining orbit's size a power of p greater than 1 (hence divisible by p). Summing orbit sizes, n_p = |X| = 1 + (\text{a sum of multiples of } p) \equiv 1 \pmod p.

Normality. For any g \in G and any commutator [a,b] = a^{-1}b^{-1}ab, g[a,b]g^{-1} = (gag^{-1})^{-1}(gbg^{-1})^{-1}(gag^{-1})(gbg^{-1}) = [gag^{-1}, gbg^{-1}], itself a commutator. Conjugating any generator of [G,G] by g produces another generator of [G,G], so conjugating the whole subgroup by g returns [G,G] itself: g[G,G]g^{-1}=[G,G] for every g.

Abelian quotient. Let aN, bN \in G/[G,G] (writing N=[G,G]). Their product order swaps by exactly [a,b]: (bN)(aN) = baN, \qquad (aN)(bN) = abN, and ab = ba \cdot (b^{-1}a^{-1}ba)^{-1}... more directly, a^{-1}b^{-1}ab = [a,b] \in N means abN = baN (multiplying the relation ab=(ba)[a,b] by N and using [a,b]\in N). So (aN)(bN)=(bN)(aN) for every a,b \in G -- G/[G,G] is abelian.

The map \Phi: G \to \operatorname{Aut}(G), \Phi(g) = \varphi_g (conjugation by g), is a homomorphism: \varphi_g \circ \varphi_h = \varphi_{gh} for all g,h \in G, since \varphi_g(\varphi_h(x)) = g(hxh^{-1})g^{-1} = (gh)x(gh)^{-1} = \varphi_{gh}(x).

Its image is exactly \operatorname{Inn}(G), by definition. Its kernel is \{g \in G : \varphi_g = \text{id}\} = \{g : gxg^{-1}=x \text{ for every } x \in G\} = \{g : gx=xg \text{ for every } x\} = Z(G).

By the First Isomorphism Theorem, G/\ker(\Phi) \cong \operatorname{im}(\Phi), i.e. G/Z(G) \cong \operatorname{Inn}(G).

Stated here without proof. The full argument goes through group cohomology (showing a certain obstruction class in H^2(G/N, Z(N)) must vanish when |N| and [G/N] are coprime, by a counting argument on that group), which is well outside this course's scope. The statement itself is what gets used going forward: whenever a normal subgroup's order and its quotient's order share no common factor, the "does this extension split?" question is answered automatically, without having to search for a complement by hand.

\gcd(a,n)=1 means the residue of a mod n is a unit, i.e. an element of U(n) (group-theory chapter 3), a group of order \varphi(n) under multiplication mod n. Let m = |a| be a's order as an element of U(n) -- the smallest positive integer with a^m \equiv 1 \pmod n. The cyclic subgroup \langle a \rangle \le U(n) generated by a has exactly m elements (a^0=1,a^1,\ldots, a^{m-1}, all distinct by minimality of m, and a^m=1 closes the list). By Lagrange's theorem applied to U(n), m = |\langle a\rangle| divides |U(n)| = \varphi(n); write \varphi(n) = mq for an integer q. Then a^{\varphi(n)} = a^{mq} = (a^m)^q \equiv 1^q = 1 \pmod n.