如何求原根_求模47的所有原根

如何求原根_求模47的所有原根说这种最好就是举个例子比如说求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/…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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} 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/219623.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号