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 G1 and G2 are groups, H1 ≤ G1 and H2 ≤ G2. Then, (H1 ⊕ H2) ≤ (G1 ⊕ G2)
Proof.
∀ a, b ∈ H1 ⊕ H2, a = (a1, a2), b = (b1, b2), a1, b1 ∈ H1, a2, b2 ∈ H2 ⇒ [H1 ≤ G1 and H2 ≤ G2] ∃b1-1 ∈ H1, b2-1 ∈ H2 such that a·b-1 = (a1, a2)·(b1-1, b2-1) = (a1·b1-1, a2·b2-1) ∈ H1 ⊕ H2∎
Lemma 2. If G1, G2, H1, H2 are groups such that G1 ≋ H1 and G2 ≋ H2, then G1 ⊕ G2 ≋ H1 ⊕ H2
Proof.
Since G1 ≋ H1 and G2 ≋ H2 ⇒ ∃Φ1: G1 → H1, Φ2: G2 → H2 isomorphism.
Define a function Φ: G1 ⊕ G2 → H1 ⊕ H2, by Φ(g1, g2) = (Φ1(g1), Φ2(g2)). 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, ⟨ak⟩=⟨agcd(n,k)⟩ and |⟨ak⟩| = $\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 G1, G2, and Gn be finite cyclic groups. Then, their external direct product G1 ⊕ G2 ⊕ ··· ⊕ Gn is cyclic if and only if their orders are coprime(relatively prime),i.e., |Gi| and |Gj| are relatively prime ∀i ≠ j.
Corollary. Let m = n1n2···nk. Then, ℤm, that is, (ℤn1n2···nk) is isomorphic to ℤn1 ⊕ ℤn2 ⊕ ··· ⊕ ℤnk if and only if ni and nj are relatively prime, ∀i ≠ j, i.e., ℤn1n2···nk ≋ ℤn1 ⊕ ℤn2 ⊕ ··· ⊕ ℤnk ↭ (ni, nj) = 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, Us(st) ≈ U(t) and Ut(st) ≈ U(s)
Recall. Un = {[k]| gcd(k, n) = 1}, that is, Un consists of all [k], where k is relatively prime to n, e.g., U8 = {[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. Uk(n) = {x ∈ U(n): x mod k = 1}, Uk(n) ≤ U(n), e.g., U105(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, Φ’: Us(st) → U(t), Φ’(x) = (x mod t), Φ’’: Us(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 n1n2···nk, where each of the factors is relatively prime to all of the others (∀i, j, i ≠ j, gcd(ni, nj) = 1). Then, U(m) ≋ U(n1)⊕U(n2)⊕···⊕U(nk).
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).
U7(21) = {1, 8}, U3(21) = {1, 4, 10, 13, 16, 19}. Φ’: U7(21) → U(3), Φ’(x) = x mod 3. Φ’’: U3(21) → U(7), Φ’’(x) = x mod 7.
Theorem (Gauss, 1801). U(2) = {1} ≋ {0}, U(4) = {1, 3} ≋ ℤ2. U(2n) ≋ U(22) ⊕ U(2n-2) ≋ ℤ2⊕ℤ2n-2 ∀n ≥ 3, U(pn) ≋ ℤ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(23) = {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(52) ≋[U(pn) ≋ ℤpn-pn-1 for p a positive integer and an odd prime] ℤ52-51, i.e., U(25) ≋ ℤ20.
U(16) ≋[U(2n) ≋ ℤ2⊕ℤ2n-2 ∀n ≥ 3] ℤ2 ⊕ ℤ4, U(9) ≈[9 = 32, 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) ⇒ (an, bn) = (1, 1) ⇒[The only elements of finite order in ℝ* are 1 and -1] an = bn = 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 U105 = ℤ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.