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

数学奥赛辅导 第一讲 奇数、偶数、质数、合数 知识、方法、技能 Ⅰ.整数的奇偶性 将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可为2m（m∈Z），任一奇数可表为2m+1或2m－1的形式.奇、偶数具有如下性质： （1）奇数±奇数=偶数；偶数±偶数=偶数； 奇数±偶数=奇数；偶数×偶数=偶数； 奇数×偶数=偶数；奇数×奇数=奇数； （2）奇数的平方都可表为8m+1形式，偶数的平方都可表为8m或8m+4的形式（m∈Z）. （3）任何一个正整数n，都可以写成 的形式，其中m为非负整数，l为奇数. 这些性质既简单又明显，然而它却能解决数学竞赛中一些难. Ⅱ.质数与合数、算术基本定理 大于1的整数按它具有因数的情况又可分为质数与合数两类. 一个大于1的整数，如果除了1和它自身以外没有其他正因子，则称此数为质数或素数，否则，称为合数. 显然，1既不是质数也不是合数；2是最小的且是惟一的偶质数. 定理：（正整数的惟一分解定理，又叫算术基本定理）任何大于1的整数A都可以分解成质数的乘积，若不计这些质数的次序，则这种质因子分解表示式是惟一的，进而A可以写成分解式： （*）. 其中 为质数， 为非负整数，i=1，2，…，n. 【略证】由于A为一有限正整数，显然A经过有限次分解可分解成若干个质数的乘积，把相同的质因子归类整理可得如（*）的形式（严格论证可由归纳法证明）.余下只需证惟一性. 设另有 为质数， 为非负整数，j=1，2，…，m.由于任何一 必为 中之一，而任一 也必居 中之一，故n=m.又因 ，再者，若对某个i， （不妨设 ），用 除等式 两端得： 此式显然不成立（因左端是 的倍数，而右端不是）.故 对一切i=1，2，…，n均成立.惟一性得证. 推论：（合数的因子个数计算公式）若 为标准分解式，则A的所有因子（包括1和A本身）的个数等于 （简记为 ） 这是因为，乘积 的每一项都是A的一个因子，故共有 个. 定理：质数的个数是无穷的. 【证明】假定质数的个数只有有限多个 考察整数 由于 且又不能被 除尽，于是由算术基本定理知，a必能写成一些质数的乘积，而这些质数必异于 ，这与假定矛盾.故质数有无穷多个. 赛题精讲 例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为奇数， ，证明：如果a+d=2k，b+c=2m，k,m为整数，那么a=1. （第25届IMO试题） 【证明】首先易证： 从而 .再由 因而 ① 显然， 为偶数， 为奇数，并且 只能一个为4n型 偶数，一个为4n+2型偶数（否则它们的差应为4的倍数，然而它们的差等于2a不是4 的倍数）， 因此,如果设 ，其中e,f为奇数，那么由①式及 的特性就有 （Ⅰ） 或（Ⅱ） 由 得e=1， 从而 于是（Ⅰ）或（Ⅱ）分别变为 或 解之，得 .因a为奇数，故只能a=1. 例3．设 是一组数，它们中的每一个都取1或－1，而且a1a2a3a4+a2a3a4a5+…+ana1a2a3=0，证明：n必须是4的倍数. （第26届IMO预选题） 【证明】由于每个 均为1和－1，从而题中所给的等式中每一项 也只取1或－1，而这样的n项之和等于0，则取1或－1的个数必相等，因而n必须是偶数，设n=2m. 再进一步考察已知等式左端n项之乘积=( )4=1，这说明，这n项中取－1的项（共m项）也一定是偶数，即m=2k，从而n是4的倍数. 例4．如n是不小于3的自然数，以 表示不是n的因数的最小自然数[例如 =5].如果 ≥3，又可作 .类似地，如果 ≥3，又可作 等等.如果 ，就把k叫做n的“长度”.如果用 表示n的长度，试对任意的自然数n（n≥3），求 ，并证明你的结论. （第3届全国中学生数学冬令营试题） 【解】令 为非负整数，t为奇数. 当m=0时， ，因而ln=1； 当 时，设u是不能整除奇数t的最小奇数，记 （1）若 （2）若 故 例5．设n是正整数，k是不小于2的整数.试证： 可表示成n个相继奇数的和. 【证明】对k用数学归纳法. 当k=2时，因 命题在立. 假设k=m时成立，即 （a为某非负数） 则 若记 （显然b为非负偶数），于是 时，命题成立，故命题得证. 例6．在平面上任画一条所有顶点都是格点的闭折线，并且各节的长相等.能使这闭折线的节数为奇数？证明你的结论. （莫斯科数学竞赛试题） 【解】令符合题设条件的闭折线为A1A2…AnA1，则所有顶点 的坐标（ ）符 合 并且 为一固定的正整数），其中 则由已知有 ① ② ③ 不妨设 中至少有一个为奇数（因为设 是指数最小的，ti为奇数，用2m除所有的数后，其商仍满足①、②、③式），于是它们的平方和C只能为4k+1或4k+2. 当C=4k+2时，由③知，所有数对 都必须是奇数，因此，根据①、②式知，n必为偶数. 当C=4k+1时，由③知，所有数对 都必一奇一偶，而由①知，Xi中为奇数的有偶数个（设为2u），余下的n－2u个为偶数（与之对应的Yi必为奇数），再由②知，这种奇数的Yi也应有偶数个（设为 ），故 =偶数. 综上所述，不能作出满足题设条件而有奇数个节的闭折线. 例7．求出最小正整数n，使其恰有144个不同的正因数，且其中有10个连续整数. （第26届IMO预选题） 【解】根据题目要求，n是10个连续整数积的倍数，因而必然能被2，3，…，10整数.由于8=23，9=32，10=2×5，故其标准分解式中，至少含有23·32·5·7的因式，因此，若设 则 由 而 故最多还有一个 为使n最小，自然宜取 由 ,考虑144的可能分解，并比较相应n的大小，可知合乎要求的（最小） 故所求的 下面讲一个在指定集合内的“合数”的问题.这种合数与通常的合数有区别，题中的“素元素”是指在该集合内的素数，也与通常的素数有区别. 例8．设n>2为给定的正整数， 试证：存在一数 这个数可用不只一种方式表示成数集Vn中素元素的乘积. （第19届IMO试题） 【证明】由于Vn中的数都不小于 因而 . 显然 是Vn中的素元素.又若（2n－1）2不是Vn中素元素，则有 由此有 于是 从而b=1,a=1;b=1,a=2,b=1,a=3,对此就有 故n=8.这说明 ，当 就是Vn中素元素. 当 当n=8时，有1089=136×8+1=9×121=33×33，而9，121，33∈V8. 综上知，命题得证. 例9．已知n≥2，求证：如果 对于整数k（ ）是质数，则 对于所有整数 都是质数. （第28届（1987）国际数学奥林匹克试题6） 【证】设m是使 为合数的最小正整数.若 的最小质因子，则 . （1）若m≥p，则p|(m－p)2+(m－p)+n. 又(m－p)2+(m－p)+n≥n＞p，这与m是使 为合数的最小正整数矛盾. （2）若m≤p－1，则 被p整除，且 因为 为合数，所以 由 即 由此得 与已知矛盾.所以，对所有的 为质数. 1 _1124023546.unknown _1124084856.unknown _1124090597.unknown _1124092031.unknown _1124094317.unknown _1124105058.unknown _1124105653.unknown _1124106169.unknown _1124106622.unknown _1124106710.unknown _1124106375.unknown _1124105891.unknown _1124105940.unknown _1124105665.unknown _1124105370.unknown _1124095153.unknown _1124095340.unknown _1124095408.unknown _1124095448.unknown _1124095783.unknown _1124095383.unknown _1124095324.unknown _1124094602.unknown _1124094943.unknown _1124094591.unknown _1124093684.unknown _1124094266.unknown _1124094301.unknown _1124093903.unknown _1124094233.unknown _1124092325.unknown _1124092473.unknown _1124092250.unknown _1124091434.unknown _1124091697.unknown _1124091840.unknown _1124091450.unknown _1124090926.unknown _1124091017.unknown _1124090726.unknown _1124087559.unknown _1124089433.unknown _1124090110.unknown _1124090576.unknown _1124089831.unknown _1124088928.unknown _1124089084.unknown _1124087717.unknown _1124087162.unknown _1124087486.unknown _1124087544.unknown _1124087285.unknown _1124086855.unknown _1124087145.unknown _1124086810.unknown _1124026271.unknown _1124080118.unknown _1124080351.unknown _1124081492.unknown _1124084708.unknown _1124081402.unknown _1124080236.unknown _1124080260.unknown _1124080172.unknown _1124026826.unknown _1124079918.unknown _1124079972.unknown _1124026949.unknown _1124026670.unknown _1124026761.unknown _1124026615.unknown _1124024338.unknown _1124024690.unknown _1124025398.unknown _1124025755.unknown _1124024888.unknown _1124024536.unknown _1124024575.unknown _1124024412.unknown _1124023704.unknown _1124024234.unknown _1124024271.unknown _1124023931.unknown _1124023678.unknown _1124023627.unknown _1124023665.unknown _1124018921.unknown _1124021213.unknown _1124023117.unknown _1124023416.unknown _1124023423.unknown _1124023295.unknown _1124021269.unknown _1124021352.unknown _1124021255.unknown _1124020694.unknown _1124021072.unknown _1124021179.unknown _1124021059.unknown _1124019626.unknown _1124020523.unknown _1124019607.unknown _1124017235.unknown _1124017805.unknown _1124017856.unknown _1124018836.unknown _1124017828.unknown _1124017543.unknown _1124017750.unknown _1124017258.unknown _1124014929.unknown _1124017073.unknown _1124017145.unknown _1124016954.unknown _1124014345.unknown _1124014446.unknown _1124013833.unknown