原根

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

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

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

例子

设m = 7，则φ(m)等于6。

• 设a = 2，由于$2^3 = 8 \equiv 1 \pmod{7}$，而$\displaystyle 3 < 6$，所以 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₇(3) = 6 = φ(7)，所以 3 是模 7 的一个原根。

性质

• 可以证明，如果正整数(a,m) = 1和正整数 d 满足$a^d \equiv 1 \pmod{m}$，则 d 整除 ϕ(m)。因此Ord_m(a)整除φ(m)。在例子中，当a = 3时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。

• 记δ = 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ⁿ,2pⁿ，其中p是奇質數，n是任意正整數。

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

一些數的原根列表

m	2	3	4	5	6	7
模m的原根	1	2		2、3		3、5、6

除了直接運算以外，至今還沒有一個辦法可以找到模特定m時的原根，但假如已知模m有一個原根，則可找出它其他的原根

參見

• 費馬小定理

• 同餘

• 離散對數