Question

对于任意一个正整数a是否都存在一个素数p以它为原根

补充下：a不是完全平方数

Answer 1

一个非常著名的猜想跟你说的这个挺像。
搜索一下 Artin's conjecture 。
说的是：任意一个整数a，除了1、-1、和完全平方数之外，都有无穷多个素数p 以它为原根。

追问

可是我只要求存在性，并不要求有无穷多个这样的素数，这个难度比这个猜想容易的多啊

追答

这倒是。不过我很菜，不仅无法回答你的问题，甚至连那个猜想里为什么把完全平方数给除掉都不明白。如果你明白了，还恳请告诉我。

追问

因为除了2，其他的素数都为奇数，对于奇素数p，它的欧拉函数φ(p)=p-1为一个偶数，对于一个完全平方数x^2（不妨让x与p互素），由费马小定理有x^(p-1)≡1 (mod p)，所以(x^2)^((p-1)/2)≡1 (mod p)，所以x^2不能是原根。变成我回答你的问题了……

追答

赞，还真是。

Answer 2

搜索一下 Artin's conjecture 。
说的是：任意一个整数a，除了1、-1、和完全平方数之外，都有无穷多个素数p 以它为原根。