Question

为什么素数p有原根?

是不是只有对大于一的正整数m,m=2,4,p^l(l为正整数），2p^l(l为正整数）才有原根？
为什么呢？
如果其他的很难证，就只证一下素数p有原根吧.

Answer 1

是的，只有这些数有原根。素数原根的存在性是最不容易证明的。这些符号不好打，我就说一种证法。
你应该懂费马小定理吧，就是说a^(p-1)=1(mod p)，所以某数a一定有一个幂模p后和1同余，这个幂指数一定是p-1的因子,最小的叫做指标。

先把p-1分解，设p-1=(a^m)*(b^n)*...
我们可以找到一个数A，它的指标是a^m。方法是设k是1,2,...,p-1里的一个数，满足k^((p-1)/a)不与1同余(都是模p，我以后不说了)，那么A同余于k的((p-1)/a^m)次幂。
同样可以找到一个数B，它的指标是b^n，等等。则A*B*...就是p的一个原根