原根

原根是模 $p$ 乘法群的生成元，它使非零剩余类呈现循环结构，是解高次同余方程与构造有限域的工具。

定义

设 $g$ 与 $m$ 互素，$g$ 模 $m$ 的阶是使 $g^k\equiv1\pmod m$ 的最小正整数 $k$。若阶等于 $\varphi(m)$，则称 $g$ 为模 $m$ 的原根。

存在性

模 $m$ 存在原根当且仅当 $m=2,\ 4,\ p^k,\ 2p^k$（$p$ 为奇素数）；此时 $(\mathbb{Z}/m\mathbb{Z})^\times$ 是循环群，原根共有 $\varphi(\varphi(m))$ 个。特别地，模奇素数 $p$ 必有原根。

离散对数

固定原根 $g$，对 $p\nmid a$ 存在唯一的 $1\le k\le p-1$ 使 $g^k\equiv a\pmod p$，记 $k=\mathrm{ind}_g a$。离散对数把乘法化为指数加法：

$$\mathrm{ind}_g(ab)\equiv\mathrm{ind}_g a+\mathrm{ind}_g b\pmod{p-1}$$

示例

• 模 $7$：$3^1\equiv3$，$3^2\equiv2$，$3^3\equiv6$，$3^4\equiv4$，$3^5\equiv5$，$3^6\equiv1$，故 $3$ 是原根；$2^3\equiv1$，$2$ 的阶为 $3$，不是原根
• 原根个数为 $\varphi(6)=2$：$3$ 与 $5$（$5\equiv3^5\pmod7$）