关于原根的一些知识点:
定义1:设,
,使得
成立的最小的
,称为
对模
的阶,记为
。
定理1:如果模有原根,那么它一共有
个原根。
定理2:若,
,
,则
。
定理3:如果为素数,那么素数
一定存在原根,并且模
的原根的个数为
。
定理4:设是正整数,
是整数,若
模
的阶等于
,则称
为模
的一个原根。
假设一个数对于模
来说是原根,那么
的结果两两不同,且有
,那么
可以称为是模
的一个原根,归根到底就是
当且仅当指数为
的时候成立。(这里
是素数)
定理5:模有原根的充要条件:
,其中
是奇素数。
求模素数原根的方法:对
素因子分解,即
是
的标准分解式,若恒有
成立,则就是
的原根。(对于合数求原根,只需把
换成
即可)
以上内容转自http://blog.csdn.net/acdreamers/article/details/8883285
求原根的代码:
题目:
poj 1284
题意:
给出一个数n,求原根数目。
限制:
3 <= n < 65536; n为奇素数。
思路:
因为n是素数,所以模n的原根数=phi(phi(n))=phi(n-1)。
phi(i) 可以预处理出来。
原文:http://blog.csdn.net/whai362/article/details/43525015