原根

维基百科,自由的百科全书

跳转到: 导航, 搜索

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

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

由此,在(a,m) = 1時,定義a对模m的指数Ordm(a)為使a^d \equiv 1 \pmod{m}成立的最小的正整数d。由前知Ordm(a) 一定小于等于 φ(m),若Ordm(a) = φ(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} ,则 d 整除 φ(m)。因此Ordm(a)整除φ(m)。在例子中,当a = 3时,我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
  • δ = Ordm(a),则a^0,a^1,a^2 \cdots , a^{\delta -1} 模 m 两两不同余。因此当a是模m的原根时,a^0,a^1,a^2 \cdots , a^{\delta -1} 构成模 m 的简化剩余系
  • m有原根的充要條件是m = 1,2,4,pn,2pn,其中p是奇質數,n是任意正整數
  • 对正整数(a,m) = 1,如果 a 是模 m 的原根,那么 a 是整数模n乘法群(即加法群 Z/mZ 的可逆元,也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zn×的一个生成元。由于Zn×φ(m)个元素,而它的生成元的个数就是它的可逆元个数,即 φ(φ(m))个,因此当模m有原根時,它有φ(φ(m))個原根。

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

m 模m的原根
2 1
3 2
4 3
5 2,3
6 5
7 3,5

除了直接運算以外,至今還沒有一個辦法可以找到模特定m時的原根,但假如已知模m有一個原根,則可找出它其他的原根

[编辑] 參見

个人工具