大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
说这种最好就是举个例子
比如说求81的所有原根
先说欧拉函数通式：
通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
1.先算81的欧拉函数，结果为54, 又54的素因数有2和3, 54除以这两个素因数得到18和27
2. 从2，4，5开始验算 2^18 != 1 mod 81 ,2^27 != 1 mod 81, 所以2是81的原根（只要找到一个由素因数的出来的次数mod81不等于1的就可以停止了）
3.原根的个数就是就81算两次欧拉函数，得到18，那就用18个原根，54的简化剩余系的各个数字作为第二步找到的原根的次数就行
54的简化剩余系（其实就是与54互素的）为{1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53}
那么81的所有原根为{2^1, 2^5, 2^7,2^11…………2^53} ，不要忘了，里面的值还要mod81的哦
即{2^1mod81, 2^5mod81, 2^7mod81,2^11mod81…………2^53mod81}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219623.html原文链接：https://javaforall.net
