循环群

定义

回顾一下循环群的定义，当我们说群可以由一个元素生成，我们就可以说这个群是循环群，具体的：$G=\{a^n\mid n\in Z\}$
$a$叫做$G$的生成元，记为$G=⟨a⟩$

例子

• 整数加法群是由$1$或$-1$生成的，幂$n$相当于乘$n$：即$1^2=2,1^0=0,1^{-1}=-1$，群元素相乘的意义上的计算。
• $Z_n$是循环群，生成元是$1$或$n-1$，彼此互逆；另外根据$n$的取值，还可能有其他生成元。如$Z_8=⟨3⟩=⟨5⟩$
• $U(10)$也是循环群，但$U(8)$不是循环群。

Theorem 4.1

设元素$a$属于群$G$，如果$a$有无限阶，$a^i=a^j\leftrightarrow i=j$；如果$a$有有限阶$n$，$a^i=a^j\leftrightarrow n\mid i-j$

证明：当$a$无限阶时，说明$a$的任何正整数次幂都不会为$e$，那么假设给定不等的$i<j$，$a^i=a^j\to a^{j-i}=e$，显然矛盾。那么说明$i=j$。
当$a$有限阶时，即$a^n=e$，如果不等的$i,j$使$a^i=a^j$，那么$i-j\ge n$，否则根据上面证明依旧会导出$a$的更小的阶。将$i-j$写为$qn+r,0<r<n$，那么$e=a^{i-j}=a^{qn}{a}^r=a^r$，由于$r<n$，且$n$是阶，那么必然有$r=0$，QED

Corollary 1

对于任何群都有$|a|=|⟨a⟩|$

这其实是Theorem 4.1的特例，即：无限阶元素生成的元素各不相等（仍然是无限阶），阶为$n$的元素只能生成$n$个元素的群（相当于幂在模$n$的意义上才有区别）。

Corollary 2

对群$G$和$n$阶元素$a\in G$来说，$a^k=e\to n\mid k$

这依旧是Theorem 4.1的特例，取$i,j$为$k,0$即可

Corollary 3

如果$a,b$属于一个有限群且$ab=ba$，那么$|ab|\mid |a||b|$

依旧用Theorem 4.1考虑，设$|ab|=n$，显然$(ab{)}^0=e，(ab{)}^{|a||b|}=a^{|a||b|}{b}^{|a||b|}=e$，根据定理4.1 必有：$n\mid |a||b|$

定理理解

根据定理和推论内容，以及证明过程，我们可以隐约把握到一些特殊的地方。这个定理的有限情况实际上在说这么一层意思：$⟨a⟩$中的乘积运算，和模$n$加法的操作很相像，即如果$i+j\mathrm{mod}n=k$，那么$a^i{a}^j=a^k$，故这个$a$生成的循环群和$Z_n$存在相似性；在阶无限情况下则和$Z$存在相似性。

基于以上理由，可以说$Z_n$和$Z$是所有循环群的“原型”，对这两个原型的研究将有助于理解所有循环群（实际上后面章节Chapter 6会说，这实际上是同构）。

Theorem 4.2

$a$是阶$n$的群元素，$k$是正整数，那么：$⟨a^k⟩=⟨a^{\gcd (n,k)}⟩$，$|a^k|=n/\gcd (n,k)$

证明：这是两个结论。

• 对于前者，自然想到的是$\gcd (n,k)=ns+kt$，$a^{\gcd (n,k)}=a^{kt}$，问题就变成了要证明$a^{kt}$与$a^k$生成同一个群，显然$⟨a^{kt}⟩\subseteq ⟨a^k⟩$，因为后者能生成前者。现在再回到$\gcd (n,k)$，设公约数为$d$，那么$k=dr$，显然$⟨a^k⟩\subseteq ⟨a^d⟩$，故$⟨a^k⟩\subseteq ⟨a^d⟩=⟨a^{\gcd (n,k)}⟩=⟨a^{kt}⟩\subseteq ⟨a^k⟩$，故两集合相等。
• 对于后者，先根据前者的结论以及Corollary 1将结论化简为$|a^d|=n/d$，首先$(a^d{)}^{n/d}=e$，那么$|a^d|\le n/d$；如果存在$i<n/d$使得$a^{di}=e$，那么将导出$di<n$才是$a$的阶，矛盾，故阶就是$n/d$

定理应用例子

• 对于$|a|=30$，找到$⟨a^{26}⟩,⟨a^{17}⟩,⟨a^{18}⟩,|a^{26}|,|a^{17}|,|a^{18}|$
  根据定理Theorem 4.2，$⟨a^{26}⟩=⟨a^2⟩=\{e,a^2,a^4,\cdots ,a^{28}\}$; 阶$30/2=15$
  $⟨a^{17}⟩=⟨a⟩=\{e,a,a^2,\cdots ,a^{29}\}$；阶$30/1=30$
  $⟨a^{18}⟩=⟨a^6⟩=\{e,a^6,a^{12},\cdots ,a^{24}\}$；阶$30/6=5$

Corollary 1

有限循环群元素的阶整除群的阶

这是Theorem 4.2的直接结论

Corollary 2

对于$|a|=n$
$⟨a^i⟩=⟨a^j⟩iif.\gcd (n,i)=\gcd (n,j)$
$|a^i|=|a^j|iif.\gcd (n,i)=\gcd (n,j)$

• 对于推论第一项，因为$⟨a^i⟩=⟨a^{\gcd (n,i)}⟩,⟨a^j⟩=⟨a^{\gcd (n,j)}⟩$，公约数相等当然这两个生成群相等；另一个方向上，根据Theorem 4.1的推论1，生成群相等，则生成元的阶相等，那么$|a^{\gcd (n,i)}|=|a^{\gcd (n,j)}|$，那么根据Theorem 4.2的后一个结论，$n/\gcd (n,i)=n/\gcd (n,j)$，可得公约数相等。
• 对于后一项，直接可以计算出两个阶为$n/\gcd (n,i)$和$n/\gcd (n,j)$，这个证明实际上只是上一项的一部分。

Corollary 3

$|a|=n$
$⟨a⟩=⟨a^j⟩iif.\gcd (n,j)=1$
$|a|=|⟨a^j⟩|iif.\gcd (n,j)=1$

这个和推论2证法一致。实际上就是前一个推论的特例

Corollary 4

$Z_n=⟨k⟩iif.\gcd (n,k)=1$

这又是推论3的特例

定理理解

这些定理和推论揭示了一些新的，重要的，之前可能有模糊感觉但不确定的性质。
推论3说明了，一旦循环群一个生成元被找到，那么所有生成元都能轻易确定。即如果找到一个生成元$a$，那么让$a$取和群阶互质的的数作为$a$的幂，得到的元素也是生成元。
例如：$|U(50)|=20$，由$3$生成，那么$3^3\mathrm{mod}50,3^7\mathrm{mod}50,\cdots ,3^{19}\mathrm{mod}5$都是此群的生成元。

循环群的子群

Theorem 4.3 循环群基本定理

循环群的子群都是循环群；
并且，如果$|⟨a⟩|=n$，$⟨a⟩$的子群的阶必定是$n$的约数；
再者，对于$n$的正约数$k$，$⟨a⟩$必定有一个确定的$k$阶子群$⟨a^{n/k}⟩$

定理理解

这个定理第一部分是符合直观的，重要的后两部分，这后两部分合起来说的意思是告诉我们循环群所有子群是什么样的。

定理证明

首先证明循环群的子群都是循环群，如果循环群仅包含单位元，那么按定义也是循环群，如果包含生成元$a$，那么这个子群就是它本身，当然也是循环群；考虑完这两个平凡子群后，现考虑$G=⟨a⟩$，$G$的子群$H$中必然都是形式$a^t$的元素，那么断言其中最小的幂$a^m$将生成$H$。假设子群中存在另一个元素$a^t=a^{mq+r}=a^{mq}{a}^r$，显然$a^{mq}$可由$a^m$生成，那么再结合条件$a^t$可由$a^m$生成，可推知$a^r$可由$a^m$生成，那么$r=0$，QED
假设群$G$的阶是$n$，现在我们知道循环群子群也有一个元素生成，这个元素可以写成$a^t$，那么根据Theorem 4.2 $⟨a^t⟩=⟨a^{\gcd (n,t)}⟩$，阶$|a^t|=n/\gcd (n,t)$，后者说明子群的阶必然是$n$的约数，也暗示子群的形式。

推论：$Z_n$的子群

对于$n$的正约数$k$，$⟨n/k⟩$是$Z_n$独一无二的$k$阶子群；更进一步，这些子群也是$Z_n$仅有的子群。

这个推论仅仅是基本定律的特例，另外要注意的是，这里说的是子群只有这么多，但同一个子群可能有不同形式。

Theorem 4.4 循环群各阶元素的个数

如果$d$是$n$的约数，$n$阶循环群的$d$阶元素的个数为$\varphi (d)$，我们有$\varphi (d)=|U(d)|$，其中$\varphi (n)$是欧拉$\varphi$函数。

这个定理可以结合前面的定理和推论得出，循环群基本定理说明，群元素的子群都是循环群，其中一个生成元$a$的阶是$n$的约数$d$，且这个$d$阶子群是唯一的，那么$d$阶元素说的是这个$d$阶子群的生成元个数，这样，所有的$a^{j}s.t.\gcd (n,j)=1$都是这个子群的生成元，根据这个定义，可知正好生成元个数满足$U(n)$的定义。

推论：有限群的同阶元素个数

（注意，这个推论扩展到了所有有限群）有限群中，阶$d$元素个数是$\varphi (d)$的倍数。

显然，如果有限群没有阶$d$元素，这个推论是成立的，因为倍数就是$0$。
如果有限群中有$d$阶元素$a$，那么循环群$⟨a⟩$中肯定有$\varphi (d)$个$d$阶元素。如果所有$d$阶元素都在$⟨a⟩$内，那么显然$d$阶元素个数就是$\varphi (d)$，如果有其他$d$阶元素$b$，那么$⟨b⟩$同样有$\varphi (d)$个$d$阶元素，$d$阶元素个数就是$2\varphi (d)$（因为两个不同子群不会有$d$阶的交集，只要意识到子群的交集也是子群，这个子群肯定小于$d$阶）。

欧拉$\varphi$函数的计算

根据定义，似乎并不好计算欧拉$\varphi$函数的具体值，然而存在一个有趣的特性可以帮助计算：$\varphi (p^n)=p^n-p^{n-1}$，且对于互质的数$m,n$，有$\varphi (mn)=\varphi (m)\varphi (n)$，把握这两个性质可以很快计算出结果。例如
$\varphi (40)=\varphi (8)\varphi (5)=(2^3-2^2)\times 4=16$