浙大高中数学竞赛培训PPT《数论》ppt课件 33页

数论试题中的概念和方法\n竞赛中常用的定理：欧拉定理费马小定理中国剩余定理……基本研究对象：整数涉及的范围：整除问题同余问题不定方程……\n1、已知a、b、c为正整数，且是有理数.求证：是整数.证明：因为为无理数，故b－c≠0，于是上式表示有理数，则有b2-ac=0.从而a2+b2+c2=(a+b+c)2-2ab-2bc-2ca=(a+b+c)2-2(ab+bc+b2)=(a+b+c)(a-b+c).故\n整除有如下的一些性质：①若a|b，b|c，则a|c；②若c|a，d|b，则cd|ab；③若c|a，c|b，则c|（ma＋nb）；④若a|b，则ma|mb，反之亦成立；⑤a、b互质，若a|c，b|c，则ab|c；⑥p为质数，若p|a1a2…an，则p必能整除a1，a2，…，an中的某一个；特别地，若p为质数，p|an，则p|a.\n2、证明：当n为任何整数时，36|(2n6–n4–n2).证明：2n6―n4―n2=n2(2n2＋1)(n2－1)，当n为偶数时，4|n2；当n为奇数时，n2被4除余数为1，故4|(n2－1).故4|n2(2n2＋1)(n2－1).当n＝3k（k∈Z）时，9|n2(2n2＋1)(n2－1)；当n＝3k±1（k∈Z）时，n2被3除余数总是1，所以3|(n2－1)，且2n2被3除余数为2，所以3|(2n2＋1)，于是9|(n2－1)(2n2＋1)，故9|n2(n2－1)(2n2＋1).所以36|(2n6–n4–n2).\n3、对任意正整数n，求证：(n+2)(12005+22005+…+n2005).分析：按底数之和为（n＋2）进行配对计算.k2005＋(n＋2－k)2005＝(n＋2)[k2004－k2003(n＋2－k)＋…+(n＋2－k)2004]，∴k2005＋(n＋2－k)2005能被n＋2整除（k＝2，3，…）.\n因式分解公式：对大于1的整数n有xn－yn=(x－y)(xn-1+xn-2y+xn-3y2+……+xyn-2+yn-1)；对大于1的奇数n有xn+yn=(x+y)(xn-1－xn-2y+xn-3y2－……－xyn-2+yn-1)；对大于1的偶数n有xn－yn=(x+y)(xn-1－xn-2y+xn-3y2－……+xyn-2－yn-1).\n同余问题定义:①设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同，则称a、b对模m同余，记为a≡b(modm).②若m|(a－b)，则称a、b对模m同余.③若a=b+mt(t∈Z)，则称a、b对模m同余.\n性质：①a≡a（modm）②若a≡b（modm），则b≡a（modm）③若a≡b（modm）,b≡c（modm）,则a≡c（modm）④若a≡b（modm）,c≡d（modm）,则a±c≡b±d（modm），ac≡bd（modm）,an≡bn（modm）⑤若n|m，a≡b（modm），则a≡b（modn）⑥若(m，n)＝1，a≡b（modm），a≡b（modn），则a≡b（modmn）\n⑦欧拉定理：若（a,m）=1，则⑧费尔马小定理：p是素数，则ap≡a（modp）若另上条件（a，p）＝1，则ap-1≡1（modp）⑨威尔逊定理：设p素数，则（p－1）！≡-1（modp）.\n4、一个数的各位数字的和被9除的余数等于这个数被9除的余数.证明设a==an×10n+an-1×10n-1+…+a1×10+a0，∵10≡1(mod9)，∴10n≡1(mod9)，∴an×10n+an-1×10n-1+…+a1×10+a0≡an+an-1+…+a1+a0(mod9)\n5、试求出一切可使被3整除的自然数.\n\n6、求除以13的余数.解：103≡－1（mod13）106≡1（mod13）102≡10≡10（mod6）103≡102≡10（mod6）10n≡10n-1≡…≡10≡4（mod6）10n＝6k＋4∴≡106k+4≡(106)k×104≡1k×104≡104≡3（mod13）\n不定方程不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.对于二元一次不定方程问题，我们有两个定理：①二元一次不定方程ax+by=c(a，b，c为整数)有整数解的充分必要条件是(a,b)|c.②若(a,b)=1，且x0，y0为上述方程的一组解，则方程的全部解为x=x0+bt，y=y0-at(t为整数).对于非二元一次不定方程问题，常用的求解方法有：①恒等变形;②构造法;③奇偶分析法;④不等式估计法.\n7、求满足方程2x2+5y2=11(xy－11)的正整数数组(x，y).(2x－y)(x－5y)=－112.8、求不定方程14x2－24xy+21y2+4x－12y－18=0的整数解.解原式变形为：2(x－3y+1)2+3(2x－y)2=20，故3(2x－y)2≤20，即平方数(2x－y)2≤4，当(2x－y)2=0，1时，(x－3y+1)2=10或2(x－3y+1)2=17，均不可能，故(2x－y)2=4，从而(x－3y+1)2=4，由此得方程有唯一整数解：（1，0）.\n证明由于2×5－1=32，2×13－1=52，5×13－1=82，因此，只需证明2d－1，5d－1，13d－1中至少有一个不是完全平方数.假设它们都是完全平方数，令2d－1=x2①5d－1=y2②13d－1=z2③x,y,z∈N*由①知，x是奇数，设x=2k－1，于是2d－1=(2k－1)2，即d=2k2－2k+1，这说明d也是奇数.因此，再由②，③知，y,z均是偶数.9、（第27届IMO试题）设正整数d不等于2，5，13.证明在集合｛2，5，13，d｝中可以找到两个元素a,b，使得ab－1不是完全平方数.反证法\n设y=2m，z=2n，代入②，③，相减，除以4得，2d=n2－m2=(n+m)(n－m)，从而n2－m2为偶数，n，m必同是偶数或同是奇数，于是m+n与m－n都是偶数，这样2d就是4的倍数，即d为偶数，这与上述d为奇数矛盾.故命题得证.2d－1=x2①5d－1=y2②13d－1=z2③d是奇数，y,z均是偶数\n解5×2m=n2－1=(n+1)(n-1)，其中n+1与n-1同为偶数，则n为奇数，设n=2k-1(k∈N+)，10、（2006澳大利亚数学奥林匹克）求所有的正整数m、n，使得1+5×2m=n2.所以5×2m=4k(k-1),即5×2m-2=k(k-1),故m≥2,k＞1，因k与k-1一奇一偶，故或或解得k=5，m=4，所以m=4，n=9满足条件.\n11、（2004年中国西部数学奥林匹克）求所有的整数n，使得n4+6n3+11n2+3n+31是完全平方数．解设A＝n4+6n3+11n2+3n+31是完全平方数，则配方后A＝(n2+3n+1)2―3(n―10)是完全平方数．当n=10时，A＝(102+3×10+1)2=1312是完全平方数.当n＞10时，A＜(n2+3n+1)2，所以A≤(n2+3n)2，∴A―(n2+3n)2＝(n2+3n+1)2―3(n―10)―(n2+3n)2≤0，即(n2+3n+1)2―(n2+3n)2≤3(n―10)，∴2n2+3n+31≤0，这不可能．\n于是A≥(n2+3n+2)2，化简得2n2+9n－27≤0，∴n=－6，－5，－4，－3，－2，－1，0，1，2，此时对应的A=409，166，67，40，37，34，31，52，145都不是完全平方数．A＝(n2+3n+1)2―3(n―10)当n＜10时，A＞(n2+3n+1)2，所以，只有当n=10时，A是完全平方数．\n(1)平方数的个位数字只可能是0，1，4，5，6，9；(2)偶数的平方数是4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余数只能是0或1；(3)奇数平方的十位数字是偶数；(4)十位数字是奇数的平方数的个位数一定是6；(5)不能被3整除的数的平方被3除余1，能被3整除的数的平方能被3整除，因而，平方数被9除的余数为0，1，4，7；(6)平方数的约数的个数为奇数；(7)任何四个连续整数的乘积加1，必定是一个平方数；(8)在两个相邻的整数的平方数之间的所有整数都不是完　　全平方数.完全平方数的性质\n算术基本定理：任何一个大于1的整数均可分解为素数　的乘积，若不考虑素数相乘的前后顺序，则分解式是惟一的．即大于1的整数a可以表示为：a=，其中i=l，2，…，s．为质数，为非负整数.d是a的正因数其中0≤βi≤αi，i=l，2，…，sa的正因数的个数为d(a)=(α1+1)(α2+1)…(αs+1)a的正因数的和\n12、（2003年泰国数学奥林匹克）求所有使p2+2543具有少于16个不同正因数的质数p.解当p=2时，p2+2543=2547=32×283，283是质数，此时共有正因数(2+1)×(1+1)=6个，满足条件；当p=3时，p2+2543=2552=23×11×19，此时共有正因数(3+1)×(1+1)×(1+1)=16个，不满足条件；当p＞3时，p2+2543=(p-1)(p+1)+2400+144，…(p-1)(p+1)是24的倍数，所以p2+2543是24的倍数，p2+2543=23+i×31+j×m，若m＞1，共有正因数(3+i+1)×(1+j+1)×(k+1)≥16个，若m=1，2i×3j＞106，当j＞1，正因数个数不少于16，当j=1，i＞4，正因数个数不少于24，当j=0，i＞5，正因数个数不少于18，所以p＞3不满足条件.综上所述，p≥2时，正因数个数至少有16个，而p=2时正因数个数为6，故所求的质数p是2.\n13、（2004土耳其数学奥林匹克）(1)对于每一个整数k=1,2,3，求一个整数n，使n2-k的正因数个数为10.(2)证明：对于所有整数n，n2-4的正因数个数不是10.(1)解：k=1,24×3+1=72k=2,74×23+2=2352k=3,374×13+3=49362\n(2)证明：假设存在n，使n2-4有10个因数.ⅰ若n2-4=p9(p为质数)，即(n-2)(n+2)=p9,令n-2=pi,n+2=pj(i4,所以无解.ⅱ若n2-4=p14p2，（p1,p2为质数，且p1≠p2），即(n-2)(n+2)=p14p2，当(n-2,n+2)=1时，①n-2=1，则n+2=5，无解.②n-2=p14，n+2=p2，则p2-p14=4.\n如果p1=5，则p2=629=17×37，矛盾.如果p1≠5，则p14≡1(mod5),p2≡p14+4≡0(mod5).故p2=5，p14=1无解.③n-2=p2,n+2=p14，则p14-p2=4，所以(p12-2)(p12+2)=p2所以，p12-2=1，p12=3，无解.当(n-2,n+2)>1时,又(n+2)-(n-2)=4，则p1=2，所以p2为奇数.故n2=16p2+4，所以2|n.设n=2m，则m2=4p2+1≡5(mod8)，矛盾.因此，不存在整数n，使得n2-4的正因数个数是10.\n14、（2006澳大利亚数学奥林匹克）对于任意正整数n，设a(n)是n的各位数的乘积.(1)证明：对所有正整数n，有n≥a(n)；(2)求所有的n，使得n2-17n+56=a(n)成立.(1)证明令则(2)解由n2-17n+56=a(n),及a(n)≤n得n2-17n+56≤n，即n2-18n+56≤0，解得4≤n≤14.又由n2-17n+56≥0,得n≤4,或n≥13,则n∈｛4,13,14｝逐一检验得n＝4.\n15、（2005德国数学奥林匹克）设Q(n)表示正整数n的各位数字之和，证明：Q(Q(Q(20052005)))=7.证明因为Q(n)≡n(mod9)，而20052005≡(9×222+7)2005≡72005(mod9)，由欧拉定理所以20052005≡72005=76×334+1(mod9)≡7(mod9)，故Q(Q(Q(20052005)))≡20052005≡7(mod9).又20052005＜(104)2005=108020，所以，20052005至多有8020位，故Q(20052005)≤9×8020=72180于是Q(20052005)至多只有5位，因此Q(Q(20052005))≤9×5=45,从而Q(Q(Q(20052005)))≤3+9=12,又Q(Q(Q(20052005)))≡7(mod9)，所以Q(Q(Q(20052005)))＝7.\n16、(2004年西部数学奥林匹克)设n∈N*，用d(n)表示n的所有正约数的个数，φ(n)表示1，2，…，n中与n互质的数的个数．求所有的非负整数c，使得存在正整数n，满足d(n)＋φ(n)＝n＋c，并且对这样的每一个c，求出所有满足上式的正整数n.分析d(n)表示n的所有正约数的个数，φ(n)是1，2，…，n中与n互质的数的个数，两类数中的公共部分只有1，如果1，2，…，n中的数恰好是大于1的正约数与第二类中大于1的某数的乘积，该数不在这两类数中，把这种数称为第三类数.当没有第三类数时．c=1；当有1个第三类数时．c=0；当第三类数的个数大于1时．c＜0.\n17、(2004-2005匈牙利数学奥林匹克)已知n是正整数，如果存在整数a1,a2,…,an（不一定是不同的），使得a1+a2+…+an=a1a2…an=n，则称n是“迷人的”.求迷人的整数.解：若k=4t+1,t∈N，显然满足要求，取4t+1及2t个1，2t个-1即可.若k=4，则a1a2a3a4=4，只可能a4=4或a4=a3=2，显然无解.若k=4t，t≥2，分两种情况讨论.当t为奇数时，取2t，-2，x个1，y个-1（x，y待定）.则x+y=4t-2，x-y+2t-2=4t.解得x=3t，y=t-2.显然这样一组数满足题设要求.\n当t为偶数时，类似地取2t，2，x个1，y个-1，则x+y=4t-2，x-y=2t-2.解得x=3t-2，y=t.这一组数比满足题设要求.综上，4t(t≥2)型数是迷人的.下面证明4t+2，4t+3型数是不迷人的.若4t+2型数是迷人的，设4t+2=a1+a2+…+a4t+2=a1a2…a4t+2.易知，ai中有且仅有一个偶数，其余4t+1个数均为奇数，故a1+a2+…+a4t+2必为奇数，矛盾.因此4t+2型数是不迷人的.\n若4t+3型数是迷人的，设4t+3=a1+a2+…+a4t+3=a1a2…a4t+3.其中模4余1的有x个，模4余3的有4t+3-x个.故x+3(4t+3-x)≡3（mod4），所以2x≡2（mod4），于是x是奇数，4t+3-x为偶数，则3≡4t+3≡1x×34t+3-x≡1（mod4），矛盾.因此4t+3型数是不迷人的.综上所述，全部的迷人数为4t+1，t∈N；4t，t≥2的类型.