原根

· · 个人记录

什么是原根？

首先你要知道：

其中\varphi(1)=1

当两个正整数a,m符合以下要求时，a是m的原根：

  1. \gcd(a,m)=1

此时，称d为a模m的阶（记为\delta _ma或\delta m(a)或\operatorname{Ord}_ma，当然你可以不管它），称a为m的原根。

即：

如果a^d\equiv 1(\mod m)(只有\gcd(a,m)=1时才可能成立)，就把d叫做a模m的阶。

在各个d的取值当中取一个最小的，如果这个最小的d等于\varphi(m)，就把a叫做m的原根

（其实应该称作a模m的原根，但是……不理它了QωQ）

原根有以下性质：

  1. 符合a^d\equiv 1(\mod m)任意一个d都一定是最小的d的倍数

  2. 如果把符合a^d\equiv 1(\mod m)最小的d记为\delta，那么{a^1\mod m,a^2\mod m,a^3\mod m,......,a^{\delta-1}}等于{1,2,3,,\delta-1}（大括号内为集合，就是无序的数组）

  4. 如果一个数m有原根，那么它就有\varphi(\varphi(m))个原根