《欧拉定理》课件1.ppt

《《欧拉定理》课件1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.5欧拉定理人教B版数学选修4-6《初等数论初步》欧拉定理定理1Euler设m是正整数，(a,m)=1，则am)1(modm)。证明设{x1,x2,,x(m)}是模m的一个简化剩余系，则{ax1,ax2,,ax(m)}也是模m的简化剩余系，因此ax1ax2ax(m)x1x2,x(m)(modm)，a(m)x1x2x(m)x1x2,x(m)(modm)。(1)由于(x1x2x(m),m)=1，所以由式(1)得出a(m)1(modm)。例1设m=11,a=2,显然(11,2)=1,(11)=102101(mod11)定理2(Fermat)设p

2、是素数，则对于任意的整数a，有apa(modp)。证明若(a,p)1，则由定理1得到ap11(modp)apa(modp)。若(a,p)>1，则pa，所以ap0a(modp)。证毕。例2设p.q是两个不同的奇素数,n=pq,a是与pq互素的整数,如果整数e满足1

3、p)1(modp)两端作k(n)/p))次幂得a1+k(n)a(modp)即aeda(modp)同理aeda(modq),因为p,q是素数,故aeda(modn),因此,cd(ae)da(modn)证毕RSA公钥密码算法(1)选取两个大素数p，q(2)计算n=pq，(n)=（p-1）(q-1)(3)随机选取正整数e，1

4、≡cd(modn),定理3(威尔逊定理)p为素数iff(p-l)!-1(modp).证明:必要性:设p为一素数,当p=2,3时,结论显然成立.现设p>3是一奇素数,S={1,2,3,…,p-2,p-1}，aS.因为(a,p)=1,存在整数d,1≤d<(p)使得ad1(modp).又a=diffa21(modp).此时,a=1或p-1,将2,…p-2中的a和d配对,则1×2×…×(p-2)(p-1)1×(p-1)×p-1(modp)2.4欧拉定理,费马定理定理3(威尔逊定理)p为素数iff(p-l)!-1(modp).充分性:若(p-1)!=-l(modp),则p为素数.假设p

5、是合数,令p＝ab,a≠p.由题设条件知,p

6、((p-1)!+l).又因a

7、p,则有a

8、((p-1)!+1).但由于a≤p-1可得a

9、(p-1)!,从而a

10、(((p-1)!+1)-(p-1)!),即a

11、l,因而p只有因子1和p,即p为素数TheEnd