《《费马小定理和欧拉定理》课件》由会员分享，可在线阅读，更多相关《《费马小定理和欧拉定理》课件（18页珍藏版）》请在金锄头文库上搜索。
1、1,费马小定理和欧拉定理,欧拉定理 费马定理及其对循环小数的应用,本节主要通过应用简化剩余系的性质证明数论中的两个重要定理，欧拉定理和费马定理,并说明其在理论和解决实际问题中的应用。,一、两个基本定理,定理1Euler 设 m是正整数，(a, m) = 1，,则 am) 1 (mod m).,证明： 设x1, x2, , x(m)是模m的一个简化剩余系，,则ax1, ax2, , ax(m)也是模m的简化剩余系，,所以 ax1ax2 ax(m) x1x2 x(m) (mod m)，,即 a(m)x1x2 x(m) x1x2 x(m) (mod m).,得 (x1x2 x(m), m) = 1，
2、,所以 a(m) 1 (mod m).,定理2(Fermat) 设p是素数，,a p a (mod p)。,注：Fermat定理即是欧拉定理的推论。,证： 由于p是素数，,若 (a, p) 1，,则由定理1得到,a p 1 1 (mod p), a p a (mod p),若(a, p) 1，则pa，,所以 a p 0 a (mod p),am) 1 (mod m),注:根据欧拉定理，当(a, m) = 1时， 总能找到x=(m)，使得ax 1 (mod m)。 但(m)并不是使ax 1 (mod m)成立的自 然数x中的最小数。,二、定理的应用举例,例1 求131956 被60除的余数。,a
3、m) 1 (mod m),即 131956被60除的余数为1。,解：,练习 求313159被7除的余数。,所以由欧拉定理得,am) 1 (mod m),从而 5159= (56)2653, 53 (mod 7),53 = 255 45 6 (mod 7)。,即 313159被7除的余数为6。,解：313159,am) 1 (mod m),即 所求余数为5,例3 如果今天是星期一，再过101010天是星期几？,即得：再过101010天是星期五。,解：,三、在分数与小数互化中的应用,有理数，即有限小数和无限循环小数，可以用 分数来表示。利用欧拉定理可以解决分数、小数的 转化问题。,1.定义 如果对
4、于一个无限小数,则称之为循环小数，并简记为,注：若找到的t是最小的，则称,为循环节；t称为循环节的长度；若最小的s0，,则称该小数为纯循环小数，否则为混循环小数。,2.定理3 有理数,能表示为纯循环小数,即：分母不含质因数2或5。,(b, 10) = 1,由Euler定理可知，有正整数k，使得,10k 1 (mod b)，0 k (b)，,因此存在整数q使得,而且ak, , a1不能都等于0，也不能都等于9。,= 0.akak 1a1akak 1a1 。,3.定理4 设a与b是正整数，0 a b，(a, b) = 1，,并且 b = 25b1，(b1, 10) = 1，b1 1，,此处与是不全
5、为零的正整数，,其中不循环的位数码个数是 = max .,则 可以表示成混循环小数，,证明：不妨假设 = ，,其中0 a1 b1，0 M 10，,且(a1, b1) = (2 a Mb1, b1) = (2 a, b1) = (a, b1) = 1。,因此，由定理3， 可以表示成纯循环小数：,M = m110 1 m210 2 m（0 mi 9，1 i ），,下面说明，上式中的是最小的不循环位数码的个数。,若不然，设又有正整数，,由定理3有,其中b1 ，,10ab1 = ba。,上式右端可以被5 整除，,但是(a, 10) = 1，(b1, 10) = 1，,所以5， 。,这就证明了不循环位数码个数不能再少了。,证明：,4.,证明：,5.,
