在数论，特别是整除理论中，原根（英语：Primitive root）是一个很重要的概念。

对于两个正整数${\displaystyle gcd(a,m)=1}$，由欧拉定理可知，存在正整数${\displaystyle d\leq m-1}$， 比如说欧拉函数${\displaystyle d=\varphi (m)}$，即小于等于${\displaystyle m}$的正整数中与${\displaystyle m}$互素的正整数的个数，使得${\displaystyle a^{d}\equiv 1{\pmod {m))}$。

由此，在${\displaystyle gcd(a,m)=1}$时，定义${\displaystyle a}$对模${\displaystyle m}$的指数${\displaystyle \delta _{m}(a)}$为使${\displaystyle a^{d}\equiv 1{\pmod {m))}$成立的最小的正整数${\displaystyle d}$。由前知${\displaystyle \delta _{m}(a)}$ 一定小于等于 ${\displaystyle \varphi (m)}$，若${\displaystyle \delta _{m}(a)=\varphi (m)}$，则称${\displaystyle a}$是模${\displaystyle m}$的原根。

例子

设${\displaystyle m=7}$，则${\displaystyle \varphi (m)}$等于6。

• 设${\displaystyle a=2}$，由于${\displaystyle 2^{1}\equiv 2{\pmod {7))}$，${\displaystyle 2^{2}\equiv 4{\pmod {7))}$，${\displaystyle 2^{3}\equiv 1{\pmod {7))}$，${\displaystyle 2^{4}\equiv 2{\pmod {7))}$，${\displaystyle 2^{5}\equiv 4{\pmod {7))}$，${\displaystyle 2^{6}\equiv 1{\pmod {7))}$，因此有${\displaystyle Ord_{7}(2)=3\neq \varphi (7)=6}$，所以 2 不是模 7 的一个原根。
• 设${\displaystyle a=3}$，由于${\displaystyle 3^{1}\equiv 3{\pmod {7))}$，${\displaystyle 3^{2}\equiv 2{\pmod {7))}$，${\displaystyle 3^{3}\equiv 6{\pmod {7))}$，${\displaystyle 3^{4}\equiv 4{\pmod {7))}$，${\displaystyle 3^{5}\equiv 5{\pmod {7))}$，${\displaystyle 3^{6}\equiv 1{\pmod {7))}$，因此有${\displaystyle Ord_{7}(3)=6=\varphi (7)}$，所以 3 是模 7 的一个原根。

性质

• 可以证明，如果正整数${\displaystyle (a,m)=1}$和正整数 d 满足${\displaystyle a^{d}\equiv 1{\pmod {m))}$，则 ${\displaystyle Ord_{m}(a)}$ 整除 d。^[1]因此${\displaystyle Ord_{m}(a)}$整除${\displaystyle \varphi (m)}$。在例子中，当${\displaystyle a=3}$时，我们仅需要验证 3 的 2、3 次方模 7 的余数即可，如果其中有一个是1，则3就不是原根。

• 记${\displaystyle \delta =Ord_{m}(a)}$，则${\displaystyle a^{0},a^{1},a^{2}\cdots ,a^{\delta -1))$模 m 两两不同余。因此当${\displaystyle a}$是模${\displaystyle m}$的原根时，${\displaystyle a^{0},a^{1},a^{2}\cdots ,a^{\delta -1))$构成模 m 的简化剩余系。

• 模${\displaystyle m}$有原根的充要条件是${\displaystyle m=1,2,4,p^{n},2p^{n))$，其中${\displaystyle p}$是奇素数，${\displaystyle n}$是任意正整数。

• 对正整数${\displaystyle (a,m)=1}$，如果 a 是模 m 的原根，那么 a 是整数模m乘法群（即加法群 Z/mZ 的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Z_m^×的一个生成元。由于Z_m^×有 ${\displaystyle \varphi (m)}$个元素，而它的生成元的个数就是它的可逆元个数，即 ${\displaystyle \varphi (\varphi (m))}$个，因此当模${\displaystyle m}$有原根时，它有${\displaystyle \varphi (\varphi (m))}$个原根。

一些数的原根列表

m	模m的原根(有*号的数没有原根，此时是有最大模m周期的数)	周期 ( A002322)
1	0	1
2	1	1
3	2	2
4	3	2
5	2, 3	4
6	5	2
7	3, 5	6
8*	3, 5, 7	2
9	2, 5	6
10	3, 7	4
11	2, 6, 7, 8	10
12*	5, 7, 11	2
13	2, 6, 7, 11	12
14	3, 5	6
15*	2, 7, 8, 13	4
16*	3, 5, 11, 13	4
17	3, 5, 6, 7, 10, 11, 12, 14	16
18	5, 11	6
19	2, 3, 10, 13, 14, 15	18
20*	3, 7, 13, 17	4
21*	2, 5, 10, 11, 17, 19	6
22	7, 13, 17, 19	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22
24*	5, 7, 11, 13, 17, 19, 23	2
25	2, 3, 8, 12, 13, 17, 22, 23	20
26	7, 11, 15, 19	12
27	2, 5, 11, 14, 20, 23	18
28*	3, 5, 11, 17, 19, 23	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28
30*	7, 13, 17, 23	4
31	3, 11, 12, 13, 17, 21, 22, 24	30
32*	3, 5, 11, 13, 19, 21, 27, 29	8
33*	2, 5, 7, 8, 13, 14, 17, 19, 20, 26, 28, 29	10
34	3, 5, 7, 11, 23, 27, 29, 31	16
35*	2, 3, 12, 17, 18, 23, 32, 33	12
36*	5, 7, 11, 23, 29, 31	6

除了直接运算以外，至今还没有一个办法可以找到模特定m时的原根，但假如已知模m有一个原根，则可找出它其他的原根。

最小原根

模 p 的最小原根 g _p 定义为在 1 到 p-1 中最小的原根。数学家已经给出最小原根的上界及下界的一些限制。

伯吉斯(1962)证明对任何 ε>0，存在一个 C>0，使得 ${\displaystyle g_{p}\leq Cp^((\frac {1}{4))+\epsilon ))$。

Emil Grosswald (1981) 证明如果 ${\displaystyle p>e^{e^{24))}$，则 ${\displaystyle g_{p}<p^{0.499))$。

参考资料及注释

参见

• 费马小定理

• 同余

• 离散对数