💾 Archived View for 7irb.tk › maths › group › 16.md captured on 2022-04-29 at 11:45:28.
⬅️ Previous capture (2022-04-28)
-=-=-=-=-=-=-
# 16. Automorphisms of cyclic groups
In this lesson, we try to classify groups of order $15$, and more generally, groups of order $pq$ where $p$ and $q$ are two different prime numbers. It turns out that a study on the possible automorphisms of a cyclic group is necessary for such classification to be carried out.
## 16.1 A lemma about $\varphi(n)$
<span style="color:darkorchid">**Lemma 1:** In the cyclic group $\mathbb{Z}_n$, there are exactly $\varphi(d)$ elements of order $d$, for every $d|n$.
Since every element of $\mathbb{Z}_n$ must be of some order $d|n$, this lemma implies the following property of the Euler $\varphi$ function:
<span style="color:darkorchid">**Lemma 2:**$\sum_{d|n,\ 1\leq d\leq n}\varphi(d) = n.$
<span style="color:deeppink">**Proof of Lemma 1:** When $n=1$, the group is just the trivial group with exactly $1$ element of order $\varphi(1)=1$, hence the lemma holds. Assume that the lemma has also been proven for $\mathbb{Z}_2$, $\mathbb{Z}_3$, ... up to $\mathbb{Z}_{n-1}$.
<span style="color:deeppink">Consider $\mathbb{Z}_n$. An element of order $n$ is a generator of this group. That is, $mx\equiv 1~(\mathrm{mod}~n)$, where $x$ is the element in question, and $m$ is some integer. This implies that $x$ and $n$ are coprime. Therefore, the number of elements of order $n$ is just the number of integers coprime to $n$, which is by definition $\varphi(n)$.
<span style="color:deeppink">For any $d|n$ ($d\neq n$), an element of order $d$ within group $\mathbb{Z}_n$ generates a cyclic subgroup of order $d$. But $\mathbb{Z}_n$ has only one such subgroup, namely $\{1, \frac{n}{d}, \frac{2n}{d}, \cdots, \frac{(d-1)n}{d}\}$. Consequently, all elements of order $d$ within group $\mathbb{Z}_n$ are exactly the elements of order $d$ within this subgroup. By assumption, the number of such elements is $\varphi(d)$. This proves Lemma 1. $\square$
See Section 16.6 for a proof of Lemma 2 without using group theory.
## 16.2 Automorphisms of cyclic groups
Consider the cyclic group $\mathbb{Z}_n$. An automorphism of this group must map $1$ to some non-zero element $x$, and $x$ must be a generator of $\mathbb{Z}_n$, in other words, $x\in \mathbb{Z}^*_n$. If two automprphisms map $1$ to $x$ and $y$ respectively, then their composition (the order does not matter here) is another automorphism mapping $1$ to $xy$. Hence $\mathrm{Aut}(\mathbb{Z}_n) = \mathbb{Z}^*_n$
Here is a table of the structure of groups $\mathbb{Z}^*_n$ with $1\leq n\leq 12$
| Group | Element(s) | Isomorphic to | Generator(s) (if cyclic) |
|-------------------|-------------------------------|-----------------|--------------------------|
| $\mathbb{Z}^*_1$ | None | $\emptyset$ | |
| $\mathbb{Z}^*_2$ | 1 | $\{1\}$ | 1 |
| $\mathbb{Z}^*_3$ | 1, 2 | $\mathbb{Z}_2$ | 2 |
| $\mathbb{Z}^*_4$ | 1, 3 | $\mathbb{Z}_2$ | 3 |
| $\mathbb{Z}^*_5$ | 1, 2, 3, 4 | $\mathbb{Z}_4$ | 2, 3 |
| $\mathbb{Z}^*_6$ | 1, 5 | $\mathbb{Z}_2$ | 5 |
| $\mathbb{Z}^*_7$ | 1, 2, 3, 4, 5, 6 | $\mathbb{Z}_6$ | 3, 5 |
| $\mathbb{Z}^*_8$ | 1, 3, 5, 7 | $K_4$ | |
| $\mathbb{Z}^*_9$ | 1, 2, 4, 5, 7, 8 | $\mathbb{Z}_6$ | 2, 5 |
| $\mathbb{Z}^*_{10}$ | 1, 3, 7, 9 | $\mathbb{Z}_4$ | 3, 7 |
| $\mathbb{Z}^*_{11}$ | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 | $\mathbb{Z}_{10}$ | 2, 6, 7, 8 |
| $\mathbb{Z}^*_{12}$ | 1, 5, 7, 11 | $K_4$ | |
## 16.3 Structure of $\mathbb{Z}^*_p$, with $p$ prime
<span style="color:darkorchid">**Proposition 3:** The group $\mathbb{Z}^*_p$ is just a cyclic group of order $p-1$. That is, $\mathbb{Z}^*_p \cong \mathbb{Z}_{p-1}$.
<span style="color:deeppink">**Proof:** We only need to show that $\mathbb{Z}^*_p$ contains an element of order $p-1$.
<span style="color:deeppink">If we can demonstrate that, for any $d|(p-1)$, there are **at most** $\varphi(d)$ elements of order $d$ in this group, we are done, because Lemma 2 will then imply that there are **exactly** $\varphi(d)$ elements of order $d$, otherwise the total number of elements do not add up.
<span style="color:deeppink">The fact that there are **at most** $\varphi(d)$ elements of order $d$ in $\mathbb{Z}^*_p$ is also easy to show: suppose there is **one** element $g$ of order $d$, then it must generate a cyclic subgroup of order $d$: $\{1, g, g^2, \cdots, g^{d-1}\}$. It is evident that all these $d$ elements are roots of the equation $x^d=1$ over the **field** $\mathbb{Z}_p$. The point is, this subgroup must contain all elements of $\mathbb{Z}^*_p$ of order $d$. Otherwise, the equation $x^d=1$ will have more than $d$ roots, which is impossible. By Lemma 1, we see that the number of elements of order $d$ is thus $\varphi(d)$. Note that this is under the assumption that there is **one** element $g$ of order $d$. By this way of reasoning alone we have not yet ruled out the possibility that there is **no** element of order $d$. However, by the reasoning of the previous paragraph, we now see that that there are **exactly** $\varphi(d)$ elements of order $d$. In particular, there is some element of order $p-1$. $\square$
## 16.4 Classification of groups of order $pq$ where $p$ and $q$ are primes
We are now at a point where we can classify groups of order $pq$ with $p$ and $q$ both prime. The case where $p=q$ has already been treated in lesson 11. We now focus on the case where $p<q$.
According to the Sylow theorems, there is at least one subgroup of order $q$, and one subgroup of order $p$. In particular, the number of $q$-subgroups not only divides $p$, but also equals $1$ mod $q$. The only possibility is that there is only one, hence normal, $q$-subgroup.
Denote this $q$-subgroup by $K$, and also choose one $p$-subgroup $H$. We see that every element of this group can be uniquely written as $hk$, where $h\in H$ and $k\in K$. Therefore, the entire group is a semidirect product $H \ltimes K$, or more explicitly, $\mathbb{Z}_p\ltimes\mathbb{Z}_q$.
To construct this semidirect product, we need to study the ways that $\mathbb{Z}_p$ can act on $\mathbb{Z}_q$, or equivalently, the ways that $\mathbb{Z}_p$ can be homomorphically mapped into the group of automorphisms of $\mathbb{Z}_q$, namely $\mathbb{Z}^*_{q}$, which is in turn isomorphic to $\mathbb{Z}_{q-1}$.
There are only two different ways that a homomorphism can be established from $\mathbb{Z}_p$ to another group:
(i) The kernel is $\mathbb{Z}_p$ itself. In this case, all of $\mathbb{Z}_p$ maps to $1$ of $\mathbb{Z}_q^*$. That is to say, the action of $\mathbb{Z}_p$ on $\mathbb{Z}_q$ is trivial, and the resulting group is the direct product $\mathbb{Z}_p\times\mathbb{Z}_q$.
(ii) The kernel is the identity. This embeds $\mathbb{Z}_p$ into $\mathbb{Z}_q^*$, which is possible if and only if $p|(q-1)$, and uniquely defines a semidirect product $\mathbb{Z}_p\ltimes\mathbb{Z}_q$.
To summarize:
<span style="color:darkorchid">**Proposition 4:** $~p$ and $q$ are both prime numbers, $p<q$. If $p$ does not divide $q-1$, the only group of order $pq$ is the cyclic group $\mathbb{Z}_{pq}$. Otherwise, there are only two possibilities: the cyclic group $\mathbb{Z}_{pq}$, or a semidirect product $\mathbb{Z}_p\ltimes\mathbb{Z}_q$.
In particular, $15=3\times 5$, and $3$ does not divide $5-1$. Therefore, the cyclic group $\mathbb{Z}_{15}$ is the only group of order $15$.
Putting $p=2$ and $q=$any odd prime in Proposition 4, we see that the only possible structures for a group of order $2q$ is the cyclic group, and the dihedral group.
## 16.5 Structure of $\mathbb{Z}^*_m$, with general $m$
From Lesson 5, we already know that, if $m = {p_1}^{a_1}{p_2}^{a_2}\cdots {p_r}^{a_r}$ where $p_1, p_2, \cdots, p_r$ are different primes,$\mathbb{Z}^*_m = \mathbb{Z}^*_{p_1^{a_1}}\times \mathbb{Z}^*_{p_2^{a_2}}\times\cdots\times\mathbb{Z}^*_{p_r^{a_r}}.$Therefore, we only need to figure out the structure of $\mathbb{Z}^*_{p^n}$ with $p$ prime. The general result is as follows:
<span style="color:darkorchid">**Proposition 5:** When $p$ is an odd prime, $\mathbb{Z}^*_{p^n}$ ($n \geq 2$) is just a cyclic group of order $\varphi(p^n)$ (which equals $p^{n-1}(p-1)$). When $p=2$, $\mathbb{Z}^*_{2^n}$ is isomorphic to $\mathbb{Z}_2\times\mathbb{Z}_{2^{n-2}}$.
<span style="color:deeppink">**Proof of proposition 5 for $p$ an odd prime:** This proof will be carried out in 2 steps.
<span style="color:deeppink">*Step 1.* We prove that the element $p+1$ in $\mathbb{Z}^*_{p^n}$ has order $p^{n-1}$. That is, $(p+1)^{p^{n-1}}=1$, and $(p+1)^{p^{n-2}}\neq1$ in $\mathbb{Z}^*_{p^n}$. To do this, we explicitly compute these quantities in $\mathbb{Z}$ using the binomial theorem:$(1+p)^{p^{n-1}}=1+p^{n-1}p +\frac{p^{n-1}(p^{n-1}-1)}{1\cdot 2}p^2 +\frac{p^{n-1}(p^{n-1}-1)(p^{n-1}-2)}{1\cdot 2\cdot 3}p^3 + \cdots.$For an odd prime $p$, the second and third terms on the right hand side are both divisible by $p^n$. All terms starting from the fourth term are of the form$\frac{p^{n+m-1}(p^{n-1}-1)(p^{n-1}-2)\cdots(p^{n-1}-m+1)}{1\cdot 2\cdot \cdots \cdot m}.$This, as it turns out, is also divisible by $p^n$. At first sight, it seems that the denominator may pose a challenge here, but every factor $l$ in the denominator, if divisible by some power of $p$, will have a corresponding factor $(p^{n-1}-l)$ in the numerator that is also divisible by the same power of $p$. That is, except for $m$ itself. But $m$ contains at most $p^{m-2}$ in its prime decomposition (since $p^{m-2}\geq m$ for any $p\geq 3$ and $m \geq 3$), so the entire expression is divisible by $p^{n+1}$, let alone by $p^n$, and we now have $(1+p)^{p^{n-1}}\equiv 1$ ($\mathrm{mod}\ p^n$).
<span style="color:deeppink">What about $(1+p)^{p^{n-2}}$? By the same reasoning, we can show that it is equal to $1+p^{n-1}$ plus something that is divisible by $p^n$. Thus $(p+1)^{p^{n-2}}\not\equiv 1$ ($\mathrm{mod}\ p^n$), and step 1 is complete.
<span style="color:deeppink">*Step 2.* The element $p+1$ generates a cyclic subgroup of order $p^{n-1}$ in $\mathbb{Z}^*_{p^n}$. Denote this subgroup by $N$, and form the quotient group $H=\mathbb{Z}^*_{p^n}/N$. Clearly $H$ has order $p-1$. If we can prove that $H$ is cyclic, we are done. In fact, we are going to prove that it is isomorphic to $\mathbb{Z}_p^*$.
<span style="color:deeppink">We first ask the following question: what are the elements of $H$? That is, what are the cosets of $N$ in $\mathbb{Z}^*_{p^n}$? There are $p-1$ cosets in total (including $N$ itself), and one obvious thing to try is $N, 2N, \cdots, (p-1)N$.
<span style="color:deeppink">Firstly, the numbers $1, 2, 3, \cdots, (p-1)$ are indeed in the group $\mathbb{Z}^*_{p^n}$, as they are coprime with $p$, let alone $p^n$. So $N, 2N, \cdots, (p-1)N$ are indeed cosets of $N$. But are any two of them the same? Let's say that $aN=bN$. This implies that for some $r$, the equation $a = b(p+1)^r$ holds in $\mathbb{Z}^*_{p^n}$, namely $a = b(p+1)^r + lp^n$ in $\mathbb{Z}$. Dividing by $p$, we see that $a \equiv b$ ($\mathrm{mod}\ p$). But both $a$ and $b$ come from the set $\{1, 2, 3, \cdots, (p-1)\}$, so the the only possibility is $a=b$. Therefore, $N, 2N, \cdots, (p-1)N$ are exactly the cosets of $N$.
<span style="color:deeppink">Secondly, consider the multiplication in $H$. Given two cosets $aN$ and $bN$, their product is $cN$ where $c\equiv ab$ ($\mathrm{mod}\ p^n$). But actually, $c$ is also congruent to $ab$ mod $p$, as $ab-c$, being divisible by $p^n$, is obviously also divisible by $p$. Now it is evident that $H$ is structurally equivalent to $\mathbb{Z}_p^*$. $\square$
This proof is not applicable to $p=2$, because when $p=2$, the element $p+1$ no longer has order $p^{n-1}$.
<span style="color:deeppink">**Proof of proposition 5 for $p=2$:** The method is similar. Here we just give an outline in 3 steps.
<span style="color:deeppink">*Step 1.* Prove that $\{1, 2^n-1\}$ is a subgroup of order $2$.
<span style="color:deeppink">*Step 2.* Prove that $5$ generates a subgroup of prder $2^{n-2}$. In particular, prove that $5^{2^{n-2}}=1$, but $5^{2^{n-3}}=1+2^{n-1}\neq 1$ in $\mathbb{Z}_{2^n}^*$.
<span style="color:deeppink">*Step 3.* Prove that the intersection of these two subgroups is $\{1\}$. $\square$
## 16.6 Appendix: Proof of Lemma 2 without using group theory
<span style="color:deeppink">**Proof of Lemma 2:** For every $d|n$ ($1\leq d\leq n$), define $S_d$ to be $S_d = \{1\leq x\leq n ~|~ \gcd(x, n) = d\}.$Note that, $\gcd(x, n) = d$ implies that $x$ is a multiple of $d$, and that $x/d$ and $n/d$ are coprime. That is, with slight abuse of notation,$S_d = d\times\left\{1\leq y\leq \frac{n}{d}~\left|~ \gcd\left(y, \frac{n}{d}\right)=1\right.\right\}.$We now see that $|S_d| = \varphi(\frac{n}{d})$. Also, $\{1,2,\cdots,n\} = \bigsqcup_{d|n,~1\leq d\leq n}S_d.$Counting the number of elememts on both sides, we have$n = \sum_{d|n,~1\leq d\leq n}\varphi\left(\frac{n}{d}\right).$But summing over quotients is the same as summing over divisors, hence$n = \sum_{d|n,~1\leq d\leq n}\varphi(d).$$\square$