原根

原根是数论中重要的概念，它可以将乘法群（有限域）$\Z_m^*$的结构做极大简化，应用广泛。

阶的概念

设$(a, m) = 1$，满足$a^r \equiv 1 \pmod{m}$的最小正整数$r$称为整数$a$模$m$的阶。

定理：$(a, m) = 1$，$r$为$a$模$m$的阶。则$a^k \equiv 1 \pmod{m}$当且仅当$r \mid k$，特别地，$r \mid \varphi (m).$

证明：

1. 对于 $(a, m) = 1$，$a^{0},a^{1}\cdots a^{\varphi (m)}{\pmod {m}}$这 $\varphi (m)+1$ 个数中，对应 $\varphi(m)$ 种余数，因为由 $(a, m) = 1$ 可知这个余数与 $m$ 互质。由鸽巢原理可知，一定存在至少一对数 $0\leq i<j\leq \varphi (m),a^{i}\equiv a^{j}{\pmod {m}}$，将两边同时除以 $a^i$ 可知 $a^{j-i}\equiv 1{\pmod {m}}$，此时 $r$ 为最小的 $j-i$ 就是整数$a$模$m$的阶，$1\leq r\leq \varphi (m)$，并且其他 $j-i$ 一定是 $r$ 的倍数。否则将 $j-i,r$ 的最大公约数显然能得到一个更小的 $r$。
2. 对于 $m>0$，令 $(a, m) = 1$，$i \geq 0$，由 $r$ 的最小性可知，$a^{i},a^{i+1},a^{i+2}\cdots ,a^{i+r-1}{\pmod {m}}$ 互不相同，不妨把 $a^{i},a^{i+1},a^{i+2}\cdots ,a^{i+r-1}{\pmod {m}}$ 里的数看成一个组别。对于一个组别中的数 $b$，$ab{\pmod {m}}$ 一定也在这个组别中。对于 $\varphi(m)$ 种余数，每一种余数都只存在于一种组别当中。所以不难得出 $r\mid \varphi (m)$。特别的，如果 $m$ 是质数且 $a\ne 1$，则 $r=\varphi (m)$。

以下给出阶的判定条件：$(a, m) = 1$，$r$为$a$模$m$的阶当且仅当

1. $a^r \equiv 1 \pmod{m}$；
2. 对于$r$的每个素因子$p$，$a^{\frac{r}{p}} \not\equiv 1 \pmod{m}.$

下面这个结论给出了我们通过已知阶来求未知阶的一个方法：$(a, m) = 1$，$r$为$a$模$m$的阶，则对每个整数$l$，$a^l$模$r$的阶为$\dfrac{r}{(r, l)}.$当$(r, l) = 1$时，$a^l$与$a$有相同的阶。

原根

若整数$a$模$m$的阶为$\varphi(m)$，那么就称$a$是$m$的一个原根，一般用$g$表示。

检验某个数$a$是否为模$m$原根，一般从$2$开始的每个与$m$互素的数逐个试起，按照阶的判定方法，只需验证对于$\varphi(m)$的每个素因子 $p$，$a^{\frac{\varphi (m)}{p}} \not\equiv 1 \pmod{m}.$

原根存在的充要条件

定理：$m$存在原根，当且仅当$m = 2, 4, p^\alpha, 2 p^\alpha$，其中$p$为奇素数。

且若$g$是$p$的一个原根，则$p$和$g+p$中必有一个是$p^\alpha$的原根；$g$和$g+p^\alpha$中的奇数是$2p^\alpha$的一个原根。

如果若$g$是$m$的一个原根，则对$\varphi(m)$的每个正因子$d$，模$m$的$d$阶元素共有$\varphi (d)$个，它们是 $$g^{ld'}, 1 \leqslant l \leqslant d, (l, d) = 1, d' = \dfrac{\varphi (m)}{d}.$$

据此我们只要找到一个模$m$的原根$g$，可以决定出所有模$m$的原根。

乘法群

$m$在有原根$g$时，由于$\Z_m^*$共有$\varphi(m)$元素，而$g$不断自乘得到的元素在同余意义下都是不同的，直到自乘到$\varphi(m)$次才会乘到自己，期间所有的元素收集在一起，就是$\Z_m^*$的所有元素了，即$\Z_m^* = \{g^0, g^1, g^2, g^3, \cdots, g^{\varphi (m)-1} \}$，这就是一个乘法循环群。

上下节

• 上一节：Euler-Fermat 定理
• 下一节：指数