- 中文名
- 原根
- 外文名
- Primitive Root
- 适用领域
- 数论
- 应用学科
- 数学
定义
播报编辑
假设一个数g是P的原根，那么g^i mod P的结果两两不同，且有 1<g<P，0<i<P，归根到底就是渗判元g^(P-1) = 1 (mod P脚兰)当且仅当指数为P-1的时芝笑晚想候成立.(这里P是设杠设素数)。
简单来说，g^i mo热踏d p ≠ g^j mod p （p为素数），其中i≠j且i, j介于体章境1至(p-1)之间，则g为p的原根。
性质
播报编辑
原根具有以下性质：
（1）对于任意正整数a,m,如果(a,m) = 1,存在最小的正整数 d 满足a^d≡1(mod m)，则有 d 整除 φ(m)，因此Ordm(a)整除φ(m)。这里的d被称为a模m的阶，记为Ordm(a)。
例如:求3模7的阶时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
（4）对正整数(a,m) = 1，如果 a 是模 m 的原根，那么 a 是整数模n乘法群（即加法群 Z/mZ的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zn的一个生成元。由于Zn有 φ(m)个元素，而它的生成元的个数就是它的可逆元个数，即 φ(φ(m))个，因此当模m有原根时，它有φ(φ(m))个原根。 [2]
原根存在条件
播报编辑
原根存在的条件有以下几个：
定理一：设p是奇素数，则模p的原根存在； [3]
定理二：设g是模p的原根，则g或者g+p是模
定理三：设p是奇素数，则对任意
定理四：设
例子
播报编辑
设m= 7，则φ（7）等于6。
设a= 2，由于2^3=8≡1(mod 7)，2^6=64≡1(mod7)，2^3≡2^6(mod7)，所以 2 不是模 7 的一个原根。设a= 3，由于3^1≡3(mod 7)，3^2≡2(mod 7)，3^3≡6(mod 7)，3^4≡4(mod 7)，3^5≡5(mod 7)，3^6≡1(mod 7)，所以 3 是模 7 的一个原根。
补充一点，根据原根的性质1，只需要验证3^1，3^2，3^3，3^6即可，这样可以简化运算。
