原根

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

例子[编辑]

m=7,则 \varphi (m)等于6。

  • a=2,由于2^3 = 8 \equiv 1 \pmod{7} ,而\displaystyle 3 < 6 ,所以 2 不是模 7 的一个原根。
  • a=3,由于3^1  \equiv 3 \pmod{7} 3^2  \equiv 2 \pmod{7} 3^3  \equiv 6 \pmod{7} 3^4  \equiv 4 \pmod{7} 3^5  \equiv 5 \pmod{7} 3^6  \equiv 1 \pmod{7} ,因此有Ord_7(3) = 6 =\varphi (7),所以 3 是模 7 的一个原根。

性质[编辑]

  • 可以证明,如果正整数(a,m)=1和正整数 d 满足a^d \equiv 1 \pmod{m} ,则 Ord_m (a) 整除 d。[1]因此Ord_m (a)整除 \varphi (m) 。在例子中,当a=3时,我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
  • m有原根的充要條件是m = 2 , 4 , p^n , 2p^n,其中p是奇質數,n是任意正整數
  • 对正整数(a,m)=1,如果 a 是模 m 的原根,那么 a 是整数模n乘法群(即加法群 Z/mZ 的可逆元,也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zn×的一个生成元。由于Zn× \varphi (m)个元素,而它的生成元的个数就是它的可逆元个数,即  \varphi (\varphi (m))个,因此当模m有原根時,它有\varphi (\varphi (m))個原根。

一些數的原根列表[编辑]

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 8
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有一個原根,則可找出它其他的原根

参考资料及注释[编辑]

參見[编辑]