资源描述：
《费马定理、欧拉定理、威尔逊定理(讲稿).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、欧拉定理、费马定理、威尔逊定理1、欧拉函数：φ(m)是1,2,…,m中与m互质的个数，称为欧拉函数.①欧拉函数值的计算公式：若m＝…,则φ(m)＝m(1－)(1－)…(1－)例如，30＝2·3·5，则②若p为素数，则若p为合数，则③不超过n且与n互质的所有正整数的和为；④若若⑤设d为n的正约数，则不大于n且与n有最大公因数d的正整数个数为，同时；例1、证明：φ(n)＝n不可能成立.例2、证明：数列{2n－3}中有一个无穷子数列，其中任意两项互质.例3、已知p为质数，在1,2,…,pα中有多少个数与pα互质？并求φ(pα).直接用性质②例4将与105互素的所有正整数从小
2、到大排成数列，求出这个数列的第2010项.解：1~105的所有正整数中共有个与105互素，他们从小到排列为：.对于任一的，由带余除法存在唯一的q,r使得，由(an，105)＝1，可得(r，105)＝1，即.反之，对于任意固定非负整数q,有(105q＋r，105)＝1，于是105q＋r都是数列的项，从而存在正整数n，使得.因此数列仅由的数由小到大排列而成的.因为2010＝48*41＋42，所以有.2、(欧拉定理)若(a,m)＝1，则aφ(m)≡1(modm).证明：设r1，r2，…，rφ(m)是模m的简化剩余系，又∵(a,m)＝1，∴a·r1，a·r2，…，a·rφ(m
3、)是模m的简化剩余系，∴a·r1×a·r2×…×a·rφ(m)≡r1×r2×…×rφ(m)(modm)，又∵(r1·r2·…·rφ(m),m)＝1，∴aφ(m)≡1(modm).注：这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题.应用：设(a,m)＝1,c是使得ac≡1(modm)的最小正整数,则c
4、φ(m).2、(定义1)设m＞1是一个固定的整数,a是与m互质的整数，则存在整数k(1≤k≤m)，使ak≡1(modm)，我们称具有这一性质的最小正整数(仍记为k)称为a模m的阶，由a模m的阶的定义，可得如下性质：⑴设(a,m)
5、＝1，k是a模m的阶，u,v是任意整数，则au≡av(modm)的充要条件是u≡v(modk)，特别地，au≡1(modm)的充要条件是k
6、u证明：充分性显然.必要性：设，由及知.用带余除法，故，∴，由的定义知，必须，所以⑵设(a,m)＝1，k是a模m的阶，则数列a,a2,…,ak,ak＋1,…是模m的周期数列，最小正周期为k，而k个数a,a2,…,ak模m互不同余.⑶设(a,m)＝1，k是a模m的阶，则k
7、φ(m)，特别地，若m是素数p，则a模p的阶整除p－1.(4)设(a,p)＝1,则d0是a对于模p的阶Û≡1(modp),且1,a,…,ado−1对模p两两不同余
8、.特别地,do＝φ(p)1,a,…,aφ(p)−1构成模p的一个简化剩余系.定理：若为对模的阶，为某一正整数，满足，则必为的倍数.例5、设a和m都是正整数，a＞1.证明：证明：实上，显然互素，且的阶是m，所以由模阶的性质③导出例6：设m,a,b都是正整数，m＞1，则(证明：记由于(a,b)
9、a及(a,b)
10、b，易知及，故，另一方面设m模d的阶是k，则由推出，k
11、a及k
12、b，故k
13、(a，b).因此综合两方面可知，证毕.3、(费尔马小定理)若p是素数，则ap≡a(modp)若另上条件(a，p)＝1，则ap−1≡1(modp)证明：设为质数，若是的倍数，则.若不是的倍数，则
14、由欧拉定理得：，，由此即得.4、(威尔逊定理)p为质数Û(p－1)!≡－1(modp)证明：充分性：若p为质数，当p＝2，3时成立，当p＞3时，令x∈{1,2,3,…,p−1}，则，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0. 从而对，使得； 若，，则，，这不可能.故对于不同的，有.即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，∴或.除外，别的数可两两配对，积除以余1.故.必要性：若(p－1)!≡－1(modp)，假设p不是质数，则p有真约数d＞1，故(p－1)!≡－1(modd)，另一方面，d＜p，故d
15、
16、(p－1)!，从而(p－1)!≡0(modd)，矛盾！∴p为质数.5、算术基本定理：任何一个大于1的整数都可以分解成质数的乘积.如果不考虑这些质因子的次序，则这种分解法是唯一的.即对任一整数n＞1，有n＝…，其中p1＜p2＜…＜pk均为素数，a1、a2、…、ak都是正整数.①正整数d是n的约数Ûd＝…，(0≤βi≤αi,i＝1,2,…,k)②由乘法原理可得：n的正约数的个数为r(n)＝(a1＋1)(a2＋1)…(ak＋1)③n的正约数的和为S(n)＝(1＋p1＋…＋)(1＋p2＋…＋)…(1＋pk＋…＋)④n的正约数的积为T(n)＝⑤n为平方数的充
