例子
考虑 ,则 。
设 ,由于
因此有 ,所以 2 不是模 7 的一个原根。
设 ,由于
因此有 ,所以 3 是模 7 的一个原根[1]。
性质
- 可以证明,如果正整数 和正整数 d 满足 ,则 整除 d。[2]因此 整除 。在例子中,当 时,我们仅需要验证 3 的 2、3 次方模 7 的余数即可,如果其中有一个是1,则3就不是原根。
- 记 ,则 模 m 两两不同余。因此当 是模 的原根时, 构成模 m 的简化剩余系。
- 模 有原根的充要条件是 ,其中 是奇素数, 是任意正整数。
- 对正整数 ,如果 a 是模 m 的原根,那么 a 是整数模m乘法群(即加法群 Z/mZ 的可逆元,也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zm×的一个生成元。由于Zm×有 个元素,而它的生成元的个数就是它的可逆元个数,即 个,因此当模 有原根时,它有 个原根。
一些数的原根列表
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) 证明如果 ,则 。
参考资料及注释
参见