关于原根的一个问题
对于一个素数p，如果k是p^2的原根，则k是所有p^n（n>=1）的原根，谁能证明一下? 原根是什么？ 应该可以用二项式定理来证明 p 应限定大于2 对，p是奇素数。谁能给个证明？ 简单写下：因为k是 p^2的原根, k^(p-1)=1 mod p, k^(p-1)<>1 mod p^2,
k^(p-1)=cp+1 with gcd(c,p)=1
(k^(p-1))^(p^(n-2))=(cp+1)^(p^n-2)=1 + cp^(n-1) mod p^n <> 1 mod p^n(这步展开能得到）
并且，ord_p^n(k)|(p-1)*p^(n-1)
所以，ord_p^n(k) 是 就是(p-1)*p^(n-1) 原根
维基百科，自由的百科全书
跳转到： 导航, 搜索
在数论，特别是整除理论中，原根是一个很重要的概念。
对于两个正整数(a,m) = 1，由欧拉定理可知，存在正整数， 比如说欧拉函数d = φ(m)，即小于等于 m 的正整数中与 m 互质的正整数的个数，使得。
由此，在(a,m) = 1时，定义a对模m的指数Ordm(a)为使成立的最小的正整数d。由前知Ordm(a) 一定小于等于 φ(m)，若Ordm(a) = φ(m)，则称a是模m的原根。
目录 [隐藏]
1 例子
2 性质
3 一些数的原根列表
4 参见
[编辑] 例子
设m = 7，则等于6。
设a = 2，由于，而，所以 2 不是模 7 的一个原根。
设a = 3，由于，，，，，，因此有，所以 3 是模 7 的一个原根。
[编辑] 性质
可以证明，如果正整数(a,m) = 1和正整数 d 满足，则 d 整除 φ(m)。因此Ordm(a)整除φ(m)。在例子中，当a = 3时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
记δ = Ordm(a)，则模 m 两两不同余。因此当a是模m的原根时，构成模 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有一个原根，则可找出它其他的原根 找个数论教材就知道了，这问题不难，初等数论及其应用，这本书上就有！
页:
[1]