浙大高中数学竞赛培训PPT《数论》

数论试题中的概念和方法竞赛中常用的定理：欧拉定理费马小定理中国剩余定理……基本研究对象：整数涉及的范围：整除问题同余问题不定方程……1、已知a、b、c为正整数，且是有理数.求证：是整数.33abbc222abcabc证明：因为为无理数，故b－c≠0，于是33222223(3)(3)33()333ababbcabbcbacbcbcbc222.abcabcZabc上式表示有理数，则有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).故整除有如下的一些性质：①若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.2、证明：当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).3、对任意正整数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，…）.因式分解公式：对大于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).同余问题定义:①设m是一个给定的正整数.如果两个整数a、b用m除所得的余数相同，则称a、b对模m同余，记为a≡b(modm).②若m|(a－b)，则称a、b对模m同余.③若a=b+mt(t∈Z)，则称a、b对模m同余.性质：①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）⑦欧拉定理：若（a,m）=1，则⑧费尔马小定理：p是素数，则ap≡a（modp）若另上条件（a，p）＝1，则ap-1≡1（modp）⑨威尔逊定理：设p素数，则（p－1）！≡-1（modp）.()1(mod)mam4、一个数的各位数字的和被9除的余数等于这个数被9除的余数.证明设a=110nnaaaa=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)5、试求出一切可使被3整除的自然数.21nnnn6136233|n21n22(mod3)261(012)2(61)2(122)(31)2(mod3)62(012)2(62)2(248)(31)2(mod3)nnkknkknnkknkknkknkk解：若，则考虑到及，则当时，、、、当时，、、、6364363(012)2(63)20(mod3)64(012)2(64)2(9664)(31)1(mod3)nknkknkknknkknkk当时，、、、当时，、、、6536665(012)2(65)2(632160)(31)1(mod3)66(012)2(66)20(mod3)616223nkknknnkknkknkknknkkn当时，、、、当时，、、、由上可知当且仅当，时，+1能被整除；1010n6、求除以13的余数.1010n解：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）1010n不定方程不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.对于二元一次不定方程问题，我们有两个定理：①二元一次不定方程ax+by=c(a，b，c为整数)有整数解的充分必要条件是(a,b)|c.②若(a,b)=1，且x0，y0为上述方程的一组解，则方程的全部解为x=x0+bt，y=y0-at(t为整数).对于非二元一次不定方程问题，常用的求解方法有：①恒等变形;②构造法;③奇偶分析法;④不等式估计法.7、求满足方程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）.证明由于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不是完全平方数.反证法设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均是偶数解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一奇一偶，故252,11,mkk25,12,mkk22,15,mkk或或解得k=5，m=4，所以m=4，n=9满足条件.11、（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，这不可能．于是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，3(333)3(333)73,44n所以，只有当n=10时，A是完全平方数．(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)在两个相邻的整数的平方数之间的所有整数都不是完全平方数.完全平方数的性质1212iSiSpppp……12,nippppi算术基本定理：任何一个大于1的整数均可分解为素数的乘积，若不考虑素数相乘的前后顺序，则分解式是惟一的．即大于1的整数a可以表示为：a=，其中i=l，2，…，s．为质数，为非负整数.d是a的正因数1212iSiSdpppp……其中0≤βi≤αi，i=l，2，…，sa的正因数的个数为d(a)=(α1+1)(α2+1)…(αs+1)a的正因数的和1111()(1)1iinniiiiipappp12、（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.13、（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(2)证明：假设存在n，使n2-4有10个因数.ⅰ若n2-4=p9(p为质数)，即(n-2)(n+2)=p9,令n-2=pi,n+2=pj(ij),则pj-pi=4.①当i=0时，p9=5无解.②当i≥1时，p|4，故p=2.又25-244,所以无解.ⅱ若n2-4=p14p2，（p1,p2为质数，且p1≠p2），即(n-2)(n+2)=p14p2，当(n-2,n+2)=1时，①n-2=1