《费马小定理和欧拉定理》课件

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

1、1费马小定理和欧拉定理欧拉定理费马定理及其对循环小数的应用本节主要通过应用简化剩余系的性质证明数论中的两个重要定理，欧拉定理和费马定理,并说明其在理论和解决实际问题中的应用。一、两个基本定理定理1Euler设m是正整数，(a,m)=1，则am)1(modm).证明：设{x1,x2,,x(m)}是模m的一个简化剩余系，则{ax1,ax2,,ax(m)}也是模m的简化剩余系，所以ax1ax2ax(m)x1x2x(m)(modm)，即a(m)x1x2x(m)x1x2x(m)(modm).得(x1

2、x2x(m),m)=1，所以a(m)1(modm).定理2(Fermat)设p是素数，apa(modp)。注：Fermat定理即是欧拉定理的推论。证：由于p是素数，若(a,p)1，则由定理1得到ap11(modp)apa(modp)若(a,p)>1，则pa，所以ap0a(modp)am)1(modm)注:根据欧拉定理，当(a,m)=1时，总能找到x=(m)，使得ax1(modm)。但(m)并不是使ax1(modm)成立的自然数x中的最小数。二、定理的应用举例例1求13195

3、6被60除的余数。am)1(modm)即131956被60除的余数为1。解：练习求313159被7除的余数。所以由欧拉定理得am)1(modm)从而5159=(56)265353(mod7)53=255456(mod7)。即313159被7除的余数为6。解：313159am)1(modm)即所求余数为5例3如果今天是星期一，再过101010天是星期几？即得：再过101010天是星期五。解：三、在分数与小数互化中的应用有理数，即有限小数和无限循环小数，可以用分数来表示。利用欧拉定理可以解决分

4、数、小数的转化问题。1.定义如果对于一个无限小数则称之为循环小数，并简记为注：若找到的t是最小的，则称为循环节；t称为循环节的长度；若最小的s＝0，则称该小数为纯循环小数，否则为混循环小数。2.定理3有理数能表示为纯循环小数即：分母不含质因数2或5。定理3有理数能表示为纯循环小数(b,10)=1由Euler定理可知，有正整数k，使得10k1(modb)，0k(b)，因此存在整数q使得而且ak,,a1不能都等于0，也不能都等于9。=0.akak1a1akak1a1。3.定理4设a与b是正整数，0

5、

6、b1，10ab1=ba。上式右端可以被5整除，但是(a,10)=1，(b1,10)=1，所以5，。这就证明了不循环位数码个数不能再少了。证明：4.证明：5.