原根
原根（英语：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 的一个原根[1]。
性质[编辑]
- 可以证明，如果正整数<math>\gcd(a,m)=1</math>和正整数 d 满足<math>a^d \equiv 1 \pmod{m} </math>，则 <math>Ord_m (a)</math> 整除 d。[2]因此<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 是整数模m乘法群（即加法群 Z/mZ 的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zm×的一个生成元。由于Zm×有 <math> \varphi (m)</math>个元素，而它的生成元的个数就是它的可逆元个数，即 <math> \varphi (\varphi (m))</math>个，因此当模<math>m</math>有原根时，它有<math>\varphi (\varphi (m))</math>个原根。
一些数的原根列表[编辑]
| m | 模m的原根(有*号的数没有原根，此时是有最大模m周期的数) | 周期 (OEIS 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 p 定义为在 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>。
参考资料及注释[编辑]
- ^ Stromquist, Walter. What are primitive roots?. Mathematics. Bryn Mawr College. [2017-07-03]. （原始内容存档于2017-07-03）.
- ^ 参考 http://www.infosec.sdu.edu.cn/jpkc/resource/4yuangen.pdf （页面存档备份，存于互联网档案馆）