《数学奥赛辅导_第一讲_奇数、偶数、质数、合数》由会员分享，可在线阅读，更多相关《数学奥赛辅导_第一讲_奇数、偶数、质数、合数（7页珍藏版）》请在金锄头文库上搜索。
1、1数学奥赛辅导 第一讲 奇数、偶数、质数、合数知识、方法、技能.整数的奇偶性将全体整数分为两类，凡是 2 的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为 2m（mZ） ，任一奇数可表为 2m+1 或 2m1 的形式.奇、偶数具有如下性质：（1）奇数奇数=偶数；偶数偶数=偶数；奇数偶数=奇数；偶数偶数=偶数；奇数偶数=偶数；奇数奇数=奇数；（2）奇数的平方都可表为 8m+1 形式，偶数的平方都可表为 8m 或 8m+4 的形式（mZ）.（3）任何一个正整数 n，都可以写成 的形式，其中 m 为非负整数，l 为奇数.lnm2这些性质既简单又明显，然而它却能解决数学竞赛中一些难题.质数与合数
2、、算术基本定理大于 1 的整数按它具有因数的情况又可分为质数与合数两类.一个大于 1 的整数，如果除了 1 和它自身以外没有其他正因子，则称此数为质数或素数，否则，称为合数.显然，1 既不是质数也不是合数；2 是最小的且是惟一的偶质数.定理：（正整数的惟一分解定理，又叫算术基本定理）任何大于 1 的整数 A 都可以分解成质数的乘积，若不计这些质数的次序，则这种质因子分解表示式是惟一的，进而 A 可以写成标准分解式：（*）.naapAL21其中 为质数， 为非负整数，i=1，2，n.inp,21【略证】由于 A 为一有限正整数，显然 A 经过有限次分解可分解成若干个质数的乘积，把相同的质因子归类
3、整理可得如（*）的形式（严格论证可由归纳法证明）.余下只需证惟一性.设另有 为质数， 为非负整数，jmn qqqm ,2121 LL其 中 ij=1， 2，m .由于任何一 必为 中之一，而任一 也必居 中之一，故 n=m.又因ipj jip，再者，若对某个),(,211 nipinnL则 有i， （不妨设 ） ，用 除等式 两端得：iiiii nnaapLL2112 2.1111 niini ppp LLL此式显然不成立（因左端是 的倍数，而右端不是）.故 对一切 i=1，2，n 均i ii成立.惟一性得证.推论：（合数的因子个数计算公式）若 为标准分解式，则 A 的所有npAL21因子（包
4、括 1 和 A 本身）的个数等于 （简记为 ）).()(21nnii1)(这是因为，乘积 222121( npppp LL的每一项都是 A 的一个因子，故共有 个.)npL nii1)(定理：质数的个数是无穷的.【证明】假定质数的个数只有有限多个 考察整数 由,21npL.121npaL于 且又不能被 除尽，于是由算术基本定理知，a 必能写成一些质数的1a),21(nipL乘积，而这些质数必异于 ，这与假定矛盾 .故质数有无穷多个.i赛题精讲例 1设正整数 d 不等于 2，5，13.证明在集合2，5，13，d中可以找到两个元素 a,b，使得 ab1 不是完全平方数. （第 27 届 IMO 试
5、题）【解】由于 251=3 2，2131=5 2，5131=8 2，因此，只需证明2d1，5d1，13d1 中至少有一个不是完全平方数.用反证法，假设它们都是完全平方数，令2d1=x 2 5d1=y 2 13d1=z 2 x,y,zN *由知，x 是奇数，设 x=2k 1，于是 2d1= （2k1） 2，即 d=2k22k+1，这说明 d 也是奇数.因此，再由，知，y,z 均是偶数.设 y=2m,z=2n,代入、，相减，除以 4 得，2d=n 2m 2=(n+m)(nm)，从而 n2m 2 为偶数，n，m 必同是偶数，于是 m+n 与 mn 都是偶数，这样 2d 就是 4 的倍数，即 d 为偶
6、数，这与上述 d 为奇数矛盾.故命题得证.例 2设 a、 b、 c、 d 为奇数， ，证明：如果bcacba并 且,03a+d=2k，b+c=2 m，k,m 为整数，那么 a=1. （第 25届 IMO 试题）【证明】首先易证： 从而.2mk addacbdk 4)(,( 22于 是因 为.再由22)(4)(cbcb ,2, babcadkmm可 得因而 )(amk显然， 为偶数， 为奇数，并且 只能一个为 4n 型,mk ab和偶数，一个为 4n+2 型偶数（否则它们的差应为 4 的倍数，然而它们的差等于 2a 不是 4的倍数） ，因此,如果设 ，其中 e,f 为奇数，那么由式及 的特性就有
7、feabmk2 ,（） 或（）.,1f.2,1eabfm由 得 e=1，fefmk从而 于是（）或（）分别变为.2ab或)(,1mk12),(mkba解之，得 .因 a 为奇数，故只能 a=1.12a例 3设 是一组数，它们中的每一个都取 1 或1，而且n,1La1a2a3a4+a2a3a4a5+ana1a2a3=0，证明：n 必须是 4 的倍数. （第 26 届IMO 预选题）【证明】由于每个 均为 1 和1，从而题中所给的等式中每一项 也只取i 321iia1 或1，而这样的 n 项之和等于 0，则取 1 或1 的个数必相等，因而 n 必须是偶数，设n=2m.再进一步考察已知等式左端 n
8、项之乘积=( )4=1，这说明，这 n 项中取1 的项naL21（共 m 项）也一定是偶数，即 m=2k，从而 n 是 4 的倍数 .例 4如 n 是不小于 3 的自然数，以 表示不是 n 的因数的最小自然数例如 =5.如)(f )(f果 3，又可作 .类似地，如果 3，又可作 等等.)(f(f )(f nf4如果 ，就把 k 叫做 n 的“长度”.如果用 表示 n 的长度，试2)(Lnff l对任意的自然数 n（n3） ，求 ，并证明你的结论.nl（第 3 届全国中学生数学冬令营试题）【解】令 为非负整数，t 为奇数. 当 m=0 时， ，因而m,2 2)(tfnfln=1；当 时，设 u
9、是不能整除奇数 t 的最小奇数，记0 ).(tgu（1）若 2,)(,)(,2)(1 nmlnfuftg所 以则（2）若 .3,)3(311 nmlffn 所 以则故 ., );(2)(,023;, 1其 他 情 形 如 上且为 奇 数当 为 奇 数 时当 tgtttlmn例 5设 n 是正整数，k 是不小于 2 的整数.试证： 可表示成 n 个相继奇数的和.k【证明】对 k 用数学归纳法.当 k=2 时，因 命题在立. ),1(312nL假设 k=m 时成立，即 （a 为某非,)12(32naam L负数） 则 ,)(21 nn若记 （显然 b 为非负偶数） ，于是ab2时，命题成立，故命1
10、),2()3(11 mkm 即L题得证.例 6在平面上任画一条所有顶点都是格点的闭折线，并且各节的长相等.能使这闭折线的节数为奇数？证明你的结论. （莫斯科数学竞赛试题）【解】令符合题设条件的闭折线为 A1A2AnA1，则所有顶点 的坐标（ ）符i iyx,合 并且 为一固定的正整数） ，其中).,21(,niZyxiLCiYXii ,(2L则由已知有),(, 111 yxyYX nniiiii 5 niiX1,0niY1,222 nYXXL不妨设 中至少有一个为奇数（因为设 是指数最小的，t i为奇数，ii和 mii,2用 2m 除所有的数后，其商仍满足、式） ，于是它们的平方和 C 只能为
11、 4k+1 或4k+2.当 C=4k+2 时，由知，所有数对 都必须是奇数，因此，根据、式知，niiYX与必为偶数.当 C=4k+1 时，由知，所有数对 都必一奇一偶，而由知，X i中为奇数的有ii与偶数个（设为 2u） ，余下的 n2u 个为偶数（与之对应的 Yi必为奇数） ，再由知，这种奇数的 Yi也应有偶数个（设为 ） ，故 =偶数.u2)(un综上所述，不能作出满足题设条件而有奇数个节的闭折线.例 7求出最小正整数 n，使其恰有 144 个不同的正因数，且其中有 10 个连续整数.（第 26 届 IMO 预选题）【解】根据题目要求，n 是 10 个连续整数积的倍数，因而必然能被 2，3
12、，10 整数.由于 8=23，9=3 2，10=2 5，故其标准分解式中，至少含有 233257 的因式，因此，若设 则 由,17431 L .1,3421而 故最)()(32 ,482)()(3多还有一个 为使 n 最小，自然宜取 由,50jj且 .05考虑)0(1)()1()0(14)()1()( 5432154321 时或时144 的可能分解，并比较相应 n 的大小，可知合乎要求的（最小） ,2故所求的,543.807325下面讲一个在指定集合内的“合数”的问题.这种合数与通常的合数有区别，题中的“素元素”是指在该集合内的素数，也与通常的素数有区别.例 8设 n2 为给定的正整数， 试证
13、：存在一数 这个数可用不.,1*NknV,nVr6只一种方式表示成数集 Vn 中素元素的乘积 . （第 19 届 IMO 试题）【证明】由于 Vn 中的数都不小于 因而 .),2(1 nVnn)12(,)12(,显然 是 Vn 中的素元素.又若（2n1） 2 不是 Vn 中素元素，则有)2(1,)(2n由此有 于是 从而,)(2bab使 ,4ba,3ab=1,a=1;b=1,a=2,b=1,a=3,对此就有 故 n=8.这说明 ，当 就是 Vn82)1(8时中素元素.当 )()2(1,.)12(,8 nnrVnrnn且显 然令时 ).12(当 n=8 时，有 1089=1368+1=9121=
14、3333，而 9，121，33V 8.综上知，命题得证.例 9已知 n2，求证：如果 对于整数 k（ ）是质数，则nk2 30n对于所有整数 都是质数.k)0(（第 28 届（1987）国际数学奥林匹克试题 6）【证】设 m 是使 为合数的最小正整数.若 的最小nk2 nmpn2,3是令质因子，则 .p（1）若 mp，则 p|(mp) 2+(mp)+n. 又(mp) 2+(mp)+nnp，这与 m 是使为合数的最小正整数矛盾.nk2（2）若 mp1，则 被 p 整mp )(1()1()1(除，且 .)(2n因为 为合数，所以)( .12,mp由 即 ,122mp ,0132nm由此得 363n7与已知矛盾.所以，对所有的 为质数.nknk2,3
