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

课件18张PPT。1费马小定理和欧拉定理欧拉定理 费马定理及其对循环小数的应用 本节主要通过应用简化剩余系的性质证明数论中的两个重要定理，欧拉定理和费马定理,并说明其在理论和解决实际问题中的应用。一、两个基本定理定理1?Euler? 设 m是正整数，(a, m) = 1， 则 a??m) ? 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， 所以 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，则p?a， 所以 a p ? 0 ? a (mod p) a??m) ? 1 (mod m)注:根据欧拉定理，当(a, m) = 1时，总能找到x=?(m)，使得ax? 1 (mod m)。但?(m)并不是使ax? 1 (mod m)成立的自然数x中的最小数。二、定理的应用举例例1 求131956 被60除的余数。a??m) ? 1 (mod m)即 131956被60除的余数为1。解：练习 求313159被7除的余数。所以由欧拉定理得 a??m) ? 1 (mod m)从而 5159= (56)2653 ? 53 (mod 7) 53 = 25?5 ? 4?5 ? 6 (mod 7)。即 313159被7除的余数为6。解：313159a??m) ? 1 (mod m)即 所求余数为5例3 如果今天是星期一，再过101010天是星期几？即得：再过101010天是星期五。解：三、在分数与小数互化中的应用 有理数，即有限小数和无限循环小数，可以用
分数来表示。利用欧拉定理可以解决分数、小数的
转化问题。1.定义 如果对于一个无限小数 则称之为循环小数，并简记为 注：若找到的t是最小的，则称 为循环节；t称为循环节的长度；若最小的s＝0， 则称该小数为纯循环小数，否则为混循环小数。2.定理3 有理数 能表示为纯循环小数 即：分母不含质因数2或5。 (b, 10) = 1 由Euler定理可知，有正整数k，使得10k ? 1 (mod b)，0 ? k ? ?(b)，因此存在整数q使得 而且ak, ?, a1不能都等于0，也不能都等于9。 = 0.akak ? 1?a1akak ? 1?a1? 。3.定理4 设a与b是正整数，0 < a < b，(a, b) = 1， 并且 b = 2?5?b1，(b1, 10) = 1，b1 ? 1， 此处?与?是不全为零的正整数， 其中不循环的位数码个数是? = max{?? ?}.证明：不妨假设? = ? ? ?， 其中0 ? a1 ? b1，0 ? M ? 10?， 且(a1, b1) = (2? ??a ? Mb1, b1) = (2? ??a, b1) = (a, b1) = 1。M = m110? ? 1 ? m210? ? 2 ? ? ? m?（0 ? mi ? 9，1 ? i ? ?）， 下面说明，上式中的?是最小的不循环位数码的个数。 若不然，设又有正整数λ， 由定理3有 其中?b1?? ??? ? ?， 10?ab1? = ba?。 上式右端可以被5? 整除， 但是(a, 10) = 1，(b1?, 10) = 1， 所以5?????，? ? ?。 这就证明了不循环位数码个数不能再少了。 证明：4.证明：5.