原根

原根（）是一个在数论中的重要概念，特别是整除理论。

對於两个正整数\gcd(a,m)=1，由欧拉定理可知，存在正整数d \le 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) =\varphi(7) = 6。

设 a=2 ，由于

\begin{array}{rcrcrc}
2^1 &=& 2^0 \times 2 &\equiv& 1 \times 2 &=& 2 &\equiv& 2 \pmod 7 \\
2^2 &=& 2^1 \times 2 &\equiv& 2 \times 2 &=& 4 &\equiv& 4 \pmod 7 \\
2^3 &=& 2^2 \times 2 &\equiv& 4 \times 2 &=& 8 &\equiv& 1 \pmod 7
\end{array}

因此有Ord_7(2) = 3 \neq \varphi (7) = 6 ，所以 2 不是模 7 的一个原根。

设 a=3 ，由于

\begin{array}{rcrcrcrcrcr}
3^1 &=& 3^0 \times 3 &\equiv& 1 \times 3 &=& 3 &\equiv& 3 \pmod 7 \\
3^2 &=& 3^1 \times 3 &\equiv& 3 \times 3 &=& 9 &\equiv& 2 \pmod 7 \\
3^3 &=& 3^2 \times 3 &\equiv& 2 \times 3 &=& 6 &\equiv& 6 \pmod 7 \\
3^4 &=& 3^3 \times 3 &\equiv& 6 \times 3 &=& 18 &\equiv& 4 \pmod 7 \\
3^5 &=& 3^4 \times 3 &\equiv& 4 \times 3 &=& 12 &\equiv& 5 \pmod 7 \\
3^6 &=& 3^5 \times 3 &\equiv& 5 \times 3 &=& 15 &\equiv& 1 \pmod 7
\end{array}

因此有 Ord_7(3) = 6 =\varphi (7) ，所以 3 是模 7 的一个原根。

性质
*可以证明，如果正整数\gcd(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 = 1 , 2 , 4 , p^n , 2p^n，其中p是奇質數，n是任意正整數。
*对正整数(a,m)=1，如果 a 是模 m 的原根，那么 a 是整数模m乘法群（即加法群 Z/mZ 的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zm×的一个生成元。由于Zm×有 \varphi (m)个元素，而它的生成元的个数就是它的可逆元个数，即 \varphi (\varphi (m))个，因此当模m有原根時，它有\varphi (\varphi (m))個原根。

一些數的原根列表
除了直接運算以外，至今還沒有一個辦法可以找到模特定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 。

参考资料及注释
參見
*費馬小定理
*同餘
*離散對數