《数学奥赛辅导_第一讲_奇数、偶数、质数、合数》由会员分享,可在线阅读,更多相关《数学奥赛辅导_第一讲_奇数、偶数、质数、合数(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