Group Classification

We verify the group axioms for \(G = G_1 \times G_2 \times \cdots \times G_n\).

Closure: Since each \(G_i\) is closed under its operation, the product \(g_i h_i \in G_i\) for all \(i\). Thus \((g_1 h_1, \ldots, g_n h_n) \in G\).

Associativity: Let \(a = (a_1, \ldots, a_n)\), \(b = (b_1, \ldots, b_n)\), \(c = (c_1, \ldots, c_n)\). Then: \[ \begin{align*} (ab)c &= ((a_1 b_1, \ldots, a_n b_n))(c_1, \ldots, c_n) \\\\ &= ((a_1 b_1)c_1, \ldots, (a_n b_n)c_n) \\\\ &= (a_1(b_1 c_1), \ldots, a_n(b_n c_n)) && \text{(by associativity in each } G_i \text{)}\\\\ &= a(bc). \end{align*} \]

Identity: The identity element is \(e = (e_1, e_2, \ldots, e_n)\), where \(e_i\) is the identity of \(G_i\).

Inverses: The inverse of \((g_1, g_2, \ldots, g_n)\) is \((g_1^{-1}, g_2^{-1}, \ldots, g_n^{-1})\).

Consider \(\mathbb{Z}_2 \times \mathbb{Z}_3\). The elements are all pairs \((a, b)\) where \(a \in \{0, 1\}\) and \(b \in \{0, 1, 2\}\): \[ \mathbb{Z}_2 \times \mathbb{Z}_3 = \{(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)\}. \] The operation is addition modulo 2 in the first component and modulo 3 in the second: \[ (1, 2) + (1, 1) = (1+1 \bmod 2, \, 2+1 \bmod 3) = (0, 0). \] This group has order \(|\mathbb{Z}_2 \times \mathbb{Z}_3| = 2 \cdot 3 = 6\).

\((\Rightarrow)\) Suppose \(G = G_1 \times \cdots \times G_n\) is Abelian. For any \(a_i, b_i \in G_i\), consider the elements \((e_1, \ldots, a_i, \ldots, e_n)\) and \((e_1, \ldots, b_i, \ldots, e_n)\) in \(G\). Since \(G\) is Abelian, their product commutes, which implies \(a_i b_i = b_i a_i\) in \(G_i\).

\((\Leftarrow)\) Suppose each \(G_i\) is Abelian. For any \((a_1, \ldots, a_n), (b_1, \ldots, b_n) \in G\): \[ \begin{align*} (a_1, \ldots, a_n)(b_1, \ldots, b_n) &= (a_1 b_1, \ldots, a_n b_n) \\\\ &= (b_1 a_1, \ldots, b_n a_n) \\\\ &= (b_1, \ldots, b_n)(a_1, \ldots, a_n). \end{align*} \]

Let \(s = |(g_1, g_2, \ldots, g_n)|\) and \(t = \text{lcm}(|g_1|, |g_2|, \ldots, |g_n|)\).

Since \(t\) is a multiple of each \(|g_i|\), we have \(g_i^t = e_i\) for all \(i\). Thus: \[ (g_1, g_2, \ldots, g_n)^t = (g_1^t, g_2^t, \ldots, g_n^t) = (e_1, e_2, \ldots, e_n). \] This means \(s \mid t\) (i.e., \(s\) divides \(t\)).

Conversely, \((g_1, g_2, \ldots, g_n)^s = (e_1, e_2, \ldots, e_n)\) implies \(g_i^s = e_i\) for all \(i\). Thus \(|g_i| \mid s\) for all \(i\), so \(t \mid s\).

Since \(s\) and \(t\) are positive integers with \(s \mid t\) and \(t \mid s\), we conclude \(s = t\).

Consider the element \((2, 3) \in \mathbb{Z}_4 \times \mathbb{Z}_6\).

In \(\mathbb{Z}_4\): the element \(2\) has order \(|2| = 2\) since \(2 + 2 = 4 \equiv 0 \pmod{4}\).

In \(\mathbb{Z}_6\): the element \(3\) has order \(|3| = 2\) since \(3 + 3 = 6 \equiv 0 \pmod{6}\).

Therefore: \(|(2, 3)| = \text{lcm}(2, 2) = 2\).

Now consider \((1, 1) \in \mathbb{Z}_4 \times \mathbb{Z}_6\). In \(\mathbb{Z}_4\), the element \(1\) has order \(4\); in \(\mathbb{Z}_6\), the element \(1\) has order \(6\).

Therefore: \(|(1, 1)| = \text{lcm}(4, 6) = 12\).

\((\Rightarrow)\):
Suppose \(G \times H\) is cyclic with \(|G| = m\) and \(|H| = n\), so that \(|G \times H| = mn\). We must show that \(m\) and \(n\) are relatively prime. Suppose that \(\text{gcd}(m ,n) = d\) and \((g, h)\) is a generator of \(G \times H\). Since \[ (g, h)^{\frac{mn}{d}} = \left((g^m)^{\frac{n}{d}}, (h^n)^{\frac{m}{d}}\right) = (e, e), \] we have \[ mn = |(g, h)| \leq \frac{mn}{d}. \] Thus \(\text{gcd}(m ,n) = d = 1\), which means \(m\) and \(n\) are relatively prime.

\((\Leftarrow)\):
Let \(G = \langle g \rangle\) and \(H = \langle h \rangle\). Suppose \(\text{gcd}(m ,n) = 1\). Then \[ |(g, h)| = \text{lcm}(m, n) = mn = |G \times H|, \] so that \((g, h)\) is a generator of \(G \times H\).

Isomorphic: Since \(\gcd(2, 3) = 1\): \[ \mathbb{Z}_2 \times \mathbb{Z}_3 \cong \mathbb{Z}_6. \] Both are cyclic groups of order 6.

Not Isomorphic: Since \(\gcd(2, 4) = 2 \neq 1\): \[ \mathbb{Z}_2 \times \mathbb{Z}_4 \not\cong \mathbb{Z}_8. \] The maximum order of an element in \(\mathbb{Z}_2 \times \mathbb{Z}_4\) is \(\text{lcm}(2, 4) = 4\), but \(\mathbb{Z}_8\) has an element of order 8.

Three factors: Since \(\gcd(2, 3) = \gcd(2, 5) = \gcd(3, 5) = 1\): \[ \mathbb{Z}_2 \times \mathbb{Z}_3 \times \mathbb{Z}_5 \cong \mathbb{Z}_{30}. \] Moreover, we can express the same group in different forms: \[ \begin{align*} \mathbb{Z}_{30} &\cong \mathbb{Z}_2 \times \mathbb{Z}_3 \times \mathbb{Z}_5 \\\\ &\cong \mathbb{Z}_5 \times \mathbb{Z}_6 \\\\ &\cong \mathbb{Z}_3 \times \mathbb{Z}_{10}. \end{align*} \]

Define \(\phi: H_1 \times H_2 \times \cdots \times H_n \to G\) by \(\phi(h_1, h_2, \ldots, h_n) = h_1 h_2 \cdots h_n\), where the left side is the external direct product.

Onto: By condition 2, every element of \(G\) can be written as \(h_1 h_2 \cdots h_n\) for some \(h_i \in H_i\).

One-to-one: Suppose \(\phi(h_1, \ldots, h_n) = \phi(h'_1, \ldots, h'_n)\), i.e., \(h_1 \cdots h_n = h'_1 \cdots h'_n\). By condition 3, the representation of each element as a product \(h_1 h_2 \cdots h_n\) is unique, so \(h_i = h'_i\) for all \(i\).

Homomorphism: We need elements from different \(H_i\) to commute. Let \(h \in H_i\) and \(k \in H_j\) with \(i \neq j\). Consider the commutator \([h, k] = hkh^{-1}k^{-1}\). Since \(H_j \trianglelefteq G\), we have \(hkh^{-1} \in H_j\), so \([h,k] = (hkh^{-1})k^{-1} \in H_j\). Since \(H_i \trianglelefteq G\), we have \(kh^{-1}k^{-1} \in H_i\), so \([h,k] = h(kh^{-1}k^{-1}) \in H_i\). Thus \([h,k] \in H_i \cap H_j = \{e\}\), which gives \(hk = kh\).

Therefore, we can rearrange: \[ \phi(h_1 h'_1, \ldots, h_n h'_n) = h_1 h'_1 \cdots h_n h'_n = h_1 \cdots h_n \cdot h'_1 \cdots h'_n = \phi(h_1, \ldots, h_n)\phi(h'_1, \ldots, h'_n). \]

Recall that \(U(105) \cong \mathbb{Z}_2 \times \mathbb{Z}_4 \times \mathbb{Z}_6\). This isomorphism arises because \(U(105)\) is the internal direct product of three subgroups: \[ U(105) = U_{35}(105) \times U_{21}(105) \times U_{15}(105) \] where \[ U_{35}(105) = \{1, 71\}, \quad U_{21}(105) = \{1, 22, 43, 64\}, \quad U_{15}(105) = \{1, 16, 31, 46, 61, 76\}. \] These subgroups satisfy the three conditions: each is normal (since \(U(105)\) is Abelian), their product gives all of \(U(105)\), and they have pairwise trivial intersections.

This decomposition makes it easy to find subgroups of \(U(105)\) with a specific order. Since subgroups of a direct product come from subgroups of the factors, we just need to find factor orders that multiply to the desired order.

For example, to find subgroups of order 12 in \(U(105)\), we look for divisors \(d_1 | 2\), \(d_2 | 4\), \(d_3 | 6\) with \(d_1 \cdot d_2 \cdot d_3 = 12\):

• \(1 \times 2 \times 6 = 12\): \[ \{1\} \times \{1, 64\} \times U_{15}(105) = \{1,4,16,19,31,34,46,61,64,76,79,94\} \]
• \(2 \times 2 \times 3 = 12\): \[ U_{35}(105) \times \{1,64\} \times \{1,16,46\} = \{1,4,11,16,29,44,46,64,71,74,79,86\} \]
• \(1 \times 4 \times 3 = 12\): \[ \{1\} \times U_{21}(105) \times \{1,16,46\} = \{1,4,16,22,37,43,46,58,64,67,79,88\} \]
• \(2 \times 1 \times 6 = 12\): \[U_{35}(105) \times \{1\} \times U_{15}(105) = U_5(105) = \{1,11,16,26,31,41,46,61,71,76,86,101\} \]

Each combination gives a distinct subgroup of order 12. Without the decomposition, finding these subgroups in the 48-element group \(U(105)\) would be far more tedious.

It is straightforward to verify that \(H\) and \(K\) are subgroups of \(G\) using the one-step subgroup test (since \(G\) is Abelian, \((xy^{-1})^{p^n} = x^{p^n}(y^{-1})^{p^n} = e\) whenever \(x, y \in H\), and similarly for \(K\)).

Because \(G\) is Abelian, to prove that \(G = H \times K\), we need only show that \(G = HK\) and \(H \cap K = \{e\}\).

Showing \(G = HK\):
Since \(\gcd(m, p^n) = 1\), there exist integers \(s\) and \(t\) such that \(1 = sm + tp^n\). For any \(x \in G\), we have: \[ x = x^1 = x^{sm + tp^n} = x^{sm} \cdot x^{tp^n}. \] Now, since \(|G| = p^n m\), by Lagrange's theorem we have \(x^{|G|} = e\) for all \(x \in G\). Therefore: \[ (x^{sm})^{p^n} = x^{smp^n} = x^{s |G|} = (x^{|G|})^s = e, \] so \(x^{sm} \in H\). Similarly, \[ (x^{tp^n})^m = x^{tp^n m} = x^{t |G|} = (x^{|G|})^t = e, \] so \(x^{tp^n} \in K\). Thus \(x = x^{sm} \cdot x^{tp^n} \in HK\), and we conclude \(G = HK\).

Showing \(H \cap K = \{e\}\):
Suppose \(x \in H \cap K\). Then \(x^{p^n} = e\) and \(x^m = e\), so \(|x|\) divides both \(p^n\) and \(m\).
(Note: For any group element \(a\), \(a^k = e\) if and only if \(|a|\) divides \(k\).)
Since \(p\) does not divide \(m\), we have \(\gcd(p^n, m) = 1\), which forces \(|x| = 1\). Therefore \(x = e\).

Showing \(|H| = p^n\):
Since \(H \cap K = \{e\}\), we have \[ |HK| = |H||K| / |H \cap K| = |H||K|. \] Since \(G = HK\), we get \(p^n m = |H||K|\).

Now we determine what \(|H|\) and \(|K|\) must be. Consider any element \(x \in H\). By definition of \(H\), we have \(x^{p^n} = e\), so \(|x|\) divides \(p^n\). This means every element of \(H\) has order that is a power of \(p\). By Lagrange's theorem, \(|x|\) divides \(|H|\) for all \(x \in H\), and since all element orders are powers of \(p\), the group order \(|H|\) must also be a power of \(p\). (If a prime \(q \neq p\) divided \(|H|\), then by Cauchy's theorem of Abelian groups, \(H\) would contain an element of order \(q\), contradicting the fact that all elements of \(H\) have orders dividing \(p^n\).)

Similarly, every element \(x \in K\) satisfies \(x^m = e\), so \(|x|\) divides \(m\). Since \(p\) does not divide \(m\), no element of \(K\) can have order divisible by \(p\). By the same reasoning (Cauchy's theorem), \(p\) does not divide \(|K|\).

Now we can determine \(|H|\). We know \(|H| = p^k\) for some \(k \leq n\), and \(|H||K| = p^n m\), so \(|K| = p^{n-k} m\). But since \(p\) does not divide \(|K|\), we must have \(n - k = 0\), i.e., \(k = n\). Therefore \(|H| = p^n\) and \(|K| = m\).

Let \(|G| = p^n\). We proceed by induction on \(n\). If \(n = 1\), then \(G = \langle a \rangle \times \{e\}\), and we are done.

Now assume the result holds for all Abelian groups of order \(p^k\) where \(k < n\). Let \(a\) be an element of maximum order \(p^m\) in \(G\). Then \(x^{p^m} = e\) for all \(x \in G\).

Case 1: If \(G = \langle a \rangle\), then \(G = \langle a \rangle \times \{e\}\), and we are done.

Case 2: Assume \(G \neq \langle a \rangle\). Among all elements of \(G\) not in \(\langle a \rangle\), choose \(b\) to have smallest order.

Claim: \(\langle a \rangle \cap \langle b \rangle = \{e\}\).

Proof of Claim: Since \(|b^p| = |b|/p\), we know that \(b^p \in \langle a \rangle\) by the minimality of \(|b|\) (if \(b^p \notin \langle a \rangle\), then \(b^p\) would be an element outside \(\langle a \rangle\) with smaller order than \(b\), a contradiction). Say \(b^p = a^i\) for some integer \(i\).

Now observe: \[ e = b^{p^m} = (b^p)^{p^{m-1}} = (a^i)^{p^{m-1}} = a^{i \cdot p^{m-1}}, \] so \(|a| = p^m\) divides \(i \cdot p^{m-1}\). This means \(|a^i| \leq p^{m-1}\), so \(a^i\) is not a generator of \(\langle a \rangle\). By the theory of cyclic groups, \(\gcd(p^m, i) \neq 1\), which means \(p\) divides \(i\). Write \(i = pj\) for some integer \(j\).

Consider the element \(c = a^{-j}b\). Since \(b \notin \langle a \rangle\), certainly \(c \notin \langle a \rangle\) (for if \(c \in \langle a \rangle\), then \(b = a^j c \in \langle a \rangle\), a contradiction). Also: \[ c^p = (a^{-j})^p \cdot b^p = a^{-pj} \cdot b^p = a^{-i} \cdot b^p = b^{-p} \cdot b^p = e. \] So \(c\) is an element of order \(p\) that lies outside \(\langle a \rangle\). Since \(b\) was chosen to have smallest order among elements outside \(\langle a \rangle\), we conclude \(|b| \leq |c| = p\), hence \(|b| = p\).

Now, \(\langle a \rangle \cap \langle b \rangle\) is a subgroup of both \(\langle a \rangle\) and \(\langle b \rangle\). Since \(|\langle b \rangle| = p\) is prime, either \(\langle a \rangle \cap \langle b \rangle = \{e\}\) or \(\langle a \rangle \cap \langle b \rangle = \langle b \rangle\). The latter would mean \(b \in \langle a \rangle\), contradicting \(b \notin \langle a \rangle\). Therefore \(\langle a \rangle \cap \langle b \rangle = \{e\}\), proving the claim.

Completing the proof:
Consider the factor group \(\overline{G} = G/\langle b \rangle\). Let \(\overline{x}\) denote the coset \(x\langle b \rangle\) in \(\overline{G}\).

We claim that \(|\overline{a}| = |a| = p^m\). If \(|\overline{a}| < |a| = p^m\), then \(\overline{a}^{p^{m-1}} = \overline{e}\). This means that \((a\langle b \rangle)^{p^{m-1}} = a^{p^{m-1}} \langle b \rangle = \langle b \rangle\), so that \(a^{p^{m-1}} \in \langle a \rangle \cap \langle b \rangle = \{e\}\), contradicting the fact that \(|a| = p^m\). Thus, \(|\overline{a}| = |a| = p^m\), and therefore \(\overline{a}\) is an element of maximum order in \(\overline{G}\).

By induction, we know that \(\overline{G}\) can be written in the form \(\langle \overline{a} \rangle \times \overline{K}\) for some subgroup \(\overline{K}\) of \(\overline{G}\).

Let \(K\) be the pullback of \(\overline{K}\) under the natural homomorphism from \(G\) to \(\overline{G}\) (i.e., \(K = \{x \in G \mid \overline{x} \in \overline{K}\}\)). Note that \(\langle b \rangle \subseteq K\) since \(\overline{b} = \overline{e} \in \overline{K}\).

We claim \(\langle a \rangle \cap K = \{e\}\). For if \(x \in \langle a \rangle \cap K\), then \(\overline{x} \in \langle \overline{a} \rangle \cap \overline{K} = \{\overline{e}\}\), which means \(x \in \langle b \rangle\). Thus \(x \in \langle a \rangle \cap \langle b \rangle = \{e\}\).

Now we show \(G = \langle a \rangle K\). Since \(\langle a \rangle \cap K = \{e\}\) and \(|K| = |\overline{K}| |\langle b \rangle| = |\overline{K}| p\), we have: \[ |\langle a \rangle K| = \frac{|\langle a \rangle||K|}{|\langle a \rangle \cap K|} = |\langle a \rangle||K| = |\langle \overline{a} \rangle| |\overline{K}| p = |\overline{G}| p = |G|. \] Thus \(\langle a \rangle K = G\), and since \(\langle a \rangle \cap K = \{e\}\), we conclude \(G = \langle a \rangle \times K\).

We proceed by induction on \(|G|\). Clearly, the case where \(|G| = p\) is true.

Now suppose that the statement is true for all Abelian groups of order less than \(|G|\). For any Abelian group \(L\), the set \(L^p = \{x^p \mid x \in L\}\) is a subgroup of \(L\), and is a proper subgroup if \(p\) divides \(|L|\). It follows that \[ G^p = H_1^p \times H_2^p \times \cdots \times H_{m'}^p = K_1^p \times K_2^p \times \cdots \times K_{n'}^p, \] where \(m'\) is the largest integer \(j\) such that \(|H_j| > p\), and \(n'\) is the largest integer \(i\) such that \(|K_i| > p\). (This ensures that our two direct products for \(G^p\) do not have trivial factors.)

Since \(|G^p| < |G|\), we have, by induction, \(m' = n'\) and \(|H_i^p| = |K_i^p|\) for \(i = 1, \ldots, m'\). Since \(|H_i^p| = |H_i|/p\) and \(|K_i^p| = |K_i|/p\) for \(i = 1, \ldots, m'\), this proves that \(|H_i| = |K_i|\) for all \(i = 1, \ldots, m'\).

All that remains to be proved is that the number of \(H_i\) of order \(p\) equals the number of \(K_i\) of order \(p\); that is, \(m - m' = n - n'\) (since \(m' = n'\)).

This follows directly from the facts that \[ |H_1||H_2| \cdots |H_{m'}| \cdot p^{m-m'} = |G| \quad \text{and} \quad |K_1||K_2| \cdots |K_{n'}| \cdot p^{n-n'} = |G|. \] Since \(|H_i| = |K_i|\) for \(i = 1, \ldots, m'\) and \(m' = n'\), we have \(p^{m-m'} = p^{n-n'}\), hence \(m - m' = n - n'\).

Therefore \(m = n\), and \(|H_i| = |K_i|\) for all \(i\).

Since \(72 = 2^3 \cdot 3^2\):

For \(2^3\): partitions of 3 are \(\{3\}\), \(\{2, 1\}\), \(\{1, 1, 1\}\).
For \(3^2\): partitions of 2 are \(\{2\}\), \(\{1, 1\}\).

Combining (\(3 \times 2 = 6\) possibilities):

• \(\mathbb{Z}_8 \times \mathbb{Z}_9 \cong \mathbb{Z}_{72}\)
• \(\mathbb{Z}_8 \times \mathbb{Z}_3 \times \mathbb{Z}_3\)
• \(\mathbb{Z}_4 \times \mathbb{Z}_2 \times \mathbb{Z}_9\)
• \(\mathbb{Z}_4 \times \mathbb{Z}_2 \times \mathbb{Z}_3 \times \mathbb{Z}_3\)
• \(\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_9\)
• \(\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_3 \times \mathbb{Z}_3\)

Therefore, there are exactly six non-isomorphic Abelian groups of order 72.

In the RSA cryptosystem (Rivest, Shamir, Adleman, 1978), we work in \(U(n)\) where \(n = pq\) for large primes \(p, q\). By the Chinese Remainder Theorem for groups: \[ U(pq) \cong U(p) \times U(q) \cong \mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1}. \]

This decomposition enables CRT-based RSA decryption, a standard optimization used in practice. Instead of computing \(m = c^d \bmod n\) directly with the large private exponent \(d\), we compute separately: \[ m_p = c^{d_p} \bmod p, \quad m_q = c^{d_q} \bmod q \] where \(d_p = d \bmod (p-1)\) and \(d_q = d \bmod (q-1)\) are much smaller exponents. The results are then combined using the Chinese Remainder Theorem to obtain \(m \bmod n\). This method provides significant speedup in RSA decryption and signature generation.

References

• R. L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Vol. 21, No. 2, pp. 120-126, 1978.
• A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997, Chapter 8 (Public-Key Encryption), pp. 285-291.