原根

hdxrie · 2018-08-25 21:58:43 · 个人记录

原根

考察方程a^x\equiv1({\rm mod\ }m)， 若gcd(a,m)=1，则方程一定有解x=\varphi(m)，我们定义在上述情况下， 方程最小的解为x'，则显然有x'≤\varphi(m)，若a满足条件x'=\varphi(m)，我们就称a是模m的原根。

定义原根的意义在于，原根非常类似于单位根，故有一些很好的性质，比如说我们考虑当m是质数时，原根有如下等价定义：若g是模m的原根，则g^1,g^2,\cdots,g^{m-1}的值在模m的意义下两两不同，注意到模m剩余系中恰有m个数，而任意一个非零数的幂次都不可能等于0，故原根的幂次在模m的剩余系中是最稠密的，换句话说，仅用原根就能够充分表示模m剩余系的性质。

原根的个数

如果模m有原根，那么原根恰有\varphi(\varphi(m))个。

我们从群论的角度来考虑，如果a是模m的原根，那么a是模m的约化剩余系诱导的乘法群中的生成元，考虑到模m的约化剩余系的乘法群中恰有\varphi(m)个元素，又因为生成元的个数刚好等于可逆元的个数，所以原根恰有\varphi(\varphi(m))个。

上面的解释可能仍旧有些难以理解，下面给出一个比较通俗的证明：

剩余系是加法群，约化剩余系是乘法群。

在剩余系中，可逆元是与模数m互质的数（可能不是叫可逆元，反正大概了解一下定义就行），所以其个数为\varphi(m)，并且可逆元在加法的意义上可以取遍剩余系，也就是说如果令q为可逆元，那么q,2q,\cdots,mq在模m的意义下可以取遍整个剩余系。

约化剩余系由可逆元所组成的，并且原根在乘法的意义上可以取遍约化剩余系，也就是说假设g为模m意义下的一个原根，那么g^1,g^2,\cdots,g^{\varphi(m)}在模m的意义下可以取遍整个约化剩余系，可见原根一定属于约化剩余系，所以我们首先应该在约化剩余系的\varphi(m)个数里寻找。

观察g^1,g^2,\cdots,g^{\varphi(m)}，我们想知道其中有多少数是能在乘法的意义下取遍模m的整个约化剩余系，根据乘法中指数相加以及扩展欧拉定理，我们可以将问题转化成求0,1,\cdots,\varphi(m)-1中有多少数在加法的意义下能取遍模\varphi(m)的剩余系，这样就变成了求模\varphi(m)的剩余系中可逆元的个数，也就是说模m的意义下原根的个数为\varphi(\varphi(m))个。

其他性质

定理1：质数P一定有原根，且恰有\varphi(P-1)个原根，实际上，当且仅当m=2,4,P^α,2P^α时，m才有原根。

定理2：若g是模P的原根，则g或g+P是模P^2的原根。

定理3：若g是模P^α的原根，则g或g+P^α是模2P^α的原根。

上述定理的证明远远超过了目前的知识储备，这些结论也不会以直接的方式出现在正式比赛中， 所以作为了解即可。

原根的求法

由于原根往往不太大，所以枚举即可，在m≤10^5范畴内，我们几乎可以认为枚举的方法是常数级的。

我们还有如下方法可以求得较大数的原根：

考虑对\varphi(m)进行质因数分解，则\varphi(m)=p_1p_2\cdots p_n，其中p_i可以相同，对于一个数g，若对所有的p_i恒有g^{\frac{\varphi(m)}{p_i}}≠1({\rm mod\ }m)成立，则g就是模m的原根。方法的正确性依赖于拉格朗日定理，但我们可以直观上理解，由于我们有g^{\varphi(m)}\equiv 1({\rm mod\ }m)，若g^x\equiv 1({\rm mod\ }m)且x<\varphi(m)，则理应有x|\varphi(m)成立。

原根的应用