定义

一个群是循环的如果可以由单个元素生成得到

例子

对于一个运算符是 ×\times 的群，我们有 x∈Gx\in G 的子群为 H:={⋯ ,x−3,x−2,x−1,1=x0,x,x2,x3}H:= \{\cdots,x^{-3},x^{-2},x^{-1},1=x^0,x,x^2,x^3\}
这个群就是包含 xx 的最小子群，写作 ⟨x⟩\langle x\rangle
如果存在 m∈N−{0}m\in \mathbb N - \{0\} 使得 xm=1x^m = 1 我们称 mm 是 order of x, 写作 m=∣x∣m = |x|
这个 m 将一个发散的群结构变成了循环的群结构，并且说明了群的尺寸
对于群 GG 的 order，我们有 ∣G∣|G| 为其中元素的数量

注

这里的 xnx^n 可能表示不同的元素，或者相同，如 (−1)m(-1)^m

定理

令 ⟨x⟩\langle x\rangle 是一个循环子群，元素由 xx 生成，令 S:={k∈Z∣xk=1}S:=\{k\in \mathbb Z | x^k = 1\} 那么

  1. 集合 SS 是加法群 (Z,+)(\mathbb Z, +) 的子群
    1. 令 k,l∈Sk,l\in S 那么 xk=xl=1x^k = x^l = 1 因此我们有 xk+l=xkxl=1x^{k+l} = x^k x^l = 1 因此 k+l∈Sk+l\in S
    2. x0=1x ^0 = 1 所以 0∈S0\in S
    3. 如果 k∈Sk\in S 那么 x−k=(xk)−1=1x^{-k} = (x^k)^{-1} = 1 因此 k∈Sk\in S
  2. 对于 r,s∈Zr,s\in \mathbb Z, xr=xsx^r = x^s 当且仅当 xr−s=1x^{r-s} = 1 即 r−s∈Sr-s\in S
  3. 假设 S≠{0}S\not =\{0\} 那么 S=nZS = n\mathbb Z 对某些 n∈N\{0}n\in\mathbb N\backslash \{0\} , 且 1,x,⋯ ,xn1,x,\cdots,x^n 是不同元素，且 ∣⟨x⟩∣=n|\langle x\rangle| = n
    1. 由于 SS 是 (Z,+)(\mathbb Z, +) 的一个子群，那么 S=nZS = n\mathbb Z 对某些最小的正整数 n∈Sn\in S 存在对于任意 k∈Zk\in \mathbb Z, k=qn+rk=qn + r 对某些 q 与 r 成立，因此 xk=xqn+r=xnqxr=xrx^k = x^{qn+r} = x^{nq}x^r = x^r

注

  • 如果 ∣x∣=∞|x| = \infty 那么 xr=xsx^r = x^s 当且仅当 r=sr = s , 因为这个群没有循环起来
  • 如果 ∣x∣<∞|x|< \infty 或者说 ∣x∣=n∈N|x| = n\in \mathbb N 那么 xr=xsx^r = x^s 当且仅当 n∣r−sn | r - s
    • 对于循环群而言 0 是第一个元素，而 xx 是第二个元素
  • ∣x∣|x| = ∣⟨x⟩∣|\langle x\rangle|
    • 这里的理解我们可以想象将一个循环群等效为一个圆环，那么每个节点就是一个 xx 且节点的数量就是 ∣x∣|x|，而且有 ⟨x⟩\langle x\rangle 为连接两个点之间的线，所以说 ∣x∣=∣⟨x⟩∣|x| = |\langle x\rangle| 这个就是小学生最喜欢的环湖植树问题
  • 如果 ∣x∣=n|x| = n 且 xk=1x^k = 1 那么 n ∣ kn\ |\ k

例子

对于集合 Z/8Z\mathbb Z / 8\mathbb Z 我们有 ⟨[1]⟩=⟨[3]⟩=⟨[5]⟩=⟨[7]⟩\langle [1]\rangle = \langle [3] \rangle = \langle [5]\rangle = \langle [7]\rangle
这里我们首先要看看余数空间的结构
首先我们明确 [1]={8k+1∣k∈Z}[1] = \{8k + 1|k\in \mathbb Z\} , [3]={8k+3∣k∈Z}[3] = \{8k + 3|k\in \mathbb Z\}
然后投射到循环群空间，我们有 ⟨[1]⟩=1kmod 8={1}\langle[1]\rangle = 1^k \text{mod}\ 8 = \{1\}, 同理，我们有 ⟨[3]⟩=3kmod 8={1,3}\langle[3]\rangle = 3^k \text{mod}\ 8 = \{1,3\}

问：为什么对于 [3][3] 不考虑 1111 的幂？

在 Z/8Z\mathbb Z/8\mathbb Z 空间中，我们有 3∼113 \sim 11 或者说这些元素在空间中对于定义运算符性质等价，其实不需要再考虑这些问题

最大公约数定理

令 n,k∈N\{0}n,k\in\mathbb N\backslash\{0\} 对于群 GG 和 x∈Gx\in G 有 ∣x∣=n\{0}|x| = n\backslash\{0\}
那么 ⟨xk⟩=⟨xgcd(n,k)⟩\langle x^k\rangle = \langle x^{\text{gcd(n,k)}}\rangle 且有 ∣xk∣=ngcd(n,k)|x^k| = \frac{n}{\text{gcd(n,k)}}

理解

这里的 ∣xk∣|x^k| 相当于是将生成元 xx 在循环的圈中向后顺延了 k 个节点，也就是说，圈子整体不变，第一个点不动，只是第二个点向后顺延，那么步长也变长了，所以循环群的尺寸就缩小了 gcd(n,k)gcd(n,k) 倍 (当然也可能不缩小)

证明

因为有 ∣x∣=n|x| = n 我们有

⟨xk⟩={(xk)t∣t∈Z}={xkt+ns∣t,s∈Z}={xd∣d∈gcd(n,k)Z}=⟨xgcd(n,k)⟩\langle x^k \rangle= \{(x^k)^t|t\in \mathbb Z\} = \{x^{kt + ns}| t,s\in \mathbb Z\} = \{x^d | d\in gcd(n,k)\mathbb Z\} = \langle x^{\text{gcd(n,k)}}\rangle

对于 ∣xk∣|x^k| 我们其实就是找 (xk)r=1(x^k)^r = 1 的最小 r 值
那么对于 t=∣xk∣t = |x^k|, 我们有 t=∣xk∣=∣⟨xk⟩∣=∣⟨xgcd(n,k)⟩∣=∣xgcd(n,k)∣t = |x^k| = |\langle x^k\rangle| = | \langle x^{\text{gcd(n,k)}}\rangle| = |x^\text{gcd(n,k)}| 因此

  • (xk)t=1⇔xkt=1⇒n∣kt⇔ngcd(n,k) ∣ t(x^k)^t = 1 \Leftrightarrow x^{kt} = 1 \Rightarrow n | kt \Leftrightarrow \frac{n}{\text{gcd(n,k)}}\ |\ t
  • (xgcd(n,k))n/gcd(n,k)=xn=1⇒t ∣ ngcd(n,k)(x^{\text{gcd(n,k)}})^{\text{n/gcd(n,k)}} = x^n = 1 \Rightarrow t\ |\ \frac{n}{\text{gcd(n,k)}}

注

  1. 令 ∣⟨x⟩∣<∞|\langle x\rangle | < \infty 那么 y∈⟨x⟩⇒∣y∣ divides ∣⟨x⟩∣y\in \langle x\rangle \Rightarrow|y|\ divides\ |\langle x\rangle|
    1. 这其实就是把 y=xky = x^k 带入等式
  2. 令 ∣x∣=n∈N\{0}|x| = n \in \mathbb N \backslash \{0\} 那么我们有 ⟨xi⟩=⟨xj⟩⇔∣xi∣=∣xj∣⇔gcd(n,i)=gcd(n,j)\langle x^i\rangle = \langle x^j \rangle \Leftrightarrow |x^i| = |x^j| \Leftrightarrow \text{gcd(n,i)} = \text{gcd(n,j)}

循环群子群基本定理

  1. 每一个循环群的子群是循环的（注意子群的运算符和原群一致）
  2. 如果 ∣⟨x⟩∣=n|\langle x\rangle| = n 那么 ⟨x⟩\langle x\rangle 的任意子群的 order 整除 nn
  3. 对每个 k ∣ nk\ |\ n 对于 k>0k >0 群 ⟨x⟩\langle x\rangle 有且只有一个 order 为 k 的子群，且为 ⟨xn/k⟩\langle x^{n/k}\rangle
    1. 这个子群的节点数量是原来的 1/k1/k 但是步长是 n/kn/k

欧拉商函数 Euler’s Totient Function

也叫欧拉 phi 函数，写作 ϕ(n)\phi(n) 或者 φ(n)\varphi(n) 记录小于n且与n互质的数的个数

φ(n)=∣{k∈N∣1≤k<n,gcd(n,k)=1}∣\varphi(n) = |\{k\in \mathbb N | 1\le k < n, gcd(n,k) = 1\}|

特例

  1. 对于质数p: φ(p)=p−1\varphi(p) = p-1
  2. 对于质数幂pkp^k: φ(pk)=pk−pk−1\varphi(p^k) = p^k - p^{k-1}
    1. 这个的因数是 1⋅p1\cdot p 一直到 pk−1⋅pp^{k-1}\cdot p

循环群引理

对于一个循环群 CC 序为 ∣C∣=n|C| = n 如果有 d>0∧d ∣ nd > 0\land d\ |\ n 那么 C 子群中序为 d 的元素数量是 φ(d)\varphi(d)

注

注意 上述公式 φ(d)\varphi(d) 是一个和 nn 数值无关的函数

因子和 - 高斯

对正整数 n 我们有:

n=∑d∣nφ(d)n = \sum_{d|n} \varphi(d)

乘子函数 multiplicative

对于一个函数 f:N\{0}→N\{0}f:\mathbb N\backslash\{0\}\to \mathbb N\backslash\{0\} , f(1)=1f(1) = 1 且 f(m1m2)=f(m1)f(m2)f(m_1m_2) = f(m_1)f(m_2) 对 gcd(m1,m2)=1\text{gcd}(m_1,m_2) = 1.

乘子定理

  1. 欧拉商函数是一个乘子函数
  2. 满足条件 g(m)=∑d∣mf(d)g(m) = \sum_{d|m} f(d) 那么 g 也是一个乘子函数, 且逆定理也为真

对称群 Symmetric Groups

对于 正整数 n 我们有 n 阶对称群

Sn={All permutation on n letters/numbers}S_n =\{\text{All\ permutation\ on\ n\ letters/numbers}\}

我们也可以写作

Sn={f:[n]→[n]∣f is a bijection}S_n = \{f:[n]\to [n]|\text{f is a bijection}\}

注意这里是关于映射 ff 的集合
且 SnS_n 的序为 ∣Sn∣=n!|S_n| = n!

注

对称群不是循环群，因为其元素不是由一个元素生成的

推论

当 n≥3n\ge 3 的时候，对称群一定不是 阿贝尔群

换为 transposition

对于形式为 (ab)(ab) 的排列，且有 a≠ba\not = b 我们称之为 transposition

  • 每一个 SnS_n 下的排列都是 transposition 的积
  • 如果 e=β1β2⋯βre = \beta_1\beta_2\cdots\beta_r 那么 rr 一定是偶数