欧拉定理


一、   欧拉定理

       若正整数 a , n 互质,则  aφ(n)1(mod n)   其中 φ(n) 是欧拉函数1~n)  n 互质的数。

证明如下:
        不妨设X1X2 ...... Xφn1~nn互质的数。
      首先我们先来考虑一些数:aX1aX2 ...... aXφn这些数有如下两个性质:
    1)任意两个数模n余数一定不同:(反证)若存在aX1aX2mod n,则 n | aX1 - aX,而an互质且X1 - X2< n,所以n不可能整除 aX1 - aX,也就是说
不存在aX1aX2mod n。归纳法:对于任意的与n互质的Xi均成立。故得证。那么因为有 φn 个这样的数,Xmod ni=1~φn所以就有 φ个不同的余数,并且都是模数自然是0~n-1
    2)对于任意的aXimod n都与n互质。这不难想,因为an互质这是欧拉函数的条件,Xi1~nn互质的数的集合中的元素。所以如果a*Xi做为分子,n做为分母,那么
他们构成的显然就是一个最简分数,也就是aXin互质。接下来就可以用欧几里得算法:

         因为:gcdaXin==1
         所以:gcdaXin== gcdnaXi%n== 1

         这样,我们把上面两个性质结合一下来说,aX1mod n),aX2mod n ...... aXφnmod n构成了一个集合(性质1证明了所有元素的互异性),并且这些数是1~nn互质的所有数构成的集合(性质1已说明)。这样,我们巧妙的发现了,集合{ aX1mod n),aX2mod n ...... aXφnmod n}经过一定的排序后和集合{ X1X2 ...... Xφ}完全一一对应。那么:aX1mod n* aX2mod n*  ...... * aXφnmod n= X* X2 * ...... * Xφn   因此:我们可以写出以下式子:
                  aX1 * aX2 *  ...... * aXφ  X* X2 * ...... * Xφn  mod n
即:     aφ-1X* X2 * ...... * Xφn  0 mod n

又因为X* X2 * ...... * Xφnn互质,所以, aφ-1| n,那么aφ 1mod n。欧拉定理得证。



二、   费马小定理

对于质数p,任意整数a,均满足:apamod p
如果a,p 互质也可写为: ap-1    1  (mod p)


证明如下:
        这个可以用欧拉定理来说明:首先,我们把这个式子做一个简单变换得:ap-1 * a  amod p 因为 amod p恒成立,所以ap-1 mod p == 1时费马小定理才成立,又因为p是质数,所以 φn == n-1 ,所以根据欧拉定理:若ap互质则ap-1 mod p == 1成立。那么对于ap不互质,因为p是质数,所以,a一定是倍数a a  0mod p。综上所述,费马小定理成立,其实它算是欧拉定理的一个特例。



三、   欧拉定理的推论:

若正整数an互质,那么对于任意正整数b,有abab mod φnmod n

证明如下:(类似费马小定理的证明)
       把目标式做一简单变形:ab - b mod φn* ab mod φn ab mod φnmod n,所以接下来只需要证明ab - b mod φn 1 mod n,又因为: b - b mod φn))φn,不妨设: b - b mod φn))= q*φnq为自然数),则有aq*φn== aqφn,因为an互质,那么aqn也互质,那么就转换到了欧拉定理:aqφn 1 mod n,成立。所以我们这个推论成立。


       这个推论可以帮助我们在求幂运算的时候缩小数据范围和计算次数。具体的说:在求乘方运算时,可以先把底数对mod取模,再把指数对b mod φn取模。
特别的,如果amod不互质,且b>φn时,abab mod φnφnmod n


  


打赏作者

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

Powered by JXHGZ.COM

此博客中的热门博文

sort函数和Python部分函数的使用

blogger添加代码高亮教程