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

数学奥赛辅导 第一讲

奇数、偶数、质数、合数

知识、方法、技能

Ⅰ.整数的奇偶性

将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为2m（m∈Z），任一奇数可表为2m+1或2m－1的形式.奇、偶数具有如下性质：

（1）奇数±奇数=偶数；偶数±偶数=偶数；

奇数±偶数=奇数；偶数×偶数=偶数；

奇数×偶数=偶数；奇数×奇数=奇数；

（2）奇数的平方都可表为8m+1形式，偶数的平方都可表为8m或8m+4的形式（m∈Z）.

（3）任何一个正整数n，都可以写成n 2l的形式，其中m为非负整数，l为奇数. 这些性质既简单又明显，然而它却能解决数学竞赛中一些难题.

Ⅱ.质数与合数、算术基本定理

大于1的整数按它具有因数的情况又可分为质数与合数两类.

一个大于1的整数，如果除了1和它自身以外没有其他正因子，则称此数为质数或素数，否则，称为合数.

显然，1既不是质数也不是合数；2是最小的且是惟一的偶质数.

定理：（正整数的惟一分解定理，又叫算术基本定理）任何大于1的整数A都可以分解成质数的乘积，若不计这些质数的次序，则这种质因子分解表示式是惟一的，进而A可以写成标准分解式：

aaaA p11 p22 pnn （*）. m

其中p1 p2 pn,pi为质数， i为非负整数，i=1，2， ，n.

【略证】由于A为一有限正整数，显然A经过有限次分解可分解成若干个质数的乘积，把相同的质因子归类整理可得如（*）的形式（严格论证可由归纳法证明）.余下只需证惟一性.

设另有A q1 1 q22 qnm,其中q1 q2 qm,qj为质数， i为非负整数，j=1，

2， ，m.由于任何一pi必为qj中之一，而任一qj也必居pi中之一，故n=m.又因 p1 p2 pn,q1 q2 qn,则有pi qi(i 1,2, ,n)，再者，若对某个i， i i（不妨设 i i），用pii除等式p12p21 pnn p11 p22 pnn两端得：

n 1p1 pi i i pn p11 pi 1 i 1 aaa pi 1 i 1 n pn.

此式显然不成立（因左端是pi的倍数，而右端不是）.故 i i对一切i=1，2， ，n均成立.惟一性得证.

推论：（合数的因子个数计算公式）若A p11p22 pnn为标准分解式，则A的所有因子（包括1和A本身）的个数等于( 1 1)( 2 1) ( n 1).（简记为

( i 1ni 1)） 222这是因为，乘积(1 p1 p1 p11) (1 p2 p2 p22) (1 pn pn

n

pn)的每一项都是A的一个因子，故共有 ( i 1)个. n

i 1

定理：质数的个数是无穷的.

【证明】假定质数的个数只有有限多个p1,p2, pn,考察整数a p1p2 pn 1.由于a 1且又不能被pi(i 1,2, ,n)除尽，于是由算术基本定理知，a必能写成一些质数的乘积，而这些质数必异于pi(i 1,2, ,n)，这与假定矛盾.故质数有无穷多个.

赛题精讲

例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为奇数，0 a b c d,并且ad bc，证明：如果a+d=2k，b+c=2m，

k,m为整数，那么a=1. （第25届IMO试题）

【证明】首先易证：2 2.从而k m(因为d a b c,于是(a d)2 (a d)2 4ad km

(b c)2 4bc (b c)2.再由ad bc,d 2k a,c 2m b可得b 2m a 2k b2 a2, 因而2m(b a 2k m) (b a)(b a) ①

显然，b a,b a为偶数，b 2k ma为奇数，并且b a和b a只能一个为4n型 偶数，一个为4n+2型偶数（否则它们的差应为4的倍数，然而它们的差等于2a不是4 的倍数），

因此,如果设b 2k ma e f，其中e,f为奇数，那么由①式及b a,b a的特性就有

b a 2（Ⅰ） e,或（Ⅱ） b a 2f, m 1 b a 2e. b a 2f.m 1

由ef b 2k ma b 2a b a 2f 得e=1，

从而f b 2k ma.于是（Ⅰ）或（Ⅱ）分别变为

m 1k m b a 2, b a 2(b 2a), 或 k mm 1 b a 2(b 2a) b a 2

解之，得a 2k m 1 2m 1.因a为奇数，故只能a=1.

例3．设a1,a2, ,an是一组数，它们中的每一个都取1或－1，而且a1a2a3a4+a2a3a4a5+

+ana1a2a3=0，证明：n必须是4的倍数. （第26届IMO预选题）

【证明】由于每个ai均为1和－1，从而题中所给的等式中每一项aiai 1ai 2ai 3也只取1或－1，而这样的n项之和等于0，则取1或－1的个数必相等，因而n必须是偶数，设n=2m. 再进一步考察已知等式左端n项之乘积=(a1a2 an)4=1，这说明，这n项中取－1的项（共m项）也一定是偶数，即m=2k，从而n是4的倍数.

例4．如n是不小于3的自然数，以f(n)表示不是n的因数的最小自然数[例如f(n)=5].如

果f(n)≥3，又可作f(f(n)).类似地，如果f(f(n))≥3，又可作f(f(f(n)))等等.如果f(f(f f(n) )) 2，就把k叫做n的“长度”.如果用ln表示n的长度，试对任意的自然数n（n≥3），求ln，并证明你的结论.

（第3届全国中学生数学冬令营试题）

m【解】令n 2t,m为非负整数，t为奇数. 当m=0时，f(n) f(t) 2，因而ln=1；

当m 0时，设u是不能整除奇数t的最小奇数，记u g(t).

（1）若g(t) 2m 1,则f(n) u,f(f(n)) 2,所以ln 2.

（2）若g(t) 2m 1,则f(n) 2m 1,f(f(n)) f(2m 1) 3,f(f(f(n))) f(3) 2,所以ln 3.

1,当n为奇数时;

mm 1故ln 3,当n 2t,m 0,t为奇数,且g(t) 2(g(t)如上);

2,其他情形.

例5．设n是正整数，k是不小于2的整数.试证：n可表示成n个相继奇数的和.

【证明】对k用数学归纳法.

当k=2时，因n2 1 3 (2n 1),命题在立.

假设k=m时成立，即nm (a 1) (a 3) (a 2n 1) na n2,（a为某非负数） 则nm 1 nm n (na n2)n n(na n2 n) n2,

若记b na n n（显然b为非负偶数），于是 2k

nm 1 nb n2 (b 1) (b 3) (b 2n 1),即k m 1时，命题成立，故命题得证.

例6．在平面上任画一条所有顶点都是格点的闭折线，并且各节的长相等.能使这闭折线的节

数为奇数？证明你的结论. （莫斯科数学竞赛试题）

【解】令符合题设条件的闭折线为A1A2 AnA1，则所有顶点Ai的坐标（xi,yi）符 合xi,yi Z(i 1,2, ,n).并且Xi2 Yi2 C(i 1,2, n,C为一固定的正整数），其中 Xi xi xi 1,Yi yi yi 1(i 1,2, ,n,xn 1 x1,yn 1 y1),则由已知有

X

i 1

nni 0, ① Y

i 1i 0, ②

22X12 Y12 X2 Y22 Xn Yn2 ③

不妨设Xi和Yi中至少有一个为奇数（因为设Xi 2ti,m是指数最小的，ti为奇数，用2m除所有的数后，其商仍满足①、②、③式），于是它们的平方和C只能为4k+1或4k+2. m

当C=4k+2时，由③知，所有数对Xi与Yi都必须是奇数，因此，根据①、②式知，n必为偶数.

当C=4k+1时，由③知，所有数对Xi与Yi都必一奇一偶，而由①知，Xi中为奇数的有偶数个（设为2u），余下的n－2u个为偶数（与之对应的Yi必为奇数），再由②知，这种奇数的Yi也应有偶数个（设为2 n 2u），故n 2(u )=偶数.

综上所述，不能作出满足题设条件而有奇数个节的闭折线.

例7．求出最小正整数n，使其恰有144个不同的正因数，且其中有10个连续整数.

（第26届IMO预选题）

【解】根据题目要求，n是10个连续整数积的倍数，因而必然能被2，3， ，10整数.由于8=23，9=32，10=2×5，故其标准分解式中，至少含有23·32·5·7的因式，因此，若设 n 2 1 3 2 5 3 7 4 11 5 , 则 1 3, 2 2, 3 1, 4 1.由

( 1 1)( 2 1)( 3 1)( 4 1) 144,而( 1 1)( 2 1)( 3 1)( 4 1) 4 3 2 2 48,故最多还有一个 j 0(j 5),且 j 2,为使n最小，自然宜取2 5 0.由

( 1 1)( 2 1)( 3 1)( 4 1)( 5 1) 144( 5 0时)或( 1 1)( 2 1)( 3 1)( 4 1) 144( 5 0时),考虑144的可能分解，并比较相应n的大小，可知合乎要求的（最小） 1 5, 2 2,

. 3 4 5 1,故所求的n 25 32 5 7 11 110880

下面讲一个在指定集合内的“合数”的问题.这种合数与通常的合数有区别，题中的“素元素”是指在该集合内的素数，也与通常的素数有区别.

例8．设n>2为给定的正整数，Vn kn 1,k N*.试证：存在一数r Vn,这个数可用不

只一种方式表示成数集Vn中素元素的乘积. （第19届IMO试题）

【证明】由于Vn中的数都不小于n 1(n 2),因而(n 1)2,(2n 1)2,(n 1) (2n 1) Vn. 显然(n 1)2,(n 1) (2n 1)是Vn中的素元素.又若（2n－1）2不是Vn中素元素，则有 a b 1,使(an 1) (bn 1) (2n 1)2,由此有4n 4 abn a b,于是1 ab 3,从而b=1,a=1;b=1,a=2,b=1,a=3,对此就有n 2,

中素元素.

当n 8时,令r (n 1)2(2n 1)2.显然r Vn,且r (n 1)2(2n 1)2 [(n 1)(2n 1)] 8,8,故n=8.这说明 ，当n 8时,(2n 1)2就是Vn2

[(n 1)(2n 1)].