关于原根的一个问题

gracias

对于一个素数p，如果k是p^2的原根，则k是所有p^n（n>=1）的原根，谁能证明一下?

〇〇

原根是什么？

mathe

应该可以用二项式定理来证明

gxqcn

p 应限定大于2

gracias

对，p是奇素数。谁能给个证明？

hyperthread

简单写下： 因为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有一个原根，则可找出它其他的原根

nyy

找个数论教材就知道了，这问题不难，初等数论及其应用，这本书上就有！