.欧拉函数.docVIP

第八讲:欧拉函数 71 第八讲:欧拉函数 由欧拉函数而引发的欧拉定理及其推论(费马小定理)是初等数论中的两个重要定理,与它们有关的问题是数学竞赛中出现频率十分高的一类问题. 欧拉函数:⑴定义:小于m且与m互素的正整数的个数叫做欧拉函数,记作(m);⑵性质:①若(a,b)=1,则(ab)= (a)(b);②若d1,d2,…,dk是正整数m的所有正约数,则=m;⑶公式:①若p是素数,则(pk)=pk-pk-1(k∈N+),特别地,(p)=p-1;②若m=(pi为质数,αi为正整数,i=1,2,…,k),则(m)=m(1-)(1-)…(1-); 欧拉定理:①若m≥2,(a,m)=1,则≡1(modm);若r是使得ar≡1(modm)成立的最小正整数,则r|(m); 费马定理:①若p为质数,且(a,p)=1,则ap-1≡1(modp);②若p为质数,对任意整数a,ap≡a(modp); 既约剩余:⑴定义:若m的剩余类Kr中的每一个数都与m互质,则称Kr为m的互质剩余类;在模m的全部互质剩余类中,从每一类中任取一个数所构成的数组,称为模m的一个既约(简化)剩余类;⑵性质:①Kr与模m互质Kr中有一个数与m互质;②与模m互质的剩余类的个数等于(m),即模m的一个既约剩余系由(m)个整数组成((m)为欧拉函数);③若(a,m)=1,则x与ax同时遍历模m的既约剩余系;④若a1,a2,…,aφ(m)是(m)个与m互质的整数,并且两两对模m不同余,则a1,a2,…,是模m的一个既约剩余系;⑤设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m2x+m1y历遍模m1m2的既约剩余系; 阶数原根:⑴定义:设m≥1,(a,m)=1,使得ax≡1(modm)成立的最小正整数x称为a关于模m的阶数(或指数),并用ordm(a)表示;若ordm(a)=(m),则a叫做模m的一个原根;⑵阶数性质:①ordm(a)|xax≡1(modm);②ordm(a)|(m);③若ax≡1(modm),ay≡1(modm),则a(x,y)≡1(modm);⑶原根定理:若p是奇素数,则模p的原根存在; 幂羞整除:若p是奇素数,整数a,b满足:(b,p)=1,a≠b,且存在正整数m,和非负整数k,使得pm||(a-b),pk||n,则pm+k||(an-bn). 证明:由pm||(a-b),设a-b=pmα(pa)a=pmα+ban-bn=(pmα+b)n-bn=npmαbn-1+;由(b,p)=1,pk||n pm+k||npmαbn-1;故只须证pm+k+1||Cnipmiαibn-i,注意到Cnipmi=Cn-1i-1pmi=npm,由是整数,且P| pm+k+1||Cnipmipm+k+1||Cnipmiαibn-I; 质因性质:如果正整数a、b满足:(a,b)=1,则a2+b2的质因子都是4k+1的形式. 证明:用反证法,假设p=4k-1是a2+b2的质因子,由(a,b)=1a、b不能同时被p整除;若a、b中恰有一个能被p整除,不妨设p|a,由p|(a2+b2)p|b2p|b,矛盾,故a、b都不能被p整除(a,p)=(b,p)=1,由费马小定理知:p|(ap-1-1), p|(bp-1-1)p|(ap-1-bp-1)=(a4k-2-b4k-2)(因p为奇数,由pbp2b4k-2)p[(a4k-2-b4k-2)+2b4k-2]=[(a2)2k-1+(b2)2k-1]=(a2+b2) (a4k-4-a4k-6b2+…-b4k-4)p(a2+b2),矛盾. 1.欧拉函数: [例1]:(2004年第四届中国西部数学奥林匹克试题)设n∈N+,用d(n)表示n的所有正约数的个数,φ(n)表示1,2,…,n中与n互质的数的个数.求所有的非负整数c,使得存在正整数n,满足d(n)+φ(n)=n+c,且对这样的每一个c,求出所有满足上式的正整数n. [解析]:设N={1,2,…,n},n的所有正约数组成的集合为A,1,2,…,n中与n互质的数组成的集合为B,1,2,…,n中与既不是n的约数又不与n互质的数组成的集合为C,则AN,BN,CN,且A∪B∪C=N;由于1,2,…,n中恰有一个数1∈A∩B,所以, d(n)+φ(n)+|C|=n+1d(n)+φ(n)≤n+1,故c=0或1;①当c=0时,由d(n)+φ(n)=n|C|=1,知1,2,…,n中恰好有一个不属于A∪B.如果n为偶数,且n8,则n-2,n-4都不属于A∪B,此时n不满足方程.如果n为奇数