证明:如果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.com.cn/s/blog_48e3f9cd010002uc.html
知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.com.cn/s/blog_48e3f9cd010002uc.html

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。