关于原根的一个证明
2008-06-09 18:13阅读：
证明:如果p是一个奇素数，g是p^2的一个原根，那么g是p^k的一个原根，k是任意自然数
什么是原根？参见
http://mathworld.wolfram.com/PrimitiveRoot.html
http://en.wikipedia.org/wiki/Primitive_root_modulo_n
简单的说如果对g来说满足g^j mod p =
1最小的自然数j=φ(p)，那么g是就是p的一个原根。φ(p)是p的欧拉函数。
首先证明g是p（k=1）的一个原根。由费马小定理参见
http://blog.sina.cn/dpool/blog/s/blog_48e3f9cd010002uc.html?vt=4
知g^(p-1) mod p = 1,
p是素数φ(p) = p - 1, 如果存在自然数j使得g^j mod p =
1， j < p - 1。
那么令g^j =
1 + a*p, a是整数， g^(pj) = (1+a*p)^p = 1 + a*p^2 +
C(p,2)*a^2*p^2 + ....
显然有g^(pj) mod p^2 = 1, pj < p*(p-1) = φ(p^2)
这和g是p^2的一个原根矛盾。所以p-1是最小满足
g^j mod p = 1的自然数，g是p的一个原根。
一个有用的性质：假设j是满足g^j mod
q = 1的最小自然数而且 j <
φ(q)，那么j|φ(q)。
如果j不能被φ(q)整除，那么φ(q) = j*a + b , 0 < b < j， g^φ(q) = g^(j*a+b)
= （g^j)^a *g^b
g^φ(q) mod p = 1 -> (g^
j)^a *g^b mod
q = 1 -> g^b mod
q = 1 由于b < j
这与j是
满足g^j mod
q = 1的最小自然数矛盾。
下面由数学归纳法证明对k >= 2成立，
假设n = k时成立，即φ(p^k) = p^(k-1)*(p-1)是满足g^j mod p^k = 1最小自然数j。
对n = k + 1,首先g^j mod p^(k+1) != 1, 0 < j < p^(k-1)*(p-1),
证明：如果存在
g^j mod p^(k+1) = 1, 0 < j < p^(k-1)*(p-1)那么显然 g^j mod p^k =
1这和p^(k-1)*(p-1)是满足g^j mod p^k = 1最小自然数j矛盾。
所以如果存在j < φ(p^(k+1)) = p^k*(p-1)满足 g^j mod p^(k+1) = 1 那么j >=
p^(k-1)*(p-1)
又由刚才证明的性质知j|p^k*(p-1),因此j可能的取值只有p^(k-1)*(p-1)，p^k两个值。
对于j = p^(k-1)*(p-1)如果成立那么会有：g^(p^(k-1)*(p-1)) mod p^(k+1) = 1
对n = k时g是p^k的一个原根，因此g^(p^(k-2)*(p-1)) mod p^k != 1 因为
p^(k-2)*(p-1) < p^(k-1)*(p-1)
由欧拉定理，参见
http://blog.sina.cn/dpool/blog/s/blog_48e3f9cd010002uc.html?vt=4
g^(φ(p^(k-1))) =
g^(p^(k-2)*(p-1)) mod p^(k-1) = 1
刚证明了g^(p^(k-2)*(p-1)) mod p^k != 1
由以上得
g^(p^(k-2)*(p-1))
= a*p^(k-1) + 1，a是整数，(a,p) =
1。
g^(p^(k-1)*(p-1)) = （a*p^(k-1) + 1）^p = 1 + a*p^k +
C(p,2)*a^2*p^(2k-2) + C(p,3)*a^3*p^(3k-3) + ....
p是奇素数所以C(p,2) = p*(p-1)/2 = b*p, 自然数 b = (p-1)/2
g^(p^(k-1)*(p-1)) = 1 + a*p^k + a^2*b*p^(2k-1) +
C(p,3)*a^3*p^(3k-3) + ....
由k >= 2得
2*k-1 >= k + 1,
当 m >= 3时
m(k-1) >= k + 1，
所以 g^(p^(k-1)*(p-1)) mod p^(k+1) = 1 + a*p^k
!=
1与假设矛盾
对于j = p^k 如果成立那么会有：
g^(p^k) mod p^(k + 1) = 1 -> g^(p^k) mod p^k = 1
当n = k时p^(k-1)*(p-1)是满足g^j mod p^k = 1 最小自然数j。
那么显然有p^(k-1)*(p-1)|p^k -> (p-1)|p, p是奇素数显然不可能。
所以不存在j < φ(p^(k+1)) = p^k*(p-1)满足 g^j mod p^(k+1) = 1
由欧拉定理知g^(φ(p^(k+1))) mod p^(k+1) = 1,所以φ(p^(k+1))是满足g^j mod
p^(k+1)的最小自然数。
因此n=k+1也成立。
因此命题得证。
一个例子： 2是3^2的一个原根，所以2是3^k的一个原根，k为自然数
k = 1
2^1 mod 3 = 2
2^2 mod 3 = 1
k = 2
2^1 mod
9 = 2
2^2 mod 9 = 4
2^3 mod 9 = 8
2^4 mod 9 = 7
2^5 mod 9 = 5
2^6 mod 9 = 1
k = 3
2^1 mod 27 = 2
2^2 mod 27 = 4
2^3 mod 27 = 8
2^4 mod 27 = 16
2^5 mod 27 = 5
2^6 mod 27 = 10
2^7 mod 27 = 20
2^8 mod 27 = 13
2^9 mod 27 = 26
2^10 mod 27 = 25
2^11 mod 27 = 23
2^12 mod 27 = 19
2^13 mod 27 = 11
2^14 mod 27 = 22
2^15 mod 27 = 17
2^16 mod 27 = 7
2^17 mod 27 = 14
2^18 mod 27 = 1
原根的很重要的一个性质：
g是q的一个原根，那么g^k mod q， k为自然数
组合成一个以φ(q)为周期的循环数列，每个循环节中的元素各不相同而且都满足与q互质，且循环节最后一个元素是1。
