万维百科

原根

数论,特别是整除理论中,原根是一个很重要的概念。

对于两个正整数,由欧拉定理可知,存在正整数, 比如说欧拉函数,即小于等于的正整数中与互素的正整数的个数,使得

由此,在时,定义对模的指数为使成立的最小的正整数。由前知 一定小于等于 ,若,则称是模的原根

例子

,则等于6。

  • ,由于,因此有,所以 2 不是模 7 的一个原根。
  • ,由于,因此有,所以 3 是模 7 的一个原根。

性质

  • 可以证明,如果正整数和正整数 d 满足,则 整除 d。因此整除。在例子中,当时,我们仅需要验证 3 的 2、3 次方模 7 的余数即可,如果其中有一个是1,则3就不是原根。
  • ,则模 m 两两不同余。因此当是模的原根时,构成模 m 的简化剩余系
  • 有原根的充要条件是,其中是奇素数,是任意正整数
  • 对正整数,如果 a 是模 m 的原根,那么 a 是整数模m乘法群(即加法群 Z/mZ 的可逆元,也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zm×的一个生成元。由于Zm×个元素,而它的生成元的个数就是它的可逆元个数,即 个,因此当模有原根时,它有个原根。

一些数的原根列表

m 模m的原根(有*号的数没有原根,此时是有最大模m周期的数) 周期 (OEISA002322)
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) 证明如果 ,则

参考资料及注释

参见


本页面最后更新于2021-06-23 21:41,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器