查看“︁原根”︁的源代码

{{NoteTA
| G1 = Math
}}
'''原根'''（{{lang-en|Primitive root}}）是一个在[[数论]]中的重要概念，特别是[[整除]]理论。

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

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

==例子==

考慮 <math>m=7</math>，则 <math> \varphi (m) =\varphi(7) = 6</math>。

设 <math>a=2</math> ，由于

<math display="block">
\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}
</math>

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

设 <math>a=3</math> ，由于

<math display="block">
\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}
</math>

因此有 <math>Ord_7(3) = 6 =\varphi (7)</math> ，所以 3 是模 7 的一个原根<ref>{{cite web |last=Stromquist |first=Walter |title=What are primitive roots? |publisher=Bryn Mawr College |department=Mathematics |url=http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |access-date=2017-07-03 |url-status=dead |archive-url=https://web.archive.org/web/20170703173446/http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |archive-date=2017-07-03}}</ref>。

==性质==

*可以证明，如果正整数<math>(a,m)=1</math>和正整数 d 满足<math>a^d \equiv 1 \pmod{m} </math>，则 <math>Ord_m (a)</math> 整除 d。<ref>参考 http://www.infosec.sdu.edu.cn/jpkc/resource/4yuangen.pdf {{Wayback|url=http://www.infosec.sdu.edu.cn/jpkc/resource/4yuangen.pdf |date=20141006135539 }}</ref>因此<math>Ord_m (a)</math>整除<math> \varphi (m) </math>。在例子中，当<math>a=3</math>时，我们仅需要验证 3 的 2、3 次方模 7 的[[余数]]即可，如果其中有一个是1，则3就不是原根。

*记<math>\delta = Ord_m (a)</math>，则<math>a^0,a^1,a^2 \cdots , a^{\delta -1} </math>模 m 两两不[[同余]]。因此当<math>a</math>是模<math>m</math>的原根时，<math>a^0,a^1,a^2 \cdots , a^{\delta -1} </math>构成模 m 的[[简化剩余系]]。

*模<math>m</math>有原根的充要條件是<math>m = 1 , 2 , 4 , p^n , 2p^n</math>，其中<math>p</math>是奇質數，<math>n</math>是任意[[正整數]]。

*对正整数<math>(a,m)=1</math>，如果 a 是模 m 的原根，那么 a 是'''[[整数模n乘法群|整数模m乘法群]]'''（即加法群 '''Z'''/m'''Z''' 的可逆元，也就是所有与 m [[互素]]的正整数构成的[[等价类]]构成的乘法群）'''Z'''<sub>m</sub><sup>&times;</sup>的一个[[循环群|生成元]]。由于'''Z'''<sub>m</sub><sup>&times;</sup>有 <math> \varphi (m)</math>个元素，而它的生成元的个数就是它的可逆元个数，即 <math> \varphi (\varphi (m))</math>个，因此当模<math>m</math>有原根時，它有<math>\varphi (\varphi (m))</math>個原根。

== 一些數的原根列表 ==
{|class="wikitable"
|m
|模m的原根(有*號的數沒有原根，此時是有最大模m週期的數)
|週期 ({{oeis|id=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 <sub>p</sub> 定義為在 1 到 p-1 中最小的原根。數學家已經給出最小原根的上界及下界的一些限制。

伯吉斯(1962)證明對任何 ε>0，存在一個 C>0，使得
<math> g_p \leq Cp^{\frac{1}{4}+\epsilon} </math>。

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

==参考资料及注释==
{{Reflist}}

== 參見 ==

*[[費馬小定理]]

*[[同餘]]

*[[离散对数|離散對數]]

{{ModernAlgebra}}

[[Category:同余]]