欧拉函数第八讲

1、 第八讲:欧拉函数 71 第八讲:欧拉函数 由欧拉函数而引发的欧拉定理及其推论(费马小定理)是初等数论中的两个重要定理,与它们有关的问题是数学竞赛中出现频率十分高的一类问题. 欧拉函数:定义:小于m且与m互素的正整数的个数叫做欧拉函数,记作(m);性质:若(a,b)=1,则(ab)=(a)(b);若d1,d2,dk是正整数m的所有正约数,则=m;公式:若p是素数,则(pk)=pk-pk-1(kN+),特别地,(p)=p-1;若m=(pi为质数,i为正整数,i=1,2,k),则(m)=m(1-)(1-)(1-); 欧拉定理:若m2,(a,m)=1,则1(modm);若r是使得ar1(modm)成

2、立的最小正整数,则r|(m); 费马定理:若p为质数,且(a,p)=1,则ap-11(modp);若p为质数,对任意整数a,apa(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,

3、是模m的一个既约剩余系;设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m2x+m1y历遍模m1m2的既约剩余系; 阶数原根:定义:设m1,(a,m)=1,使得ax1(modm)成立的最小正整数x称为a关于模m的阶数(或指数),并用ordm(a)表示;若ordm(a)=(m),则a叫做模m的一个原根;阶数性质:ordm(a)|xax1(modm);ordm(a)|(m);若ax1(modm),ay1(modm),则a(x,y)1(modm);原根定理:若p是奇素数,则模p的原根存在; 幂羞整除:若p是奇素数,整数a,b满足:(b,p)=1,ab,且存在正整数m,和非

4、负整数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=npmbn-1+;由(b,p)=1,pk|npm+k|npmbn-1;故只须证pm+k+1|Cnipmiibn-i,注意到Cnipmi=Cn-1i-1pmi=npm,由是整数,且P|pm+k+1|Cnipmipm+k+1|Cnipmiibn-I; 质因性质:如果正整数a、b满足:(a,b)=1,则a2+b2的质因子都是4k+1的形式. 证明:用反证法,假设p=4k-1是a2+b2的质因子,由(a,b)=1a、b不能同时被p整除;若

5、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年第四届中国西部数学奥林匹克试题)设nN+,用d(n)表示n的所有正约数的个数,(n)表示1,2,n中与n互质的数的个数.求

6、所有的非负整数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,且ABC=N;由于1,2,n中恰有一个数1AB,所以,d(n)+(n)+|C|=n+1d(n)+(n)n+1,故c=0或1;当c=0时,由d(n)+(n)=n|C|=1,知1,2,n中恰好有一个不属于AB.如果n为偶数,且n8,则n-2,n-4都不属于AB,此时n不满足方程.如果n为奇数,当n为质数或1时,d(

7、n)+(n)=n+1(属于情形);当n为合数时,设n=pq,10.求证:n或者是素数,或者是2的某个正整数次幂.解:因为(1,n)=(n-1,n)=1,且ai+1aia1=1,ak=n-1;令a2-a1=d0;当a2=2时,d=1ai=i(i=1,2,k)k=n-11,2,n-1均与n互素n是素数;当a2=3时,d=2ai=2i-1(i=1,2,k)2k-1=n-1n=2k1,3,2k-1均与n=2k互素n是2的某个正整数次幂;当a23时,首先证明:a2不是合数;否则,设a2=pq(p1,q1),由(a2,n)=1(pq,n)=1(p,n)=1,(q,n)=1在p,q应为a1,a2,ak中的某

8、两个,但pa2,q3素数3与n不互素3|n;因存在正整数m.使得ak=1+mdn-1=1+mdn=2+md3d;由a2=1+d,3a23(1+d)d1(mod3)3|(1+2d);如果1+2dnk=2,a2=1+d=n-1,即与互素的只有1,n-1(n)=2;设n=(pi为质数,i为正整数,i=1,2,k),则(n)=n(1-)(1-)(1-)=2(p1-1)(p2-1)(pk-1)=2p1=3,1=1,n=3,或p1=2,1=2,n=4,均与a23矛盾.2.(2006年伊朗国家队选拔考试试题)设p是一个素数,求所有的正整数n,使得p|(n),且对所有满足(a,n)=1的a,有n|(-1).解

9、:设n=(pi为质数,i为正整数,i=1,2,k),则(n)=n(1-)(1-)(1-)=(p1-1)(p2-1)(pk-1);所以,p|(n)存在某个pi=p,或存在某个pi满足p|(pi-1);又因对所有满足(a,n)=1的a,n|(-1)|(-1)(i=1,2,k);由(a,n)=1(a,)=1,由欧拉定理知1(mod)|(-1),所以,|(-1)()|(i=1,2,k);下面分情况讨论:至少有两个pi,pj满足p|(pi-1),p|(pj-1),则由()=(pi-1),()=(pj-1)N+,N+=()|(i=1,2,k),这样的n满足条件;恰有一个pi满足p|(pi-1),设pt|(

10、)(tN+);若pn,则pt-1|,与()|矛盾,故这样的不存在;若p|n,不妨设p1=p;(i)若12,则N+,N+()|(i=1,2,k),这样的n满足条件;(ii)若1=1,则pt-1|,与()|矛盾,故这样的不存在;不存在pi满足p|(pi-1),则p|n,不妨设p1=p,则|()|,与()|矛盾,故这样的不存在.3.(2005年第36届奥地利数学奥林匹克试题)设f是定义在0,1,2005上的函数,取值于非负整数,对任意定义域的变量x,都有f(2x+1)=f(2x),f(3x+1)=f(3x),f(5x+1)=f(5x).问:这个函数最多能取到多少个函数值？解:因对任意定义域的变量x,

11、都有f(2x+1)=f(2x),f(3x+1)=f(3x),f(5x+1)=f(5x)对任意x0,1,2005,当且仅当x能被2,3,5整除时,f(x+1)=f(x);为使函数值最多,应当(x,30)=1时,f(x+1)f(x);由(30)=(2)(3)(5)=(2-1)(3-1)(5-1)=8,2005=3066+250,1,2005中与30互素的数有668+7=535个,可得535个函数值,因此,最多能取到535+1=536个函数值. (1988年加拿大国家队选拔考试试题)序列Sn构造如下:S1=1,1,S2=1,2,1,S3=1,3,2,3,1,一般地,若Sk=a1,a2,an,则Sk+

12、1=a1,a1+a2,a2,a2+a3,an-1+an,an.在S1988中有多少项等于1988？ 第八讲:欧拉函数 73 解:由序列Sn的构造知,Sn中每两个相邻的数互素,并且较大的数等于它左右两个相邻数的和;首先证明引理:当n2时,每一对不大于n的互素数ab,在S2,S3,Sn中恰有两次相邻;因为Sk每个中的数都关于数2对称,故只须证明:a和b在2的左边恰有一次相邻;用数学归纳法证明:当n=2时,ban=2a=2,b=1,1和2在S2=1,2,1中2的左边恰有一次相邻;假设对n-1(n-12)时,结论成立;只考虑的左边:若an,则a,b在Sn中不相邻,否则,若a,b在Sn中相邻,则a-b,

13、b在Sn-1中相邻;又由归纳假设,a,b在Sn-1中相邻a-b,b在Sn-2中相邻,这样a-b,b均在Sn-1,Sn-2中相邻,即在2的左边至少相邻两次,矛盾;于是,a,b在S2,S3,Sn中与S2,S3,Sn-1中均相邻一次;若a=n,则由a-b,b在S2,S3,Sn-1中仅相邻一次a-b,b在S2,S3,Sn中也仅相邻一次,于是对于n,结论成立; 现观察Sn中n的个数,n是Sn中的较大数,这些n的左邻与右邻均小于n,且它们之和为n;由引理知,n的左邻与右邻的个数=2(n)Sn中n的个数=(n);本题答案(1988)=(4771)=(4)(7)(71)=(22-2)(7-1)(71-1)=8

14、40. (2006年第45届国际数学奥林匹克预选题)己知x(0,1),令y(0,1),且y的小数点后第n位数字是x的小数点后第2n位数字.证明:若x是有理数,则y也是有理数.解:由x是有理数x从小数点后的某位开始具有周期性,设周期长度d=2uv,其中,u是非负整数,v是奇数,则(2,v)=1,由欧拉定理知,1(modv)对每个正整数n,2n2n(modv);又因当nu时,2u0(mod2u)2n(modd)当n足够大时,x的小数点后第(v)+n位数字与第n位数字相同y从小数点后的某位开始以(v)为周期y是有理数. 2.费马定理:例2:(2012年全国高中数学联赛试题B卷)己知素数p满足下列条件

15、:存在正整数n,u,v,使n的正约数个数等于pu,且这pu个正约数之和等于pv,求p的一切可能值.解析:设n=(pi为质数,i为正整数,i=1,2,m),则(1+1)(2+1)(m+1)=pu,(1+p1+p12+)(1+p2+p22+)(1+pm+pm2+)=pv;因为p是素数,由知,存在sN+,使得1+1=ps,因此,1+p1+p12+=,由该式中的与均为整数,由知,存在tN+,使得=ptp|(p1p-1)(p1p-1)0(modp)p1p1(modp);由费马小定理知:p1pp1(modp)p11(modp);设p1=kp+1,kN+,则pt=Cp0(kp)p-1+Cp1(kp)p-2+

16、Cpp-2kp+Cpp-1;当p3时,Cp0(kp)p-1,Cp1(kp)p-2,Cpp-2kp均能被p2整除,但Cpp-1=p不能被p2整除Cp0(kp)p-1+Cp1(kp)p-2+Cpp-2kp+Cpp-1=p(pa+1)(aN+)pt=p(pa+1)pt-1=pa+1p|1,矛盾;当p=2时,由pt=2t=2t=p1+1p1=2t-1,令p1=1,p2=3,p3=7,n=21是满足条件的解.综上,p=2是满足条件的唯一素数.练习2:1.(1988年第届莫斯科数学奥林匹克试题)证明:当素数p7时,p4-1能被240整除.解:因240=2435;由p4-1=(p-1)(p+1)(p2+1)

17、;由素数p7p为奇数p-1,p+1,p2+1均为偶数;又因p-1与p+1是连续的偶数p-1与p+1中恰有一个是4的倍数24|(p4-1);因(3,p)=1,由费马小定理得p21(mod3)3|(p2-1)3|(p4-1);因(5,p)=1,由费马小定理得p41(mod5)5|(p4-1);又因24,3,5两两互素240=2435|(p4-1). (1990年年国家集训队培训题)求出所有小于10的正整数M,使得5整除1989M+M1989解:因1989M=(3985-1)M(-1)M(mod5);若M=5,则1989M+M1989=(19895+51989)19895(-1)5(-1)(mod5

18、),不满足条件;若M5,由1M9(M,5)=1,由费马小定理得M1989M(mod5)1989M+M1989(-1)M+M0(mod5);(i)当M为奇数时,5|(M-1)M=1;(ii)当M为偶数时,5|(M+1)M=4.综上,M=1,4.2.(2004年加拿大数学奥林匹克试题)设p是奇质数,证明:(modp2). 74 第八讲:欧拉函数 解:因为p-1是偶数,故=;由二项式定理得(p-k)2p-1=C2p-11p(-k)2p-2+(-k)2p-1(2p-1)p(-k)2p-2-k2p-1(modp2)k2p-1+(p-k)2p-1(2p-1)p(-k)2p-2(2p2-p)k2p-2-pk

19、2p-2(modp2);对1kp-1(k,p)=1,由费马小定理得kp-11(modp)k2p-21(modp)p|(k2p-2-1)-pk2p-2=-p(k2p-2-1)-p-p(modp2)=-p-p+p2(modp2). (1993年国家集训队选拔考试试题)对素数p3,定义F(p)=,f(p)=-,这里x=x-x表示x的小数部分.求f(p)的值.解:作120除以p-1的带余除法:120=q(p-1)+r,0rp-2;因素数p3p是奇数p-1是偶数,又120是偶数r是偶数;定义G(p)=,对k=1,2,(k,p)=1,由费马小定理:kp-11(modp)k120=kq(p-1)+r=(kp

20、-1)qkrkr(modp)F(p)G(p)(modp)f(p)=-=-;以下分两种情况讨论:当r=0时,G(p)=f(p)=-=-=;由r=0(p-1)|120p=3,5,7,11,13,31,41,61;当r0时,由r是偶数,G(p)=1r+2r+()r(p-1)r+(p-2)r+(p-)r(p-1)r+(p-2)r+()r(modp)2G(p)=G(p)+(p)(modp);又因同余方程xr1(modp)的互不同余的解不超过r个(0rp-2),所以至少存在一个a1,2,p-1,使得ar1(modp)2arG(P)=ar=2G(p)(modp)(这是因为a,2a,(p-1)a对于摸p两两不

21、同余,构成模p的剩余系)2(ar-1)G(p)0(modp)G(p)0(modp)=0f(p)=.综上,当p=3,5,7,11,13,31,41,61时,f(p)=;当素数p为其它奇素数时,f(p)=.3.(第20届韩国数学奥林匹克试题)试求所有的素数对(p,q),使得pq|(pp+qq+1).解:显然质数pq,不妨设p2时,则p与q均为奇素数;由pq|(pp+qq+1)q|(pp+1)q|(p+1)(pp-1-pp-2+-p+1)(若q|(p+1),则由pq,由(p,q-1)=1,由裴蜀定理,存在正整数u、v,使u(q-1)-vp=1;显然质数p、q都不为5,由费马小定理得5q-11(mod

22、q),2q-11(modq)5q-12q-1(modq)5u(q-1)2u(q-1)(modq)5vp+12vp+1(modq)5(5vp-2vp)+32vp0(modq),注意到q|(5p-2p)5p2p(modq)5vp2vp(modq)(5vp-2vp)(modq)32vp0(modq)q|32vp,矛盾. 3.活用费马:例3:(2003年第44届国际数学奥林匹克(IMO)试题)设p是质数,证明:存在一个质数q,使得对任意整数n,数np-p不 第八讲:欧拉函数 75 是q的倍数.解析:由于=1+p+p2+pp-1(p+1)(modp2),则中至少有一个质因子q,满足q对p2的模不等于1;

23、下面证明q为所求;假设存在整数n,使得npp(modq),则由q的选取,有pp1(modq);另一方面,由费马小定理,有nq-11(modq)(由于q为质数,且(n,q)=1),由于p2(q-1),有(p2,q-1)|p,因此,np1(modq),从而p1(modq),这则导出p+p2+pp-1p(modq),由q的选取,有p1(modq),矛盾.所以,命题成立.注:此题是第44届IMO中第二天的压轴题,是本次竞赛中难度最大的一道试题;其困难之处在于寻求一个合适的质数q,只需将其取为pp-1的一个恰当的质因子;当年参赛的中国队的6名国家队员中仅有2人解出了此题,本题的难度由此可见.由此可见,灵

24、活选取素数为摸是有力使用费马小定理的关键所在.练习3:1.(1988年加拿大数学奥林匹克试题)设整数k不能被5整除,证明:x5-x+k不能写成两个次数较低的整系数多项式的乘积.解:对x5-x+k的分解有两种可能:x5-x+k=(x+a)(x4+bx3+cx2+dx+e)(a,b,c,d,eZ)(-a)5-(-a)+k=0k=a5-a;由费马小定理a5a(mod5)5|(a5-a)=k,矛盾;x5-x+k=(x2+ax+b)(x3+cx2+dx+e)(a,b,c,d,eZ)x5-x+k=x5+(a+c)x4+(ac+b+d)x3+(ad+bc+e)x2+(ae+bd)x+bea+c=0,ac+b

25、+d=0,ad+bc+e=0,ae+bd=-1,be=kc=-a,d=a2-b,e=a(b-d)=a(2b-a2)a2(2b-a2)+b(a2-b)=-13a2b+1=a4+b2,k=be=ab(2b-a2)=2ab2-a3b=2a(3a2b+1-a4)-a3b=5a3b-2(a5-a)5|k,矛盾. (2009年第24届中国数学奥林匹克试题)求所有的素数对(p,q),使得pq|(5p+5q).解:若2|pq,不妨设p=2,则2q|(52+5q)q|(5q+25);由Fermat小定理q|(5q-5)q|30q=2,3,5,验证素数对(2,2)不合要求,(2,3),(2,5)合要求;若pq为奇

26、数,且5|pq,不妨设p=5,则5q|(55+5q)q|(5q-1+625);当q=5时素数对(5,5)合要求;当q5时,由Fermat小定理有q|(5q-1-1)q|626=2313q=313,经检验素数对(5,313)合要求;若p,q都不等于2和5,则由pq|(5p+5q)pq|5(5p-1+5q-1)pq|(5p-1+5q-1)p|(5p-1+5q-1)=(5p-1-1)+(5q-1+1)p|(5q-1+1);设p-1=2m(2a-1),q-1=2n(2b-1),其中m,n,a,b为正整数;若mn,则1(5q-1)2a-1(-1)2a-1-1(modp)p=2,矛盾;若mn,同理可得,矛

27、盾.综上,所有满足题目要求的素数对(p,q)为(2,3),(3,2),(2,5),(5,2),(5,5),(5,313),(313,5).2.(2005年国家集训队培训题)求所有的整系数多项式f(x),使得对所有正整数n,都有f(n)|(2n-1).解:如果f(x)不为常数,不妨设f(x)的首项系数为正,则存在正整数N,使得当nN时,f(n)2,取f(n)的一个质因子p,由f(n)|(2n-1)p|(2n-1)(2n-1)0(modp)2n1(modp);又由f(n+p)f(n)0(modp),及f(n+p)|(2n+p-1)p|(2n+p-1)2n+p1(modp)2n+p2n(modp)2

28、p1(modp);但由费马小定理2p2(modp),矛盾.所以,f(x)为常数,由f(1)|(21-1)=1f(1)=1f(x)=1. (1979年保加利亚数学奥林匹克试题)证明:方程x2+5=y3没有正整数解.解:当x为奇数时,x2+51+52(mod4)y32(mod4)y为偶数y30(mod4),矛盾;当x为偶数时,设x=2n(nN+),由y3=x2+551(mod4),设y=4m+1(mN+),则4n2+5=y34(n2+1)=(y-1)(y2+y+1)=4m(16m2+12m+3)n2+1=md,其中,d=16m2+12m+3-1(mod4)d中存在4k-1型的质因数p(否则,d中质

29、因数均是4k+11(mod4)质因数d1(mod4),矛盾),设p=4k-1,则n2+10(modp)n2-1(modp)np-1=n4k-2=(n2)2k-1(-1)2k-1-1(modp);另一方面,由n2-1(modp)(n,p)=1,由费马小定理np-11(modp),矛盾.综上,方程x2+5=y3没有正整数解.3.(第18届亚太地区数学奥林匹克试题)己知p(p5)为素数,从pp的棋盘上任取p个方格使,得所取方格不能位于同一行(可以位于同一列),记这样的取法数为r.求证:p5|r.解:在p2个方格中,任取p个,有种取法,其中位于同一行的有p种情况(p行),故r=-p;所以,p5|rp5

30、|(-p)P5|-pp4|-1p4|(p2-1)(p2-2)(p2-p+1)-(p-1)！(p2-1)(p2-2)(p2-p+1)-(p-1)！0(modp4);令f(x)=(x-1)(x-2)(x-p+1)=xp-1+ap-2xp-2+a1x+a0,其中a0=(p-1)！,则 76 第八讲:欧拉函数 (p2-1)(p2-2)(p2-p+1)-(p-1)！0(modp4)f(p2)-a00(modp4)a1p20(modp4)a10(modp2);由费马小定理: xp-11(modp)(由威尔逊定理知a0=(p-1)！-1(modp);又因p|x(x-1)(x-2)(x-p+1)xp-1-1(

31、x-1)(x-2)(x-p+1)(modp),比较两边的系数可得p|ai(1ip-2);又因a0=f(0)=(-1)p-1(p-1)！=(p-1)！=f(p)=pp-1+ap-2pp-2+a1p+a0a1p=-(pp-1+ap-2pp-2+a2p2)0(modp3)a10(modp2). 4.欧拉定理:例4:(1978年第20届国际数学奥林匹克(IMO)试题)数1978n与1978m的最后三位数相等,试求出正整数m和n,使得m+n取最小值(这里nm解析:数1978n与1978m的最后三位数相等1978n1978m(mod1000)1978n-m1(mod1000);注意到:(1000)=(23

32、53)=(23)(53)=(23-22)(53-52)=400,由欧拉定理知1978400=1971(mod1000)19781001(mod1000)n-m100;又由1978n1978m(mod1000)2n2m(mod8)2m(2n-m-1)0(mod8)2m0(mod8)m3n+m=(n-m)+2m100+23=106,当且仅当m=3,n=103时,等号成立.练习4:1.(1975年第17届国际数学奥林匹克(IMO)试题)设A是十进制数44444444的各位数码的和,B是A的各位数码的和,求B的各位数码的和(所有讨论的数都是在十进制数系中).解:用S(n)表示正整数在十进制中各位数码的

33、和,则S(n)n(mod9),本题的关键是反复利用同余式:S(n)n(mod9);注意到:(9)=32-3=6=444461(mod9)44444444(9493+7)6740+476740+474(9266+7)7(mod9)B的各位数码的和BA444444447(mod9);又因44444444(104)444444444444至多为44444=17776位数A917776=159984A至多为6位数B69=54B至多为2位数B的各位数码的和4+9=13B的各位数码的和=7. (2005年德国数学奥林匹克试题)设Q(n)表示正整数n的各位数字之和.证明:Q(Q(Q(20052005)=7.

34、解:显然Q(n)n(mod9),而20052005=(9222+7)200572005(mod9),注意到:(9)=32-3=6=761(mod9)72005=76334+17(mod9)Q(Q(Q(20052005)Q(Q(20052005)Q(20052005)200520057(mod9);又因20052005(104)2005=10802020052005至多为8020位数Q(20052005)98020=72180Q(20052005)至多为5位数Q(Q(20052005)95=45Q(Q(Q(20052005)3+9=12Q(Q(Q(20052005)=7.2.(2005年国家集训

35、队测试试题)设a0,a1,an,x0,x1,xn(n2)均为整数,r(r2)为整数,满足=0,k=1,2,r.证明:对正整数mr+1,r+2,2r+1,都有0(modm).解:设p|m,其中,p是质数,1,则由(p)=p-p-1(p)|(m-);由r+1rrp-1;若对任意xj(j=0,1,2,n),有p|xj,则由mxjmxj0(modp)0(modp);又因对任意p|m,上式均成立0(modm);若存在j,有pxj,则由(p)|(m-)1(modp)xjmxj0(modp)0(modp);又因对任意p|m,上式均成立0(modm).3.(1991年国家集训队测试试题)设d,a,n为正整数,

36、且3d2n+1.求证:d(+1).解:反证:假设d|(+1)d|(+1)(-1)d|(-1),显然有(a,d)=1;考虑以d为模的数列ak(modd),因=akak(modd)数列ak(modd)是周期数列,且2n+1是其的一个周期;设Tn(d)是该数列的最小正周期,则Tn(d)|2n+1;又由(a,d)=11(modd)ak(modd)(d)是其的一个周期Tn(d)|(d)Tn(d)|(2n+1,(d);又由(d)d-1和已知d2n+1(d)1)为奇数,m的最小素因子为p,m=pk(kN+),因p3(否则3|mn|(3m+1),矛盾)p5;由费马小定理3p-11(modp);又由p|mn|(

37、3m+1)3m-1(modp)32m1(modp)32pk1(modp);又由(p-1,2pk)=2321(modp)80(modp),矛盾;当m=1时,由n|(31+1)n=1,2,4,但n=4,不满足4|(34+1)(m,n)=(1,1),(1,2),(2,1). (2006年国家集训队测试试题)求所有的正整数对(a,n),使得是整数.解:当n=1时,正整数对(a,n)=(a,1)均满足条件;当n1时,设(a+1)n-an=kn(kN+),由(a,a+1)=1(a,n)=(a+1,n)=1,由欧拉定理(a+11(modn);又由(a+1)n-an=kn(a+1)n-an0(modn)(a+

38、1)nan(modn);令(n,(n)=d,则(a+1)dad(modn)(a+1)dad(modd)(a,d)是其一解,注意到d(n)n2=dn3,这是一个无穷递降的正整数数列,而这是不存在的.故所有的正整数对(a,1).2.(1985年第26届国际数学奥林匹克预选题)设k2,n1,n2,nk为正整数,满足n2|(-1),n3|(-1),nk|(-1),n1|(-1).证明:n1=n2=nk=1.解:设p是质数,由费马小定理得2p-11(modp);设(n,p-1)=d,如果2n1(modp)(n1),则2d1(modp)n的最小素因数q(n)dp-11,则由n1|(-1)-1n112nk1

39、nk-11n21;由n2|(-1)q(n2)|(-1q(n2)q(n1),同理可得:q(n3)q(n2),q(n1)q(nk)q(n1)q(n1),矛盾.3.(2003年第16届韩国数学奥林匹克试题)设m是正整数,如果2m+1+1整除+1.证明:2m+1+1解:设p=2m+1+1,由p|(+1)-1(modp)(3,p)=1,且()21(modp)1(modp)3p-11(modp)ordp(3)=p-1;又由欧拉定理知1(modp)ordp(3)=(p-1)|(p)(p)p-1,又因(p)p-1(p)=p-1p是质数2m+1+1是质数. (2010年第23届韩国数学奥林匹克试题)对于质数p,

40、若存在无限多个正整数k,存在一个正整数数列n1,n2,nk满足:当i=1,2,k时,ni;当i=1,2,k时,-1是ni+1的倍数,且与ni+1互质,nk+1=n1,且对于k=1不成立.此时,称p是“漂亮质数”.证明:2不是漂亮质数,但所有奇质数是漂亮质数.解:显然ni3,且均为奇数;记n1n2n3的最小素因子为q,则q3,不妨设q|n2,则ordq(2)|(q-1)ordq(2)1);若b1,则由ab=1+b+bnab-1=b(1+b+bn-1)b|(ab-1),设p是b的最小质因子,则p|(ab-1)ordp(a)|b;由费马小定理知ordp(a)p-11).2.(第22届俄罗斯数学奥林匹

41、克试题)设正整数x、y、p、n、k满足xn+yn=pk.证明:若n是大于1的奇数,p为奇质数,则n可以表示为p的正整数指数幂.解:因n为奇数,则(x+y)|(xn+ym);由xn+yn=pk(x+y)|pk,设x+y=pr(1rk),ps|n,则pr+s|xn-(-y)n=xn+yn=pkr+s=k;假若n=psq(q是大于1的奇数,(p,q)=1),则pk=xn+yn=()q+()q,又由ps|n,及x+y=prpr+s|-=(+)pk|(+)pk(+)()q+()q=pk,矛盾n=ps.3.(2000年第41届国际数学奥林匹克(IMO)试题)是否存在一个恰好为2000个不同质数整除的正整数

42、N,使得:N|(2N+1)？解:将题中的2000加强为任意正整数m,并对m归纳构造奇数N:当m=1时,则N1=3满足条件;假设命题对m成立,即存在Nm=,使得Nm|(+1);设|(+1),由(+1,-1)=1|(-1)|(-1)对任意正整数k,有|(-1)=(+1)(-1),而(+1,-1)=1|(+1);对足够大的k,总可以使得3),存在恰有m个不同质数乘积的正整数Nm,使得Nm|(-1); 首先证明引理:a-1中存在质因数p,使得ap-1中存在不同于p的质因数q;设p|(a-1),由p|pp+1|(ap-1),设a-1=tp,则a=tp+1ap-1=(tp+1)p-1p+1ap-1中存在不

43、同于p的质因数q; 回到本题,对m归纳:当m=1时,则取a-1的一个质因数p,令N1=p,由p|(a-1)p|(ap-1)N1|(-1);假设命题对m成立,即存在Nm=p1p2pm,使得Nm|(-1),令Nm+1=Nmpm+1,其中,pm+1是不同于p1,p2,pm的质数,且满足pm+1(-1),且pm+1|(-1)(由引理知pm+1是存在的)Nmpm+1|(-1)Nm+1|(-1). 7.质因性质:例7:证明:存在无穷多个4k+1形的质数.解析:用反证法,假设只有有限个4k+1形的质数p1,p2,pn,令N=(2p1p2pn)2+1,由(2p1p2pn,1)=1N的所有质因数均为4k+1的形

44、式,设其中之一为q,则q不同于p1,p2,pn(否则,设q=pk,则由pk|N=(2p1p2pn)2+1pk|1,矛盾),而这与假设矛盾. 第八讲:欧拉函数 79 练习7:1.(2009年马其顿数学奥林匹克试题)在整数集里,求x2010-2006=4y2009+4y2008+2007y的解.解:由x2010-2006=4y2009+4y2008+2007yx2010+1=4y2009+4y2008+2007y+2007x2010+1=(y+1)(4y2008+2007),由4y2008+2007-1(mod4)4y2008+2007中必含有4k-1型的质因数(否则,所有质因数均为4k+1的形式

45、4y2008+20071(mod4),矛盾),又由(x,1)=1x2010+1的所有质因数均为4k+1的形式,矛盾,所以,在整数集里,方程的解集为空集. (第22届伊朗数学奥林匹克试题)求所有的质数p、q、r,使得p3=p2+q2+r2成立.解:由p3=p2+q2+r2p2(p-1)=q2+r2;若p能整除q、r之一,不妨设p|q,则由p|(q2+r2)p|rp=q=rp=q=r=3;若p不能整除q、r之一,则(p,q)=(p,r)=1(q,r)=1(否则,q=rp2(p-1)=2q2p|2q2p|2p=2q2=2,矛盾)q2+r2=p2(p-1)的所有质因数均为4k+1的形式p为4k+1的形

46、式,p-1为4k+1的形式,矛盾.2.(2003年匈牙利数学奥林匹克试题)设n是大于2的整数,an是最大的n位数,且既不是两个完全平方数的和,又不是两个完全平方数的差.()求an(表示成n的函数);()求n的最小值,使得an的各位数字的平方和是一个完全平方数.解:()n位数中的最大数为10n-1=9=(+)(-)=()2-()2;而为奇数,所以,10n-1可表示为两个完全平方数的差,不合题意;n位数中的次大数为10n-2,下面证明an=10n-2:因n210n-2-22(mod4);但两个完全平方数的差对摸4的余数为0,1,3;两个完全平方数的和对摸4的余数为0,1,2,且当两个完全平方数的和

47、对摸4的余数为2时,这两个数均为奇数这两个数的平方和对摸8的余数为2,但10n-2-26(mod8);()由an=10n-2an的各位数字的平方和=92(n-1)+82=81(n-1)+64,设81(n-1)+64=k2,则81(n-1)=(k-8)(k+8)34|(k-8)(k+8)81|(k-8),或81|(k+8);若81|(k-8),则k89nmin=98;若81|(k+8),则k73nmin=66.综上,nmin=66.3.(1974年第35届美国普特南大学生数学竞赛试题)根据下面的定理:一个素数p2,当且仅当p1(mod4)时,能写成两个完全平方数的和.求出那些素数,使之能写为下列两种形式之一:x2+16y2;4x2+4xy+5y2.这里x与y是整数,但不一定是正的.解:如果p1(mod4),则p1(mod8),或p5(mod8);且p=m2+n2,p为奇素数m、n一奇一偶,不妨设m21(m