费马定理、欧拉定理、威尔逊定理(讲稿).doc

《费马定理、欧拉定理、威尔逊定理(讲稿).doc》由会员分享，可在线阅读，更多相关《费马定理、欧拉定理、威尔逊定理(讲稿).doc（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、欧拉定理、费马定理、威尔逊定理1、欧拉函数：(m)是1, 2, , m中与m互质的个数，称为欧拉函数.欧拉函数值的计算公式：若m, 则(m)m (1)(1)(1)例如，30235，则 若p为素数，则若p为合数，则不超过n且与n互质的所有正整数的与为；若 若设d为n的正约数，则不大于n且与n有最大公因数d的正整数个数为，同时；例1、证明：(n)n不可能成立.例2、证明：数列2n3中有一个无穷子数列，其中任意两项互质.例3、已知p为质数，在1, 2, , p中有多少个数与p互质？并求(p). 直接用性质例4 将与105互素的所有正整数从小到大排成数列，求出这个数列的第2010项.解：1105的所有

2、正整数中共有个与105互素，他们从小到排列为：. 对于任一的，由带余除法存在唯一的q, r使得 ，由(an，105)1，可得(r，105)1，即.反之，对于任意固定非负整数q, 有(105qr，105)1，于是105qr 都是数列的项，从而存在正整数n，使得. 因此数列仅由的数由小到大排列而成的.因为201048*4142，所以有.2、(欧拉定理) 若(a, m)1，则a(m)1(mod m).证明：设r1，r2，r(m)是模m的简化剩余系，又(a, m)1，ar1，ar2，ar(m)是模m的简化剩余系，ar1ar2ar(m)r1r2r(m)(mod m)，又(r1r2r(m), m)1，a(

3、m)1(mod m).注：这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题.应用：设(a, m)1, c是使得ac1(mod m)的最小正整数, 则c|(m).2、(定义1) 设m1是一个固定的整数, a是与m互质的整数，则存在整数k (1km)，使ak1(mod m)，我们称具有这一性质的最小正整数(仍记为k)称为a模m的阶，由a模m的阶的定义，可得如下性质： 设(a, m)1，k是a模m的阶，u, v是任意整数，则auav (mod m)的充要条件是uv (mod k)，特别地，au1 (mod m)的充要条件是k|u证明：充分性显然.必要性：设，

4、由及知.用带余除法，故，由的定义知，必须，所以 设(a, m)1，k是a模m的阶，则数列a, a2, , ak, ak1,是模m的周期数列，最小正周期为k，而k个数a, a2, ak 模m互不同余. 设(a, m)1，k是a模m的阶，则k|(m)，特别地，若m是素数p，则a模p的阶整除p1.(4) 设(a, p)1, 则d0是a对于模p的阶1(mod p), 且1, a, , ado1对模p两两不同余.特别地, do(p)1, a, a(p)1构成模p的一个简化剩余系.定理：若为对模的阶，为某一正整数，满足，则必为的倍数.例5、设a与m都是正整数，a1. 证明：证明：实上，显然互素，且的阶是m

5、，所以由模阶的性质导出例6：设m, a, b都是正整数，m1，则(证明：记由于(a, b)|a及(a, b)|b，易知及，故， 另一方面设m模d的阶是k，则由推出，k|a及k|b，故k|(a，b). 因此综合两方面可知，证毕.3、(费尔马小定理) 若p是素数，则apa(mod p) 若另上条件(a，p)1，则ap11(mod p)证明：设为质数，若是的倍数，则.若不是的倍数，则由欧拉定理得：，由此即得.4、(威尔逊定理) p为质数 (p1)!1 (mod p)证明：充分性：若p为质数，当p2，3时成立，当p3时，令x1, 2, 3, , p1，则，在中，必然有一个数除以余1，这是因为则好是的一

6、个剩余系去0. 从而对，使得； 若，则，这不可能.故对于不同的，有.即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，或.除外，别的数可两两配对，积除以余1.故.必要性：若(p1)!1 (mod p)，假设p不是质数，则p有真约数d1，故(p1)!1 (mod d)，另一方面，dp，故d|(p1)!，从而(p1)!0 (mod d)，矛盾！ p为质数.5、算术基本定理：任何一个大于1的整数都可以分解成质数的乘积. 如果不考虑这些质因子的次序，则这种分解法是唯一的. 即对任一整数n1，有n，其中p1p2pk均为素数，a1、a2、ak都是正整数.正整数d是

7、n的约数 d，(0ii, i1, 2, , k) 由乘法原理可得：n的正约数的个数为r(n)(a11)(a21)(ak1) n的正约数的与为S(n)(1p1)(1p2)(1pk) n的正约数的积为T(n) n为平方数的充要条件是：r(n)为奇数.(2) 判断质数的方法：设n是大于2的整数，如果不大于的质数都不是n的因子，则n是质数.(3) n!的标准分解：设p是不大于n的质数，则n!中含质数p的最高次幂为： 从而可以写出n!的标准分解式.例7、证明：当质数p7时，240|p41.例8、求被17除所得的余数.解：因为所以由费马小定理得故所以被17除所得的余数是14.变式拓展：已知a为正整数，a2

8、，且(a, 10)1，求a20的末两位数字.解：(a, 10)1，a为奇数，a20a(25)1(mod 25)，又a21(mod 4) a201(mod 4)，又(25, 4)1，a201(mod 100)，a20的末两位数字01.例9、证明：方程无整数解.解：若y是偶数，则8 |，x23(mod 8)不可能. 故必有y一定是奇数，从而x是偶数. 令x2s，y2t1得, 知t是偶数，令t2j，代入得s21j(16j212j3) 由(16j212j3)3(mod 4) 知存在4k3型的奇素数p，使得p|(16j212j3)，从而p | s21，即s21(mod p)，有(s，p)1, (mod

9、p)，于是 1(mod p)与费尔马小定理矛盾.例10、 试证：对于每一个素数p，总存在无穷多个正整数n，使得p|2nn.证明：若p2，则n为偶数时结论成立.若p2，则(2，p)1，由费尔马小定理2 p11(mod p)，故对于任意m，有2 m(p1)1(mod p).2 m(p1)m(p1)1m (mod p)，令1m0(mod p)，即mkp1，则对于nm(p1)(kp1)(p1)(kN*)，均有2 nn被p整除例11、设a, b为正整数，对任意的自然数n有，则ab.证明：假设a 与b不相等. 考虑n1有，则ab.设p是一个大于b的素数，设n是满足条件的正整数：由孙子定理这样的n是存在的，

10、如 n(a1)(p1)1.由费马定理所以也即，所以，矛盾.例12、设p是奇素数，证明：2 p1的任一素因了具有形式是正整数.证明：设q是2 p1的任一素因子，则q2. 设2模q的阶是k，则由知k|p，故k1或p (因p是素数，这是能确定阶k的主要因素).显然k1，否则这不可能，因此kp.由费马小定理推出因p、q都是奇数，故q12px(x是个正整数).例13、设是大于5的素数, 求证：在数列1, 11, 111, 中有无穷多项是的倍数.证明： 因是素数, 故由费马小定理故对每一个正整数有 而 因 故例14、证明：若则这里是奇素数.证明：因是奇素数，故由费马定理得，于是，故可由已知条件得故存在整数

11、使得 因此例15、(2004第36届加拿大奥林匹克) 设p是奇质数，试证：例16、(第44届IMO) 设p是质数，试证：存在一个质数q，使对任意整数n，数npp不是q的倍数.例17、已知p是给定的质数，求最大正整数m满足：1mp1；.例18、(2006国家集训队测试题) 求所有的正整数对(a, n)，使得n|(a1)nan课外练习题：1、证明：f (x)x5x3x是一个整值多项式. 求证：f (n)n5n2n1被3除余2.则只需证是15的倍数即可. 由3，5是素数及Fetmat小定理得，则；而(3，5)1，故，即是15的倍数, 所以是整数.2、 证明：2730|n13n (nN*)3、 已知有正整数.证明：由于，设(a, b)d，则d2|a2b2，显然d2|ab，由得，d2|ab于是abd2，d，即 (a, b).4、求最小的正整数k，使得存在非负整数m，n满足k19m5n5、将与105互素的所有正整数从大到小排列，试求出这个数列的第1000项；法一：由105=357；故不超过105而与105互质的正整数有105(1)(1)(1)=48个. 1000=4820488， 10520=2100. 而在不超过105的与105互质的数中第40个数是86 所求数为2186.法二：6设为正整数，具有性质：等式对所有的正整数成立.证明：，其中是某个整数.第 6 页