I have yet to see any problem, however complicated, which, when looked at in the right way did not become still more complicated, Paul Anderson.
Theorem. If r is a divisor of m and s is a divisor of n, ℤ_{m} ⊕ ℤ_{n} has a subgroup isomorphic to ℤ_{r} ⊕ ℤ_{s}.
Lemma 1. Suppose G_{1} and G_{2} are groups, H_{1} ≤ G_{1} and H_{2} ≤ G_{2}. Then, (H_{1} ⊕ H_{2}) ≤ (G_{1} ⊕ G_{2})
Proof.
∀ a, b ∈ H_{1} ⊕ H_{2}, a = (a_{1}, a_{2}), b = (b_{1}, b_{2}), a_{1}, b_{1} ∈ H_{1}, a_{2}, b_{2} ∈ H_{2} ⇒ [H_{1} ≤ G_{1} and H_{2} ≤ G_{2}] ∃b_{1}^{-1} ∈ H_{1}, b_{2}^{-1} ∈ H_{2} such that a·b^{-1} = (a_{1}, a_{2})·(b_{1}^{-1}, b_{2}^{-1}) = (a_{1}·b_{1}^{-1}, a_{2}·b_{2}^{-1}) ∈ H_{1} ⊕ H_{2}∎
Lemma 2. If G_{1}, G_{2}, H_{1}, H_{2} are groups such that G_{1} ≋ H_{1} and G_{2} ≋ H_{2}, then G_{1} ⊕ G_{2} ≋ H_{1} ⊕ H_{2}
Proof.
Since G_{1} ≋ H_{1} and G_{2} ≋ H_{2} ⇒ ∃Φ_{1}: G_{1} → H_{1}, Φ_{2}: G_{2} → H_{2} isomorphism.
Define a function Φ: G_{1} ⊕ G_{2} → H_{1} ⊕ H_{2}, by Φ(g_{1}, g_{2}) = (Φ_{1}(g_{1}), Φ_{2}(g_{2})). It is pretty easy to show that Φ is indeed an isomorphism.
Proof. (Main Theorem)
Recall the following Theorem. Let a be an arbitrary element of order n in a group G, and let k be a positive integer. Then, ⟨a^{k}⟩=⟨a^{gcd(n,k)}⟩ and |⟨a^{k}⟩| = $\frac{n}{gcd(n,k)}.$
If r is a divisor of m and s is a divisor of n, the subgroup ⟨m/r⟩ ≤ ℤ_{m} is cyclic of order r (so it is isomorphic to ℤ_{r}) and the subgroup ⟨n/s⟩ ≤ ℤ_{n} is cyclic of order s (so it is isomorphic to ℤ_{s}) ⇒ [Lemma 1] ⟨m/r⟩ ⊕ ⟨n/s⟩ ≤ ℤ_{m} ⊕ ℤ_{m} and [By Lemma 2] isomorphic to ℤ_{r} ⊕ ℤ_{s} ∎
Criterion for the direct product to be cyclic. Let G and H be finite cyclic groups. Then, the external direct product of both groups G ⊕ H is cyclic if and only if their orders are relatively prime,i.e., |G| and |H| are relatively prime, (|G|, |H|) = 1.
Proof.
⇒) |G| = m, |H| = n, |G ⊕ H| = nm. Let’s assume G ⊕ H is cyclic, ∃ g∈ G, h ∈H such that G ⊕ H = ⟨(g, h)⟩, let d = gcd(n,m).
$(g, h)^{\frac{mn}{d}}=(g^{\frac{mn}{d}}, h^{\frac{mn}{d}})=((g^{m})^{\frac{n}{d}},(h^{n})^{\frac{m}{d}})=(e^{\frac{n}{d}},e’^{\frac{m}{d}})$ = (e, e’) where e and e’ are the identity in G and H respectively, and mn/d, n/d and m/d are integers by the gcd definition ⇒ [|G ⊕ H| = nm and by assumption, G ⊕ H = ⟨(g, h)⟩] |(g, h)| = nm ≤ mn/d ⇒ d = 1.
⇐) Suppose |G| = m, |H| = n, d = gcd(n, m) = 1, G = ⟨g⟩, H = ⟨h⟩ ⇒ [Order of an Element in a Direct Group] ⟨(g, h)⟩ = lcm(n, m) ⇒ [gcd(n, m) = 1] = nm, |G ⊕ H| = nm, and therefore (g, h) is a generator of G ⊕ H.
Using an induction argument and this criterion, we can generalize this result.
Theorem. Let G_{1}, G_{2}, and G_{n} be finite cyclic groups. Then, their external direct product G_{1} ⊕ G_{2} ⊕ ··· ⊕ G_{n} is cyclic if and only if their orders are coprime(relatively prime),i.e., |G_{i}| and |G_{j}| are relatively prime ∀i ≠ j.
Corollary. Let m = n_{1}n_{2}···n_{k}. Then, ℤ_{m}, that is, (ℤ_{n1n2···nk}) is isomorphic to ℤ_{n1} ⊕ ℤ_{n2} ⊕ ··· ⊕ ℤ_{nk} if and only if n_{i} and n_{j} are relatively prime, ∀i ≠ j, i.e., ℤ_{n1n2···nk} ≋ ℤ_{n1} ⊕ ℤ_{n2} ⊕ ··· ⊕ ℤ_{nk} ↭ (n_{i}, n_{j}) = 1, ∀i ≠ j.
Examples:
+ | (0,0) | (0,1) | (0,2) | (1,0) | (1,1) | (1,2) |
---|---|---|---|---|---|---|
(0,0) | (0,0) | (0,1) | (0,2) | (1,0) | (1,1) | (1,2) |
(0,1) | (0,1) | (0,2) | (0,0) | (1,1) | (1,2) | (1,0) |
(0,2) | (0,2) | (0,0) | (0,1) | (1,2) | (1,0) | (1,1) |
(1,0) | (1,0) | (1,1) | (1,2) | (0,0) | (0,1) | (0,2) |
(1,1) | (1,1) | (1,2) | (1,0) | (0,1) | (0,2) | (0,0) |
(1,2) | (1,2) | (1,0) | (1,1) | (0,2) | (0,0) | (0,1) |
The only two proper subgroups are {(0, 0), (1, 0)} and {(0, 0), (0, 1), (0, 2)}
Theorem. Suppose s and t are relatively prime. Then, U(st)≈U(s)⊕U(t), i.e., U(st) is isomorphic to the external direct product of U(s) and U(t). Futhermore, U_{s}(st) ≈ U(t) and U_{t}(st) ≈ U(s)
Recall. U_{n} = {[k]| gcd(k, n) = 1}, that is, U_{n} consists of all [k], where k is relatively prime to n, e.g., U_{8} = {[1], [3], [5], [7]}, [3]^{2} = [9] = [1], [5]^{2} = [25] = [1], and [7]^{2} = [49] = [1], so all its elements (except the identity) have order two.
Recall. U_{k}(n) = {x ∈ U(n): x mod k = 1}, U_{k}(n) ≤ U(n), e.g., U_{105}(5) = {1, 11, 16, 26, 31, 41, 46, 61, 71, 76, 86, 101}.
Proof. Let’s define an isomorphism, Φ: U(st) → U(s)⊕U(t), Φ(x) = (x mod s, x mod t). Analogously, Φ’ and Φ’’ are both isomorphisms, Φ’: U_{s}(st) → U(t), Φ’(x) = (x mod t), Φ’’: U_{s}(st) → U(s), Φ’’(x) = (x mod s).
Φ: U(st) → U(s)⊕U(t), Φ(x) = (x mod s, x mod t).
θ is Euler’s totient function, it counts the positive integers up to a given integer n that are relatively prime to n. It is a multiplicative function, meaning that if two numbers m and n are relatively prime, then θ(mn) = θ(m)θ(n).
Corollary. Let m be a integer that can be factored as n_{1}n_{2}···n_{k}, where each of the factors is relatively prime to all of the others (∀i, j, i ≠ j, gcd(n_{i}, n_{j}) = 1). Then, U(m) ≋ U(n_{1})⊕U(n_{2})⊕···⊕U(n_{k}).
Examples:
|U(21)| = 12. U(3) = {1, 2}, |U(3)| = 2; and U(7) = {1, 2, 3, 4, 5, 6}, |U(7)| = 6;
Φ: U(st) → U(s)⊕U(t), Φ(x) = (x mod s, x mod t). In particular, Φ: U(21) → U(3)⊕U(7), Φ(x) = (x mod 3, x mod 7).
U_{7}(21) = {1, 8}, U_{3}(21) = {1, 4, 10, 13, 16, 19}. Φ’: U_{7}(21) → U(3), Φ’(x) = x mod 3. Φ’’: U_{3}(21) → U(7), Φ’’(x) = x mod 7.
Theorem (Gauss, 1801). U(2) = {1} ≋ {0}, U(4) = {1, 3} ≋ ℤ_{2}. U(2^{n}) ≋ U(2^{2}) ⊕ U(2^{n-2}) ≋ ℤ_{2}⊕ℤ_{2n-2} ∀n ≥ 3, U(p^{n}) ≋ ℤ_{pn-pn-1} for p a positive integer and an odd prime.
Theorem. Every group U(n) is isomorphic to the external direct product of cyclic groups.
U(55) ≋[Criterion for the direct product to be cyclic] U(5) ⊕ U(11) ≋ ℤ_{4}⊕ℤ_{10} ≋ ℤ_{4}⊕ℤ_{2}⊕ℤ_{5}
U(8) = U(2^{3}) = {1, 3, 5, 7} has 4 elements and is non-cyclic since each element (except the identity 1) has order 2. U(8) ≋ ℤ_{2}⊕ℤ_{2}.
If p = 5, n = 2, U(5^{2}) ≋[U(p^{n}) ≋ ℤ_{pn-pn-1} for p a positive integer and an odd prime] ℤ_{52-51}, i.e., U(25) ≋ ℤ_{20}.
U(16) ≋[U(2^{n}) ≋ ℤ_{2}⊕ℤ_{2n-2} ∀n ≥ 3] ℤ_{2} ⊕ ℤ_{4}, U(9) ≈[9 = 3^{2}, 2 ≱ 3] ℤ_{6}, U(7) ≋ ℤ_{6}, U(5) ≋ ℤ_{4}, U(3) ≈ ℤ_{2}.
U(105) ≋ [105 = 3·5·7] U(3)⊕U(5)⊕U(7) ≋ ℤ_{2} ⊕ ℤ_{4} ⊕ ℤ_{6}. |U(105)| = 2 × 4 × 6 = 48.
U(100) ≋ U(4) ⊕ U(25) ≋ ℤ_{2} ⊕ ℤ_{20}
U(168) ≋ [168 = 3·7·8] U(3)⊕U(7)⊕U(8) ≋ ℤ_{2} ⊕ ℤ_{6} ⊕ ℤ_{2} ⊕ ℤ_{2}.
U(720) ≋ [720 = 16·9·5] U(16)⊕U(9)⊕U(5) ≋ ℤ_{2} ⊕ ℤ_{4} ⊕ ℤ_{6} ⊕ ℤ_{4}.
What are the possible orders of U(720)? U(720) ≋ ℤ_{2} ⊕ ℤ_{4} ⊕ ℤ_{6} ⊕ ℤ_{4}, so |(a, b, c, d)| = lcm(|a|, |b|, |c|, |d|) = {1, 2, 3, 4, 6, 12} because |a|= 1 or 2, |b| = |d| = 1, 2, or 4, |c| = 1, 2, 3 or 6.
Prove that ℝ* ⊕ ℝ* is not isomorphic to ℂ*. For the sake of contradiction, let’s suppose there exists an isomorphism Φ: ℂ* → ℝ* ⊕ ℝ*, |i| = 4 ⇒ [Isomorphisms preserve order of elements] |Φ(i)| = 4 ⊥ because we claim that the only elements of finite order in ℝ* ⊕ ℝ* are {(1, 1), (-1, 1), (1, -1), (-1, -1)} and all these elements have order either 1 or 2.
Claim. Let’s Suppose (a, b) ∈ ℝ* ⊕ ℝ* has finite order ⇒ ∃n: (a, b)^{n} = (1, 1) ⇒ (a^{n}, b^{n}) = (1, 1) ⇒[The only elements of finite order in ℝ* are 1 and -1] a^{n} = b^{n} = 1 ⇒ a = ±1, b = ±1.
Case 1. |b| = 4 (there are two choices, i.e., 1 and 3), |c| = 3 (2, 4) or 6 (1, 5). We need to count 2 (|a|)·2(|b|)·4(|c|)·4(|d|) = 64.
Case 2. |d| = 4, |c| = 3 or 6. Besides, we need to add 2 (|a|)·2(|b| because we have already counted |b|=4, so |b|=1 or |b|=2, i.e., b = 0 or 2)·4(|c|)·2(|d|) = 32. Therefore, 64+32= 96 elements of order 12.
Let $\left(\begin{smallmatrix}1 & a & b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right),\left(\begin{smallmatrix}1 & c & d\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$ ∈ H, then $\left(\begin{smallmatrix}1 & a & b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)\left(\begin{smallmatrix}1 & c & d\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)=\left(\begin{smallmatrix}1 & c+a & d+b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$ ∈ H, so it is closed under matrix multiplication.
Futhermore, $\left(\begin{smallmatrix}1 & c & d\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)\left(\begin{smallmatrix}1 & a & b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)=\left(\begin{smallmatrix}1 & a+c & b+d\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right) = \left(\begin{smallmatrix}1 & c+a & d+b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$, and therefore H is Abelian.
Matrix multiplication is associative, $\left(\begin{smallmatrix}1 & 0 & 0\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$ is the identity element, and $\left(\begin{smallmatrix}1 & -a & -b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$ is the inverse of $\left(\begin{smallmatrix}1 & a & b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$. Therefore, H is an Abelian group.
Futhermore, Φ: ℤ_{3} ⊕ ℤ_{3} → H defined by Φ(a, b) = $\left(\begin{smallmatrix}1 & a & b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$ is an isomorphism. It is clear that Φ is a bijection, and Φ((a, b) + (c, d)) = Φ(a + c, b + d) = $\left(\begin{smallmatrix}1 & a + c & b + d\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right) = \left(\begin{smallmatrix}1 & a & b\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)\left(\begin{smallmatrix}1 & c & d\\ 0 & 1 & 0\\0 & 0 & 1\end{smallmatrix}\right)$ = Φ(a, b)Φ(c, d) ⇒ Φ is an homomorphism ⇒ Φ is an isomorphism ⇒ H ≋ ℤ_{3} ⊕ ℤ_{3}.
Isomorphisms preserves order, i.e., ∀a ∈ ℤ_{105}, |a| = |Φ(a)|, and we also know that Aut(ℤ_{105}) ≈ U(105).
How many elements of order 12 are there in U_{105} = ℤ_{2} ⊕ ℤ_{4} ⊕ ℤ_{6}? If (a, b, c) ∈ ℤ_{2} ⊕ ℤ_{4} ⊕ ℤ_{6} has order 12 ⇒ lcm (|a|, |b|, |c|) = 12 ⇒ |b| = 4 (b=1 or 3 -gcd(4, 3) = 1), |c| = 3 (c=2 or 4) or |c| = 6 (c = 1 or 5). Total elements of order 12 = 2 (|a|) x 2 (|b|) x 4 (|c|) = 16. There are 16 automorphisms of order 12.
Isomorphisms preserves order, i.e., ∀a ∈ ℤ_{720}, |a| = |Φ(a)|, and we also know that Aut(ℤ_{720}) ≈ U(720). Therefore (previous exercise), there are 96 elements of order 12 in U(720), and 96 automorphism of ℤ_{720} of order 12.