早教吧 育儿知识 作业答案 考试题库 百科 知识分享

请问广义欧几里德除法拿来干嘛的?还有模重复平方法又有什么用?欧拉定理呢?都会求了,但是不知道什么时候用.

题目详情
请问广义欧几里德除法拿来干嘛的?还有模重复平方法又有什么用?欧拉定理呢?都会求了,但是不知道什么时候用.
▼优质解答
答案和解析
首先证明下面这个命题:对于集合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整除时结论显然成立.
看了 请问广义欧几里德除法拿来干嘛...的网友还看了以下:

请问下梯形边长怎么算准确呢.比如一块地面积.一边7.4一边32.2长度97这总共会算多少平方呢.请  2020-05-14 …

英语翻译1.有阅读前做准备的习惯吗?2.阅读前都该做哪些准备呢?3.认为怎样的阅读才算是真正有效的  2020-06-24 …

捕蝉(成新平的)的阅读答案1.文章为何以"捕蝉"为题呢?请简要说说你的理由.2.请简要概括文章捕蝉  2020-06-25 …

1.大明咒有什么作用呢?2.是不是普通人年念明咒也管用呢?3.南无观世音菩萨和大明咒哪个好呢?4.  2020-07-03 …

打电话时,说请稍等,除了用holdonplease,amomentplease,还有没有其他说法呢  2020-07-25 …

假如你是美术学院的老师,学院请你们出一道绘画题目,这个题目要用连续的两句诗来表现,诗句中要求活泼可可  2020-11-04 …

下列是爸爸妈妈因为你最近的表现而争吵,你该怎么说?爸爸生气地说:你怎么就不管管孩子,你看他现在成什么  2020-11-23 …

平抛运动的闪光图我想向您曾经解答过的题目请教一下(闪光图平抛运动的方格边长为5cm,g取10m/s2  2020-11-25 …

阅读下面一段文字,按要求答题。每个人都有自己的爱好,我也不例外,我的爱好是看书。家中那大书柜里,一至  2020-11-28 …

阅读下面一段文字,按要求答题。每个人都有自己的爱好,我也不例外,我的爱好是看书。家中那大书柜里,一至  2020-11-28 …