数学

突然今天，我想不起什么是原根来了，查了一下定义，哎~这货不是离散数学，循环群生成元吗？？不是而是是乘法而不是加法而是是乘法而不是加法而是是乘法而不是加法 嘛玩意是原根：?

对于素数 p，如果存在一个正整数 11–>6–>4–>2–>0，然后开始循环 2不是7的原根，因为2–>4–>1–>2–>4…，过早的循环了

说人话：好的

如果g是P的原根，就是(gP−1)≡1(modP)(g^P-1) ≡1 (mod P)(gP−1)≡1(modP)当且仅当指数为P-1的时候成立.(这里P是素数). 即 设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。 φ(m)：这货是欧拉函数

定理：

定理一： 设p是奇素数，则模p的原根存在； [3] 定理二： 设g是模p的原根，则g或者g+p是模的原根； 定理三： 设p是奇素数，则对任意，模的原根存在； 定理四： 设1，则g是模的一个原根，则g与g+中的奇数是模2的一个原根。

性质：

性质一： 对于任意正整数a,m,如果(a,m) = 1,存在最小的正整数 d 满足a^d≡1(mod m)，则有 d 整除 φ(m)，因此Ordm(a)整除φ(m)。这里的d被称为a模m的阶，记为Ordm(a)。 　例如:求3模7的阶时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。 19的原根有2，2-4-8-16-13-7-14-9-。。。。 19的原根就一定有4， 4-16-7-9-。。。。。 有8,16所以也就是说如果一个数的原根没有k也就不存在k的幂。

性质二： 记δ = Ordm(a)，则a1，……a(δ-1)模 m 两两不同余。因此当a是模m的原根时，a0a1，……a(δ-1)构成模 m 的简化剩余系。 性质三： 模m有原根的充要条件是 m=1,2,4,p,2∗p,pn,2∗pn其中p是奇质数，n是任意正整数。m= 1,2,4,p,2*p,p^n,2*p^n其中p是奇质数，n是任意正整数。m=1,2,4,p,2∗p,pn,2∗pn其中p是奇质数，n是任意正整数。

性质四： 对正整数(a,m) = 1，如果 a 是模 m 的原根，那么 a 是整数模n乘法群（即加法群 Z/mZ的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zn的一个生成元。由于Zn有 φ(m)个元素，而它的生成元的个数就是它的可逆元个数，即 φ(φ(m))个，因此当模m有原根时，它有φ(φ(m))个原根。 模m有原根的充要条件：

m=2 m=4 m=P^a m=2*P^a

怎么求？

我是笨逼枚举

对于合数,只要将2.中的p−1替换成φ(p)即可.对于合数,只要将 2. 中的p-1替换成φ(p)即可.对于合数,只要将2.中的p−1替换成φ(p)即可.