原根
在数论,特别是整除理论中,原根(英语:Primitive root)是一个很重要的概念。
对于两个正整数,由欧拉定理可知,存在正整数, 比如说欧拉函数,即小于等于的正整数中与互质的正整数的个数,使得。
由此,在时,定义对模的指数为使成立的最小的正整数。由前知 一定小于等于 ,若,则称是模的原根。
例子
编辑设 ,则 等于6。
- 设 ,由于 , , , , , ,因此有 ,所以 2 不是模 7 的一个原根。
- 设 ,由于 , , , , , ,因此有 ,所以 3 是模 7 的一个原根。
性质
编辑- 模 有原根的充要条件是 ,其中 是奇质数, 是任意正整数。
一些数的原根列表
编辑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 |
除了直接运算以外,至今还没有一个办法可以找到模特定m时的原根,但假如已知模m有一个原根,则可找出它其他的原根。
最小原根
编辑模 p 的最小原根 g p 定义为在 1 到 p-1 中最小的原根。数学家已经给出最小原根的上界及下界的一些限制。
伯吉斯(1962)证明对任何 ε>0,存在一个 C>0,使得 。
Emil Grosswald (1981) 证明如果 ,则 。