数学奥赛辅导第一讲 奇数、偶数、质数、合数

1数学奥赛辅导第一讲奇数、偶数、质数、合数知识、方法、技能I．整数的奇偶性将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数。因此，任一偶数可表为2m（m∈Z），任一奇数可表为2m+1或2m－1的形式。奇、偶数具有如下性质：（1）奇数±奇数=偶数；偶数±偶数=偶数；奇数±偶数=奇数；偶数×偶数=偶数；奇数×偶数=偶数；奇数×奇数=奇数；（2）奇数的平方都可表为8m+1形式，偶数的平方都可表为8m或8m+4的形式（m∈Z）。（3）任何一个正整数n，都可以写成lnm2的形式，其中m为非负整数，l为奇数。这些性质既简单又明显，然而它却能解决数学竞赛中一些难题。Ⅱ.质数与合数、算术基本定理大于1的整数按它具有因数的情况又可分为质数与合数两类。一个大于1的整数，如果除了1和它自身以外没有其他正因子，则称此数为质数或素数，否则，称为合数。显然，1既不是质数也不是合数；2是最小的且是惟一的偶质数。定理：（正整数的惟一分解定理，又叫算术基本定理）任何大于1的整数A都可以分解成质数的乘积，若不计这些质数的次序，则这种质因子分解表示式是惟一的，进而A可以写成标准分解式：nanaapppA2121（*）。其中inpppp,21为质数，i为非负整数，i=1，2，…，n。【略证】由于A为一有限正整数，显然A经过有限次分解可分解成若干个质数的乘积，把相同的质因子归类整理可得如（*）的形式（严格论证可由归纳法证明）。余下只需证惟一性。2设另有jmnqqqqqqqAm,,212121其中为质数，i为非负整数，j=1，2，…，m。由于任何一ip必为jq中之一，而任一jq也必居ip中之一，故n=m。又因),,2,1(,,2121niqpqqqpppiinn则有，再者，若对某个i，ii（不妨设ii），用iip除等式nnnanaapppppp21122121两端得：.11111111niiniiniinippppppp此式显然不成立（因左端是ip的倍数，而右端不是）。故ii对一切i=1，2，…，n均成立。惟一性得证。推论：（合数的因子个数计算公式）若nnpppA2121为标准分解式，则A的所有因子（包括1和A本身）的个数等于).1()1)(1(21n（简记为nii1)1(）这是因为，乘积2222212111()1()1(21nnpppppppp)nnp的每一项都是A的一个因子，故共有nii1)1(个。定理：质数的个数是无穷的。【证明】假定质数的个数只有有限多个,,,21nppp考察整数.121npppa由于1a且又不能被),,2,1(nipi除尽，于是由算术基本定理知，a必能写成一些质数的乘积，而这些质数必异于),,2,1(nipi，这与假定矛盾。故质数有无穷多个。3赛题精讲例1．设正整数d不等于2，5，13。证明在集合｛2，5，13，d｝中可以找到两个元素a，b，使得ab－1不是完全平方数。（第27届IMO试题）【解】由于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均是偶数。设y=2m，z=2n，代入③、④，相减，除以4得，2d=n2－m2=（n+m）（n－m），从而n2－m2为偶数，n，m必同是偶数，于是m+n与m－n都是偶数，这样2d就是4的倍数，即d为偶数，这与上述d为奇数矛盾。故命题得证。例2．设a、b、c、d为奇数，bcaddcba并且,0，证明：如果a+d=2k，b+c=2m，k，m为整数，那么a=1。（第25届IMO试题）【证明】首先易证：.22mk从而addadacbadmk4)()(,22于是（因为22)(4)(cbbccb。再由,222,2,22ababbcadbcadkmmk可得因而))(()2(2abababmkm①显然，abab,为偶数，abmk2为奇数，并且abab和只能一个为4n型偶数，一个为4n+2型偶数（否则它们的差应为4的倍数，然而它们的差等于2a不是4的倍数），因此，如果设feabmk2，其中e，f为奇数，那么由①式及abab,的特性就有（Ⅰ）.2,21fabeabm或（Ⅱ）.2,21eabfabm由fabababefmk222得e=1，从而.2abfmk于是（Ⅰ）或（Ⅱ）分别变为4)2(2,21abababmkm或12),2(2mmkababab解之，得1122mmka。因a为奇数，故只能a=1。例3．设naaa,,,21是一组数，它们中的每一个都取1或－1，而且a1a2a3a4+a2a3a4a5+…+ana1a2a3=0，证明：n必须是4的倍数。（第26届IMO预选题）【证明】由于每个ia均为1和－1，从而题中所给的等式中每一项321iiiiaaaa也只取1或－1，而这样的n项之和等于0，则取1或－1的个数必相等，因而n必须是偶数，设n=2m。再进一步考察已知等式左端n项之乘积=（naaa21）4=1，这说明，这n项中取－1的项（共m项）也一定是偶数，即m=2k，从而n是4的倍数。例4．如n是不小于3的自然数，以)(nf表示不是n的因数的最小自然数[例如)(nf=5]。如果)(nf≥3，又可作))((nff。类似地，如果))((nff≥3，又可作)))(((nfff等等。如果2)))(((nffff，就把k叫做n的“长度”。如果用nl表示n的长度，试对任意的自然数n（n≥3），求nl，并证明你的结论。（第3届全国中学生数学冬令营试题）【解】令mtnm,2为非负整数，t为奇数。当m=0时，2)()(tfnf，因而ln=1；当0m时，设u是不能整除奇数t的最小奇数，记).(tgu（1）若.2,2))((,)(,2)(1nmlnffunftg所以则（2）若.3,2)3()))(((,3)2())((,2)(,2)(111nmmmlfnffffnffnftg所以则故.,2);)((2)(,,0,2,3;,11其他情形如上且为奇数当为奇数时当tgtgtmtnnlmmn例5．设n是正整数，k是不小于2的整数。试证：kn可表示成n个相继奇数的和。5【证明】对k用数学归纳法。当k=2时，因),12(312nn命题在立。假设k=m时成立，即,)12()3()1(2nnanaaanm（a为某非负数）则,)()(2221nnnnannnnannnmm若记nnnab2（显然b为非负偶数），于是1),12()3()1(21mknbbbnnbnm即时，命题成立，故命题得证。例6．在平面上任画一条所有顶点都是格点的闭折线，并且各节的长相等。能使这闭折线的节数为奇数？证明你的结论。（莫斯科数学竞赛试题）【解】令符合题设条件的闭折线为A1A2…AnA1，则所有顶点iA的坐标（iiyx,）符合).,,2,1(,niZyxii并且CniCYXii,,2,1(22为一固定的正整数），其中),,,,,2,1(,111111yyxxniyyYxxXnniiiiii则由已知有niiX1,0①niiY1,0②2222222121nnYXYXYX③不妨设iiYX和中至少有一个为奇数（因为设mtXimi,2是指数最小的，ti为奇数，用2m除所有的数后，其商仍满足①、②、③式），于是它们的平方和C只能为4k+1或4k+2。当C=4k+2时，由③知，所有数对iiYX与都必须是奇数，因此，根据①、②式知，n必为偶数。当C=4k+1时，由③知，所有数对iiYX与都必一奇一偶，而由①知，Xi中为奇数的有6偶数个（设为2u），余下的n－2u个为偶数（与之对应的Yi必为奇数），再由②知，这种奇数的Yi也应有偶数个（设为un22），故)(2un=偶数。综上所述，不能作出满足题设条件而有奇数个节的闭折线。例7．求出最小正整数n，使其恰有144个不同的正因数，且其中有10个连续整数。（第26届IMO预选题）【解】根据题目要求，n是10个连续整数积的倍数，因而必然能被2，3，…，10整数。由于8=23，9=32，10=2×5，故其标准分解式中，至少含有23·32·5·7的因式，因此，若设,11753254321n则.1,1,2,34321由,144)1)(1)(1)(1(4321而,482234)1)(1)(1)(1(4321故最多还有一个,2),5(0jjj且为使n最小，自然宜取.025由)0(144)1)(1)(1)(1()0(144)1)(1)(1)(1)(1(54321554321时或时，考虑144的可能分解，并比较相应n的大小，可知合乎要求的（最小）,2,521,1543故所求的.11088011753225n下面讲一个在指定集合内的“合数”的问题。这种合数与通常的合数有区别，题中的“素元素”是指在该集合内的素数，也与通常的素数有区别。例8．设n2为给定的正整数，.,1*NkknVn试证：存在一数,nVr这个数可用不只一种方式表示成数集Vn中素元素的乘积。（第19届IMO试题）【证明】由于Vn中的数都不小于),2(1nn因而nVnnnn)12()1(,)12(,)1(22。显然)12()1(,)1(2nnn是Vn中的素元素。又若（2n－1）2不是Vn中素元素，则有,)12()1()1(,12nbnanba使由此有,44baabnn于是,31ab从而b=1，a=1;b=1，a=2，b=1，a=3，对此就有,8,28,2n故n=8。这说明，当2)12(,8nn时就是Vn中素元素。当)]12)(1[()12()1(,.)12()1(,82222nnnnrVrnnrnn且显然令时)].12)(1[(nn7当n=8时，有1089=136×8+1=9×121=33×33，而9，121，33∈V8。综上知，命题得证。例9．已知n≥2，求证：如果nkk2对于整数k（30nk）是质数，则nkk2对于所有整数)20(nkk都是质数。（第28届（1987）国际数学奥林匹克试题6）【证】设m是使nkk2为合数的最小正整数。若nmmpnmn2,23是令的最小质因子，则nmmp2。（1）若m≥p，则p|（m－p）2+（m－p）+n。又（m－p）2+（m－p）+n≥n＞p，这与m是使nkk2为合数的最小正整数矛盾。（2）若m≤p－1，则nmpmpnmpmp))(1()1()1(2被p整除，且.)1()1(2pnnmpmp因为nmpmp)1()1(2为合数，所以.12,1mpmmp由,122nmmpm即,01332nmm由此得363123nnm与已知矛盾。所以，对所有的nkknkn2,23为质数。