原はら根ね

在ざい数かず论，特とく别是整除せいじょ理り论中，原はら根ね（英語えいご：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)=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_{7}(3)=6=\varphi (7)$ ，所以ゆえん 3 是ぜ模も 7 的てき一いち个原根ね。

性せい质

可か以证明あきら，如果正せい整数せいすう $(a,m)=1$ 和かず正ただし整数せいすう d 满足 $a^{d}\equiv 1{\pmod {m}}$ ，则 $Ord_{m}(a)$ 整除せいじょ d。^[1]因いん此 $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