More Finite Groups

Let \(x, y \in G\). Since \(G = \langle a \rangle\), there exist integers \(m, n \in \mathbb{Z}\) such that \(x = a^m\) and \(y = a^n\). By the integer exponent laws in a group, \[ xy = a^m a^n = a^{m+n} = a^{n+m} = a^n a^m = yx. \] Hence \(G\) is Abelian.

The converse is false. The Klein four-group \(V_4 = \{e, a, b, ab\}\), with \(a^2 = b^2 = e\) and \(ab = ba\), is Abelian. Every non-identity element has order \(2\), so no single element generates the group.

Let \(d = \gcd(n, k)\). Since \(d \mid k\), we can write \(k = dr\) for some positive integer \(r\). Then \[ a^k = a^{dr} = (a^d)^r \in \langle a^d \rangle, \] which gives \[ \langle a^k \rangle \subseteq \langle a^d \rangle. \]

For the reverse inclusion, there exist integers \(s\) and \(t\) such that \[ d = ns + kt, \] since the greatest common divisor of two integers can always be written as an integer linear combination of them, a standard property of the integers that we take as given. Using \(a^n = e\) (since \(|a| = n\)), we rewrite \(a^d\) as \[ \begin{align*} a^d &= a^{ns+kt} \\\\ &= (a^n)^s (a^k)^t \\\\ &= e^s \cdot (a^k)^t \\\\ &= (a^k)^t \in \langle a^k \rangle. \end{align*} \] This gives \[ \langle a^d \rangle \subseteq \langle a^k \rangle, \] and combining both inclusions we conclude \[ \langle a^k \rangle = \langle a^d \rangle. \]

For the second part, we compute \(|a^d|\). Using the integer exponent law \((a^d)^{n/d} = a^{d \cdot (n/d)} = a^n\), and since \(|a| = n\) implies \(a^n = e\), we have \[ (a^d)^{n/d} = e, \] so \(|a^d| \leq n/d\).

For the reverse inequality, let \(i\) be a positive integer with \(i \lt n/d\). Then \(0 \lt di \lt n\). By definition of order, \(|a| = n\) means that \(a^m \neq e\) for all \(m\) with \(0 \lt m \lt n\). In particular, \[ (a^d)^i = a^{di} \neq e. \]

Hence \(n/d\) is the smallest positive integer yielding the identity, so \(|a^d| = n/d\). In general, for an element \(x\) of finite order \(q\), the powers \(e, x, x^2, \ldots, x^{q-1}\) are distinct (if \(x^u = x^v\) with \(0 \leq u \lt v \lt q\), then \(x^{v-u} = e\) with \(0 \lt v - u \lt q\), contradicting the minimality of \(q\)), and by the Division Algorithm every power of \(x\) equals one of them, so \(|x| = |\langle x \rangle|\). Combining with \(\langle a^k \rangle = \langle a^d \rangle\), \[ |a^k| = |\langle a^k \rangle| = |\langle a^d \rangle| = |a^d| = \frac{n}{d} = \frac{n}{\gcd(n,k)}. \]

In \(\mathbb{Z}_n = \langle 1 \rangle\), the element \(k\) is the \(k\)-th multiple of the generator \(1\) (the additive analogue of \(1^k\) in the Order of a Power theorem). Since \(|1| = n\), the same theorem gives \[ |k| = \frac{n}{\gcd(n, k)}. \] An element \(k\) generates \(\mathbb{Z}_n\) if and only if \(|k| = n\), which holds if and only if \(\gcd(n, k) = 1\).

Part 1:

Let \(H\) be a subgroup of \(G = \langle a \rangle\). If \(H = \{e\}\), then \(H\) is cyclic.

Now assume \(H \neq \{e\}\). We first show that \(H\) contains an element of the form \(a^t\) for some positive integer \(t\). Since \(H \neq \{e\}\), there exists a non-identity element \(b \in H\). Because \(G = \langle a \rangle\), we have \(b = a^t\) for some integer \(t\), and \(t \neq 0\) (otherwise \(b = a^0 = e\)). If \(t \gt 0\), we are done. If \(t \lt 0\), then by the subgroup property \(b^{-1} = a^{-t} \in H\) with \(-t \gt 0\). Thus, our claim is verified.

Now let \(m\) be the least positive integer such that \(a^m \in H\). By closure, \(\langle a^m \rangle \subseteq H\).

Next, we claim that \(H = \langle a^m \rangle\). Let \(b\) be any element in \(H\). Since \(b \in G\), we have \(b = a^k\) for some integer \(k\). By the Division Algorithm, we can write \(k = mq + r\) where \(0 \leq r \lt m\). Then: \[ a^k = a^{mq+r} = a^{mq}a^r \implies a^r = a^{-mq}a^k. \]

Since \(a^k \in H\) and \(a^{-mq} = (a^m)^{-q} \in H\), it follows that \(a^r \in H\). However, \(m\) is the least positive integer such that \(a^m \in H\) and \(0 \leq r \lt m\). Thus, \(r\) must be \(0\). Therefore, \[ b = a^k = a^{mq} = (a^m)^q \in \langle a^m \rangle. \] This implies every element in \(H\) is generated by \(a^m\), and hence \(H = \langle a^m \rangle\). Therefore, every subgroup of a cyclic group is cyclic.

Part 2:

Let \(H\) be any subgroup of \(G = \langle a \rangle\), where \(|G| = n\). From Part 1, \(H = \langle a^m \rangle\), where \(m\) is the least positive integer such that \(a^m \in H\). We show \(m \mid n\).

By the Order of a Power theorem applied to \(a\) (with \(|a| = n\)), we have \(\langle a^m \rangle = \langle a^{\gcd(n,m)} \rangle\), so \(a^{\gcd(n,m)} \in H\). Since \(\gcd(n,m)\) is a positive integer satisfying \(a^{\gcd(n,m)} \in H\), the minimality of \(m\) forces \(m \leq \gcd(n,m)\). Combined with the general inequality \(\gcd(n,m) \leq m\), this gives \(m = \gcd(n,m)\), so \(m \mid n\).

Therefore, by the Order of a Power theorem, \[ |H| = |\langle a^m \rangle| = |a^m| = \frac{n}{\gcd(n,m)} = \frac{n}{m}, \] which divides \(n\). This proves that the order of any subgroup of \(G\) is a divisor of \(n\).

Now let \(k\) be any positive divisor of \(n\). Then \(\langle a^{n/k} \rangle\) is a subgroup of order \[ |\langle a^{n/k} \rangle | = \frac{n}{\gcd(n, n/k)} = \frac{n}{n/k} = k. \]

It remains to show uniqueness. Suppose \(K\) is any subgroup of \(G\) of order \(k\). By Part 1 applied to \(K\), we have \(K = \langle a^s \rangle\) for the least positive integer \(s\) with \(a^s \in K\). The same divisibility argument used above (applied to \(K\) in place of \(H\)) gives \(s \mid n\). By the Order of a Power theorem, \[ |K| = |a^s| = \frac{n}{\gcd(n,s)} = \frac{n}{s} = k, \] where the last step uses \(s \mid n\). Solving gives \(s = n/k\), so \(K = \langle a^{n/k} \rangle\).

Let \(G = \langle a \rangle\) be a cyclic group of order \(n\). Every element of \(G\) has the form \(a^k\), and by the Order of a Power theorem, \[ |a^k| = \frac{n}{\gcd(n, k)}. \] Thus \(a^k\) has order \(d\) if and only if \(\gcd(n, k) = n/d\).

We count the integers \(k \in \{1, 2, \ldots, n\}\) with \(\gcd(n, k) = n/d\). Since \(\gcd(n, k) = n/d\) divides \(k\), we can write \(k = (n/d) \cdot j\) for some positive integer \(j\). Substituting and applying the Distributive Property of gcd, \[ \gcd(n, k) = \gcd\!\left(n, \tfrac{n}{d} \cdot j\right) = \tfrac{n}{d} \cdot \gcd(d, j), \] so \(\gcd(n, k) = n/d\) if and only if \(\gcd(d, j) = 1\).

The integers \(k \in \{1, \ldots, n\}\) satisfying \((n/d) \mid k\) are exactly those of the form \(k = (n/d) \cdot j\) with \(j \in \{1, \ldots, d\}\), and under this correspondence the condition \(\gcd(n, k) = n/d\) becomes \(\gcd(d, j) = 1\) (by the previous step). Hence the number of \(k\) giving an element of order \(d\) equals the number of \(j \in \{1, \ldots, d\}\) with \(\gcd(d, j) = 1\), which equals \(\phi(d)\). For \(d \gt 1\) the value \(j = d\) is not relatively prime to \(d\), so the count over \(\{1, \ldots, d\}\) agrees with the definition's count over \(\{1, \ldots, d-1\}\), and for \(d = 1\) both counts equal \(1\).

In a cyclic group of order \(n\), the generators are precisely the elements of order \(n\). Applying the Number of Elements of Each Order theorem with \(d = n\), the number of such elements is \(\phi(n)\).

Let \(G\) be a finite group and let \(d\) be a positive integer. If \(G\) has no element of order \(d\), the count is \(0\), which is a multiple of \(\phi(d)\).

Otherwise, let \(a \in G\) have order \(d\). Then \(\langle a \rangle\) is a cyclic subgroup of order \(d\), and by the Number of Elements of Each Order theorem, it contains exactly \(\phi(d)\) elements of order \(d\).

Suppose \(b \in G\) has order \(d\) with \(b \notin \langle a \rangle\). Then \(\langle b \rangle\) is another cyclic subgroup of order \(d\), also containing \(\phi(d)\) elements of order \(d\).

We claim \(\langle a \rangle\) and \(\langle b \rangle\) share no element of order \(d\). Indeed, if \(c\) has order \(d\) and \(c \in \langle a \rangle \cap \langle b \rangle\), then \(\langle c \rangle\) is a cyclic subgroup of order \(d\) contained in both \(\langle a \rangle\) and \(\langle b \rangle\). Since \(|\langle c \rangle| = |\langle a \rangle| = |\langle b \rangle| = d\), we must have \(\langle c \rangle = \langle a \rangle = \langle b \rangle\), contradicting \(b \notin \langle a \rangle\).

Therefore, the order-\(d\) elements of \(G\) partition into disjoint sets of size \(\phi(d)\), one for each distinct cyclic subgroup of order \(d\). The total count is thus a multiple of \(\phi(d)\).

Existence.

Let \(\alpha\) be a permutation of a finite set \(S = \{1, 2, \ldots, n\}\).

Step 1 (cycle through a single element). Fix any \(x \in S\) and consider the sequence \(x, \alpha(x), \alpha^2(x), \ldots\). Since \(S\) is finite, the pigeonhole principle yields nonnegative integers \(i \lt j\) with \(\alpha^i(x) = \alpha^j(x)\). Because \(\alpha\) is a bijection, applying \(\alpha^{-i}\) gives \(x = \alpha^{j-i}(x)\). Therefore the set \(\{t \geq 1 : \alpha^t(x) = x\}\) is nonempty. Let \(k\) be its smallest element.

The elements \(x, \alpha(x), \ldots, \alpha^{k-1}(x)\) are distinct. If \(\alpha^a(x) = \alpha^b(x)\) for some \(0 \leq a \lt b \lt k\), then \(\alpha^{b-a}(x) = x\) with \(0 \lt b - a \lt k\), contradicting the minimality of \(k\). If \(k = 1\), then \(\alpha\) fixes \(x\). If \(k \geq 2\), then on the set \(O_x := \{x, \alpha(x), \ldots, \alpha^{k-1}(x)\}\), the permutation \(\alpha\) agrees with the \(k\)-cycle \((x\, \alpha(x)\, \alpha^2(x)\, \ldots\, \alpha^{k-1}(x))\).

Step 2 (iterate over remaining elements). If \(O_x = S\), we are done. Otherwise, pick any \(y \in S \setminus O_x\) and repeat Step 1 to obtain a set \(O_y\) and an associated cycle. We claim \(O_x \cap O_y = \emptyset\). Suppose instead that \(z \in O_x \cap O_y\), so \(z = \alpha^a(x) = \alpha^b(y)\) for some integers \(a, b \geq 0\). Then \(y = \alpha^{a-b}(x) \in O_x\) (using that \(O_x\) is closed under both \(\alpha\) and \(\alpha^{-1}\), since \(\alpha^k(x) = x\)), contradicting \(y \in S \setminus O_x\).

Continuing this process until every element of \(S\) is covered yields a partition \(S = O_{x_1} \sqcup O_{x_2} \sqcup \cdots \sqcup O_{x_s}\), and \(\alpha\) equals the product of the corresponding cycles (with 1-cycles, corresponding to fixed points, omitted from the notation).

Uniqueness.

Suppose \(\alpha = \gamma_1 \gamma_2 \cdots \gamma_t\) is any decomposition into pairwise disjoint cycles of length \(\geq 2\). For each non-fixed element \(x \in S\), exactly one \(\gamma_i\) moves \(x\). On the support of \(\gamma_i\), all other \(\gamma_j\) act as the identity. Hence \(\alpha(x) = \gamma_i(x)\), \(\alpha^2(x) = \gamma_i^2(x)\), and so on, so the support of \(\gamma_i\) equals \(O_x = \{x, \alpha(x), \alpha^2(x), \ldots\}\), and \(\gamma_i\) is determined entirely by \(\alpha\) and \(x\).

Therefore the cycles in any decomposition are precisely the sets \(O_{x_i}\) produced in the existence proof, so the decomposition is unique up to the order of the factors.

Let \(S\) be the finite set on which \(\alpha\) and \(\beta\) act. Since the cycles are disjoint, the set \(S\) can be partitioned into three mutually exclusive and exhaustive subsets:

1. \(A = \{a_1, a_2, \ldots, a_m\}\), the set of elements moved by \(\alpha\).
2. \(B = \{b_1, b_2, \ldots, b_n\}\), the set of elements moved by \(\beta\).
3. \(C = \{ c_1, c_2, \ldots, c_k\}\), the set of all other elements in \(S\) (fixed by both \(\alpha\) and \(\beta\)).

To prove that the permutations are equal, we must show that the result of applying the compositions \(\alpha \beta\) and \(\beta \alpha\) is identical: \[ \forall x \in S, \, (\alpha \beta)(x) = (\beta \alpha)(x). \]

Case 1: \(x \in A\) (The element is moved by \(\alpha\))

Since \(A\) and \(B\) are disjoint, \(\beta\) must fix every element in \(A\). Thus, \(\beta(x) = x\).
For the composition \(\alpha \beta\): \[ (\alpha \beta)(x) = \alpha(\beta (x)) = \alpha(x). \] Since \(x \in A\), \(\alpha(x)\) is also in \(A\). Because \(A\) and \(B\) are disjoint, \(\beta\) fixes \(\alpha(x)\).
For the composition \(\beta \alpha\): \[ (\beta \alpha)(x) = \beta (\alpha (x)) = \alpha (x). \] Thus, for \(x \in A\), \((\alpha \beta)(x) = \alpha(x) = (\beta \alpha)(x)\).

Case 2: \(x \in B\) (The element is moved by \(\beta\))

Since \(B\) and \(A\) are disjoint, \(\alpha\) must fix every element in \(B\). Thus, \(\alpha(x) = x\).
For the composition \(\alpha \beta\): \[ (\alpha \beta)(x) = \alpha(\beta (x)). \] Since \(x \in B\), \(\beta(x) \in B\). Because \(B\) and \(A\) are disjoint, \(\alpha\) fixes \(\beta(x)\). Therefore, \[ (\alpha \beta)(x) = \beta (x). \] For the composition \(\beta \alpha\): \[ (\beta \alpha)(x) = \beta (\alpha (x)) = \beta (x), \] since \(\alpha(x) = x\). Thus, for \(x \in B\), \((\alpha \beta)(x) = \beta(x) = (\beta \alpha)(x)\).

Case 3: \(x \in C\) (The element is fixed by both \(\alpha\) and \(\beta\))

By the definition of the set \(C\), we have \(\alpha(x) = x\) and \(\beta(x) = x\).
For the composition \(\alpha \beta\): \[ (\alpha \beta)(x) = \alpha(\beta (x)) = \alpha(x) = x. \] For the composition \(\beta \alpha\): \[ (\beta \alpha)(x) = \beta (\alpha (x)) = \beta (x) = x. \] Thus, for \(x \in C\), \((\alpha \beta)(x) = x = (\beta \alpha)(x)\).

Since the result of the two compositions is the same across all three exhaustive subsets, we conclude that \(\alpha \beta = \beta \alpha\).

Let \(\alpha\) be a permutation and its disjoint cycle decomposition be: \[ \alpha = \beta_1 \beta_2 \cdots \beta_r \] where \(\beta_i\) is a cycle of length \(k_i\). The order of a \(k_i\)-cycle is \(|\beta_i| = k_i\). For a cycle \(\sigma = (i_1\, i_2\, \ldots\, i_{k_i})\), we have \(\sigma^{k_i}(i_j) = i_j\) for every \(j\), because the indices cycle back, so \(\sigma^{k_i} = \epsilon\). For any \(0 \lt t \lt k_i\), \(\sigma^t(i_1) = i_{1+t} \neq i_1\), so no smaller positive power yields the identity. We must show that \(|\alpha| = \operatorname{lcm}(k_1, k_2, \ldots, k_r) = m\).

Step 1: Show that \(\alpha^m = \epsilon\)

Since the cycles \(\beta_1, \ldots, \beta_r\) are pairwise disjoint, they pairwise commute (by the Disjoint Cycles Commute theorem). Consequently, for any positive integer \(t\): \[ \alpha^t = (\beta_1 \beta_2 \cdots \beta_r)^t = \beta_1^t \beta_2^t \cdots \beta_r^t. \]

By the definition of the least common multiple, \(m\) is a multiple of each \(k_i\). Since \(|\beta_i| = k_i\), we have \(\beta_i^m = \epsilon\) for every \(i\). It follows that: \[ \alpha^m = \epsilon \cdot \epsilon \cdots \epsilon = \epsilon. \] Since \(\alpha^m = \epsilon\), the theorem on order dividing any annihilating power gives \(|\alpha| \mid m\), and thus \(|\alpha| \leq m\).

Step 2: Show that \(m\) is the smallest such positive integer

Suppose \(\alpha^t = \epsilon\) for some positive integer \(t\). This means: \[ \beta_1^t \beta_2^t \cdots \beta_r^t = \epsilon. \]

Since the cycles are disjoint, each \(\beta_i\) moves a disjoint set of elements. For any element \(x\) moved by the cycle \(\beta_i\), the other cycles \(\beta_j\) (\(j \neq i\)) fix \(x\). Applying the permutation to such an \(x\), we get: \[ \alpha^t(x) = \beta_i^t(x) = x. \] Since this holds for all \(x\) in the support of \(\beta_i\), we must have \(\beta_i^t = \epsilon\). By the same theorem, \(\beta_i^t = \epsilon\) implies that \(|\beta_i| = k_i\) divides \(t\). Because this must hold for every \(i \in \{1, \ldots, r\}\), \(t\) must be a common multiple of all cycle lengths \(k_1, \ldots, k_r\). By definition, the least common multiple \(m\) is the smallest such integer. Thus, \(t \geq m\).

We conclude that \(|\alpha| = m = \operatorname{lcm}(k_1, k_2, \ldots, k_r)\).

Since every permutation can be written as a product of disjoint cycles (by the Products of Disjoint Cycles theorem), it suffices to show that every cycle can be written as a product of 2-cycles (transpositions). (For the identity permutation itself, the assumption \(n \gt 1\) gives the explicit product \(\epsilon = (1\, 2)(1\, 2)\).)

Consider an arbitrary \(k\)-cycle: \(\sigma = (i_1\, i_2\, \ldots\, i_k)\). We claim that: \[ (i_1\, i_2\, \ldots\, i_k) = (i_1\, i_k)(i_1\, i_{k-1}) \cdots (i_1\, i_3)(i_1\, i_2) \] where the product of \(k-1\) transpositions is evaluated from right to left.

Let \(\tau\) denote the product on the right-hand side. We verify that \(\sigma\) and \(\tau\) agree on all elements.

• For \(i_1\):

  The rightmost transposition \((i_1\, i_2)\) sends \(i_1 \mapsto i_2\). Each subsequent transposition \((i_1\, i_m)\) for \(m = 3, \ldots, k\) fixes \(i_2\) (since \(i_2 \neq i_1\) and \(i_2 \neq i_m\)). Thus \(\tau(i_1) = i_2 = \sigma(i_1)\).

• For \(i_j\) where \(2 \leq j \leq k-1\):

  Reading right to left, the transpositions \((i_1\, i_2), (i_1\, i_3), \ldots, (i_1\, i_{j-1})\) all fix \(i_j\). The transposition \((i_1\, i_j)\) sends \(i_j \mapsto i_1\). The next transposition \((i_1\, i_{j+1})\) sends \(i_1 \mapsto i_{j+1}\). The remaining transpositions \((i_1\, i_{j+2}), \ldots, (i_1\, i_k)\) all fix \(i_{j+1}\). Thus \(\tau(i_j) = i_{j+1} = \sigma(i_j)\).

• For \(i_k\):

  Reading right to left, the transpositions \((i_1\, i_2), (i_1\, i_3), \ldots, (i_1\, i_{k-1})\) all fix \(i_k\). The leftmost transposition \((i_1\, i_k)\) sends \(i_k \mapsto i_1\). Thus \(\tau(i_k) = i_1 = \sigma(i_k)\).

• For any \(x \notin \{i_1, \ldots, i_k\}\):

  Every transposition \((i_1\, i_m)\) fixes \(x\), so \(\tau(x) = x = \sigma(x)\).

Since \(\sigma\) and \(\tau\) agree on all elements of \(\{1, 2, \ldots, n\}\), we have \(\sigma = \tau\). Therefore, every cycle is a product of transpositions. Since every permutation is a product of disjoint cycles, every permutation in \(S_n\) is a product of transpositions.

Suppose for contradiction that some odd \(r \geq 1\) admits a representation \(\epsilon = \beta_1 \beta_2 \cdots \beta_r\) with each \(\beta_j\) a 2-cycle. Since a single 2-cycle moves two elements and is never the identity, \(r \geq 3\). Among all such odd representations, pick one with \(r\) minimal.

Fix any symbol \(a\) appearing in the 2-cycles, and let \(\beta_i\) be the rightmost 2-cycle containing \(a\) (so \(\beta_{i+1}, \ldots, \beta_r\) all fix \(a\)).

The case \(i = 1\). If \(\beta_1\) is the only 2-cycle containing \(a\), then \(\beta_2, \ldots, \beta_r\) all fix \(a\), so \[ \epsilon(a) = \beta_1 \beta_2 \cdots \beta_r(a) = \beta_1(a). \] But \(\beta_1\) is a 2-cycle containing \(a\), so \(\beta_1(a) \neq a\). This contradicts \(\epsilon(a) = a\).

The case \(i \geq 2\). We examine the adjacent pair \(\beta_{i-1}\beta_i\). Writing \(\beta_i = (a\, b)\), there are four possible configurations for \(\beta_{i-1}\), depending on how its entries relate to \(\{a, b\}\) (where \(c, d\) denote symbols distinct from \(a, b\) and from each other):

1. \(\beta_{i-1}\beta_i = (a\,b)(a\,b) = \epsilon\). The two 2-cycles cancel, reducing the total count to \(r - 2\).
2. \(\beta_{i-1}\beta_i = (a\,c)(a\,b) = (a\,b)(b\,c)\). After rewriting, \(a\) appears only in position \(i - 1\).
3. \(\beta_{i-1}\beta_i = (b\,c)(a\,b) = (a\,c)(b\,c)\). After rewriting, \(a\) appears only in position \(i - 1\).
4. \(\beta_{i-1}\beta_i = (c\,d)(a\,b) = (a\,b)(c\,d)\) (disjoint cycles commute, by the Disjoint Cycles Commute theorem). After rewriting, \(a\) appears only in position \(i - 1\).

In case 1, we obtain a representation of \(\epsilon\) as a product of \(r - 2\) 2-cycles. Since \(r\) is odd, so is \(r - 2\), and \(r - 2 \geq 1\). But \(r - 2 = 1\) is impossible (a single 2-cycle is not the identity), while \(r - 2 \geq 3\) contradicts the minimality of \(r\). Either way, a contradiction.

In cases 2, 3, 4, the total count remains \(r\), but the rightmost 2-cycle containing \(a\) has moved from position \(i\) to position \(i - 1\), strictly smaller. Since this position is a positive integer, repeated application of the cases must terminate. Termination occurs either by reaching case 1, which yields the contradiction above, or by reducing the position to \(i = 1\), which returns us to the contradiction established for that case.

In every scenario we reach a contradiction. Therefore no odd \(r\) admits such a representation, so \(r\) must be even.

Suppose that a permutation \(\alpha\) has two different decompositions into 2-cycles: \[ \alpha = \beta_1 \beta_2 \cdots \beta_r \quad \text{and} \quad \alpha = \gamma_1 \gamma_2 \cdots \gamma_s. \] We want to show that \(r\) and \(s\) must have the same parity. Equating the two expressions: \[ \beta_1 \beta_2 \cdots \beta_r = \gamma_1 \gamma_2 \cdots \gamma_s. \]

Since every 2-cycle is its own inverse, we multiply both sides on the right by \(\beta_r \cdots \beta_1\) to isolate the identity: \[ \epsilon = \gamma_1 \gamma_2 \cdots \gamma_s \beta_r \cdots \beta_1. \] The identity is now expressed as a product of \(s + r\) transpositions. By the Lemma above, the total number of transpositions \(s + r\) must be even.

Note that if \(s+r\) is even, then \(s\) and \(r\) must be both even or both odd. This confirms that the parity of \(\alpha\) is well-defined and consistent across any possible decomposition.

We construct a bijection between \(A_n\) and \(S_n \setminus A_n\) (the set of odd permutations). Since \(n \gt 1\), the transposition \((1\, 2) \in S_n\), and we define \[ \phi: A_n \to S_n \setminus A_n, \quad \phi(\alpha) = (1\, 2)\,\alpha. \]

Well-defined. If \(\alpha \in A_n\), then \(\alpha = \beta_1 \beta_2 \cdots \beta_{2k}\) for some even number of 2-cycles \(\beta_j\). Therefore \[ (1\, 2)\,\alpha = (1\, 2)\,\beta_1 \beta_2 \cdots \beta_{2k} \] is a product of \(2k + 1\) 2-cycles. Since \(2k + 1\) is odd, \((1\, 2)\alpha\) admits an odd-length decomposition into 2-cycles. By the Parity Theorem, every decomposition of \((1\, 2)\alpha\) has odd length, so \((1\, 2)\alpha \in S_n \setminus A_n\).

Injective. If \(\phi(\alpha) = \phi(\beta)\), then \((1\, 2)\alpha = (1\, 2)\beta\). Multiplying both sides on the left by \((1\, 2)\) and using \((1\, 2)(1\, 2) = \epsilon\), \[ \alpha = (1\, 2)(1\, 2)\alpha = (1\, 2)(1\, 2)\beta = \beta. \]

Surjective. Given any odd \(\sigma \in S_n \setminus A_n\), consider \((1\, 2)\sigma\). Writing \(\sigma = \gamma_1 \gamma_2 \cdots \gamma_{2\ell + 1}\) as a product of an odd number of 2-cycles, we see \((1\, 2)\sigma\) is a product of \(2\ell + 2\) 2-cycles, an even number, so \((1\, 2)\sigma \in A_n\). Moreover, \[ \phi\!\left((1\, 2)\sigma\right) = (1\, 2)(1\, 2)\sigma = \sigma. \]

Therefore \(\phi\) is a bijection, so \(|A_n| = |S_n \setminus A_n|\). By the Product of 2-Cycles theorem, every permutation in \(S_n\) is a product of 2-cycles, and by the Parity Theorem its parity is unambiguous. Hence \(A_n\) and \(S_n \setminus A_n\) partition \(S_n\), giving \[ |A_n| + |S_n \setminus A_n| = |S_n| = n!. \] Combined with \(|A_n| = |S_n \setminus A_n|\), this yields \(|A_n| = n!/2\).