原根

Template:NoteTA 原根（Template:Lang-en）是一个在数论中的重要概念，特别是整除理论。

對於两个正整数$gcd(a,m)=1$，由欧拉定理可知，存在正整数$d\le m-1$， 比如说欧拉函数$d=\phi (m)$，即小于等于$m$的正整数中与$m$互質的正整数的个数，使得$a^d\equiv 1(\mathrm{mod}m)$。

由此，在$gcd(a,m)=1$時，定義$a$对模$m$的指数${\delta }_m(a)$為使$a^d\equiv 1(\mathrm{mod}m)$成立的最小的正整数$d$。由前知${\delta }_m(a)$ 一定小于等于 $\phi (m)$，若${\delta }_m(a)=\phi (m)$，則稱$a$是模$m$的原根。

例子

考慮 $m=7$，则 $\phi (m)=\phi (7)=6$。

设 $a=2$ ，由于

$$\begin{array}{ccccccccc}{2}^1& =& 2^0\times 2& \equiv & 1\times 2& =& 2& \equiv & 2(\mathrm{mod}7)\\ 2^2& =& 2^1\times 2& \equiv & 2\times 2& =& 4& \equiv & 4(\mathrm{mod}7)\\ 2^3& =& 2^2\times 2& \equiv & 4\times 2& =& 8& \equiv & 1(\mathrm{mod}7)\end{array}$$

因此有$Or{d}_7(2)=3\ne \phi (7)=6$，所以 2 不是模 7 的一个原根。

设 $a=3$ ，由于

$$\begin{array}{ccccccccc}{3}^1& =& 3^0\times 3& \equiv & 1\times 3& =& 3& \equiv & 3(\mathrm{mod}7)\\ 3^2& =& 3^1\times 3& \equiv & 3\times 3& =& 9& \equiv & 2(\mathrm{mod}7)\\ 3^3& =& 3^2\times 3& \equiv & 2\times 3& =& 6& \equiv & 6(\mathrm{mod}7)\\ 3^4& =& 3^3\times 3& \equiv & 6\times 3& =& 18& \equiv & 4(\mathrm{mod}7)\\ 3^5& =& 3^4\times 3& \equiv & 4\times 3& =& 12& \equiv & 5(\mathrm{mod}7)\\ 3^6& =& 3^5\times 3& \equiv & 5\times 3& =& 15& \equiv & 1(\mathrm{mod}7)\end{array}$$

因此有 $Or{d}_7(3)=6=\phi (7)$ ，所以 3 是模 7 的一个原根。

性质

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

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

• 模$m$有原根的充要條件是$m=1,2,4,p^n,2p^n$，其中$p$是奇質數，$n$是任意正整數。

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

一些數的原根列表

m	模m的原根(有*號的數沒有原根，此時是有最大模m週期的數)	週期 (Template:Oeis)
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，使得 $g_p\le C{p}^{\frac{1}{4}+ϵ}$。

Emil Grosswald (1981) 證明如果 $p>e^{e^{24}}$，則 $g_p<p^{0.499}$。

參見

• 費馬小定理

• 同餘

• 離散對數