《费马小定理和欧拉定理》完整版-人教版1.pptxVIP

;;当n为素数时，模n的剩余类环中无零因子.;模7剩余环;第三节费马小定理和欧拉定理;;;;;;通过观察一，我们得到模7剩余环、模5剩余环、模3剩余环的规律，又由于3、5、7都是素数，我们猜想：;;;设An=a,2a,3a,4a……(p-1)a假设An中有2项ma,na被p除以后余数是相同得ma=na(modp)即a(m-n)=0(modp)因为a和p互质,所以m-n=0(modp)又因为m,n属于集合{1,2,3..p-1}且m不等于n所以m-n不可能是p的倍数.推出和假设产生矛盾.;所以An中任意2项被p除得到的余数都不同又因为对于任一个整数被p除以后的余数最多有p-1个,分别是1,2,3,….p-1而数列An中恰好有p-1个数,所以数列中的数被p除以后的余数一定正好包含所有的1,2,3,4,5….p-1所以a*2a*3a*…(p-1)a=1*2*3*4…*(p-1)(modp)对两边进行化简,即可以得到a(p-1)=1(modp);;我们看到在费马小定理中针对的是m为素数的情况，对于其它数能否找到类似的性质呢，这就是下面要讲的欧拉定理.;(1)令

则Zn=S.

①因为a与n互质，xi(1≤i≤φ(n))与n互质，所以a*xi与n互质，所以a*ximodn∈Zn.

②若i≠j，那么xi≠xj，且由a,n互质可得a*ximodn≠a*xjmodn（消去律）.;对比等式的左右两端，因为xi(1≤i≤φ(n))与n互质，所以aφ(n)≡1modn（消去律）.;;;二、设p是素数，p?bn?1，n?N，则下面的两个结论中至少有一个成立：(ⅰ)p?bd?1对于n的某个因数dn成立；(ⅱ)p?1(modn).;若dn，则结论(ⅰ)得证.

若d=n，则n?p?1，即p?1(modn)，这就是结论(ⅱ).;解由题二知

若p?235?1

则p是25?1=31或27?1=127的素因数

或者p?1(mod70)

由于31和127是素数

并且235?1=31*127*8727391

所以，235?1的另外的素因数p只可能在数列;71，211，281，?(5)中

经检验，得到8727391=71*122921.

显然??122921的素因数在31，127或者数列(5)中

说明，122921不能被31和127整除，也不能被数

列(5)中的不超过;;5、设p，q是两个不同的素数，证明：

pq?1?qp?1?1(modpq).;612?1=(63?1)(63?1)(66?1)

=5*43*7*31*46657对于46657，它的素因数必为12k?1型，经检验的46657=13*37*97故612?1=5*7*13*31*37*43*97.;证明：因561=3*11*17，对于一切整数a，(a,561)=1，有(a,3)=1，(a,11)=1，(a,17)=1，由费马定理可得a560=(a2)280?1