原根

原根（英語：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)=\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 的一個原根^[1]。

性質

可以證明，如果正整數 $(a,m)=1$ 和正整數 d 滿足 $a^{d}\equiv 1{\pmod {m}}$ ，則 $Ord_{m}(a)$ 整除 d。^[2]因此 $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 互質的正整數構成的等價類構成的乘法群）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