循环群与生成元

Cyclic Groups and Generators.

Before stepping into the definition of cyclic groups, we introduce the definition of order of a group element.

Definition. The order of a group element $g\in \mathbb{G}$ is the smallest positive integer $r$ such that $g^r=1$ , and is denoted by $ord(g)$ .

Note the distinction between the two concepts the order of a group and the order of a group element.

Definition. If an element $g\in \mathbb{G}$ has order $|\mathbb{G}|$ , then $\mathbb{G}$ is a cyclic group and can be denoted by $\mathbb{G}=\langle g \rangle$ . We call $g$ the generator of $\mathbb{G}$ .

Therefore, if $\mathbb{G}$ is a cyclic group and $|\mathbb{G}|=m$ , there must exists a generator $g\in\mathbb{G}$ that could generate the whole group by constantly multiplying itself, i.e., $\{g, g^2, ..., g^m\}=\mathbb{G}$ .

Eureka moment!

之前搞 OI 的时候在数论里学习到了原根 (primitive root) 的概念，然而并不是很明白。到大学学到生成元 (generator) 的概念突然有了醍醐灌顶之感。实际上，原根和生成元的概念是一体两面。

若一个正整数 $m$ 有原根 $g$ ，那么就意味着群 $(\mathbb{Z}/m)^{*}$ 是一个循环群，且它的生成元为 $g$ 。

正整数 $m$ 有原根 (群 $(\mathbb{Z}/m)^{*}$ 为循环群) 的充要条件为：它能表达为下列形式之一 $2,4,p^n,2p^n$ ，其中 $p$ 为奇素数。且若 $m$ 有原根，其原根的个数为 $\varphi(\varphi(m))$ 。部分证明 ( $m$ 为质数) 见我的 CnBlogs: 循环群；这里还提到，任意质数阶群 (group of prime order) 一定是循环群。