早教吧作业答案频道 -->数学-->
请问广义欧几里德除法拿来干嘛的?还有模重复平方法又有什么用?欧拉定理呢?都会求了,但是不知道什么时候用.
题目详情
请问广义欧几里德除法拿来干嘛的?还有模重复平方法又有什么用?欧拉定理呢?都会求了,但是不知道什么时候用.
▼优质解答
答案和解析
首先证明下面这个命题:对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n互素的数,即n的一个化简剩余系(或称简系、缩系),考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} .则S = Zn1) 由于a,n互质,xi也与n互质,则a*xi也一定与n互质,因此任意xi,a*xi(mod n) 必然是Zn的一个元素 .2) 对于Zn中两个元素xi和xj,如果xi ≠ xj则a*xi(mod n) ≠ a*xj(mod n),这个由a、n互质和消去律可以得出.所以,很明显,S=Zn既然这样,那么(a*x1 × a*x2×...×a*xφ(n))(mod n)= (a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n))(mod n)= (x1 × x2 × ... × xφ(n))(mod n)考虑上面等式左边和右边左边等于([a^φ(n)] *(x1 × x2 × ... × xφ(n))) (mod n)右边等于x1 × x2 × ... × xφ(n))(mod n)而x1 × x2 × ... × xφ(n)(mod n)和n互质根据消去律,可以从等式两边约去,就得到:a^φ(n) ≡ 1 (mod n)推论:对于互质的数a、n,满足a^(φ(n)+1) ≡ a (mod n)费马定理:a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p)证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明.推论:对于任意正整数a,有a^p ≡ a (mod p),因为a能被p整除时结论显然成立.
看了 请问广义欧几里德除法拿来干嘛...的网友还看了以下:
英语翻译最近陈先生在医院静养,因为前天他在一次追捕一个罪犯的时候不小心把腿弄骨折了.还有1个星期就 2020-05-13 …
英语翻译最近陈先生在医院静养,因为前天他在一次追捕一个罪犯的时候不小心把腿弄骨折了.还有1个星期就 2020-05-23 …
用汽点增减或用汽量波动都会一定程度地造成汽提蒸汽波动,调节时,应联系生产指挥中心统一调度, 2020-05-31 …
用“严”字组词填空我要上学了苏格拉底对自己要求十分(),做任何事前都会制定()的计划,工作中始终保 2020-06-14 …
2014年索契冬季奥运会上,每一位参赛者的双腿上都会绑定一对重量极轻且性能可靠的异频雷达收发机.相 2020-06-25 …
云图中的一段话,求英文.我们的生命不仅是我们自己的.从子宫到坟墓,我们和其他人紧紧相连,无论前生还 2020-06-29 …
材料一、2009年12月7日至18日,《联合国气候变化框架公约》第15次缔约方会议暨《京都议定书》 2020-07-23 …
英语翻译因为航空公司在出货前都会预定航班,但实际的货物到达时间要以实际到达时间为准,请知悉, 2020-11-01 …
一位学生在给老师的信中写到:我是一个自制力很差的学生。每学期一开始,我都会制定很多的学习计划,可是随 2020-11-24 …
英语翻译最近陈先生在医院静养,因为前天他在一次追捕一个罪犯的时候不小心把腿弄骨折了.还有1个星期就能 2020-12-09 …