原根

在數論，特別是整除理論中，原根（英語：Primitive root）是一個很重要的概念。

對於兩個正整數$gcd(a,m)=1$，由歐拉定理可知，存在正整數$d\leq m-1$， 比如說歐拉函數$d=\varphi (m)$，即小於等於$m$的正整數中與$m$互質的正整數的個數，使得$a^{d}\equiv 1{\pmod {m}}$。

由此，在$gcd(a,m)=1$時，定義$a$對模$m$的指數$\delta _{m}(a)$為使$a^{d}\equiv 1{\pmod {m}}$成立的最小的正整數$d$。由前知$\delta _{m}(a)$ 一定小於等於 $\varphi (m)$，若$\delta _{m}(a)=\varphi (m)$，則稱$a$是模$m$的原根。

例子

設$m=7$，則$\varphi (m)$等於6。

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

性質

• 可以證明，如果正整數$(a,m)=1$和正整數 d 滿足$a^{d}\equiv 1{\pmod {m}}$，則 $Ord_{m}(a)$ 整除 d。因此$Ord_{m}(a)$整除$\varphi (m)$。在例子中，當$a=3$時，我們僅需要驗證 3 的 2、3 次方模 7 的餘數即可，如果其中有一個是1，則3就不是原根。

• 記$\delta =Ord_{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=2,4,p^{n},2p^{n}$，其中$p$是奇質數，$n$是任意正整數。

• 對正整數$(a,m)=1$，如果 a 是模 m 的原根，那麼 a 是整數模m乘法群（即加法群 Z/mZ 的可逆元素，也就是所有與 m 互質的正整數構成的等價類構成的乘法群）Z_m^×的一個生成元。由於Z_m^×有 $\varphi (m)$個元素，而它的生成元的個數就是它的可逆元素個數，即 $\varphi (\varphi (m))$個，因此當模$m$有原根時，它有$\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，使得 $g_{p}\leq Cp^{{\frac {1}{4}}+\epsilon }$。

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

參見

• 費馬小定理

• 同餘

• 離散對數