中学数学中与初等数论相关的几个问题

目录TOC\o"1-5"\h\z1.前言1利用整除性判别法解决整除问题12.1能被2k或5k整除的判别法12.2割尾判别法2利用整除的基本性质解题4最大公因数6抽屉原理在数论中的应用7致谢107.参考文献10中学数学中与初等数论相关的几个问题陈琴（指导老师:左可正）

（湖北师范学院数学系湖北黄石435002）

1.前言在中学数学中，整数是特殊常用的一类数.而初等数论是研究整数的性质的、与算术有密切关系的一门学科，可以说初等数论是算术的延续.初等数论问题更是数学竞赛试题多发区.而对于整除性质和抽屉原理的考察一直是中学数学竞赛中应用范围最广的核心内容,作为高中教师,有必要对这些知识进行系统的考查.2.利用整除性判别法解决整除问题一个数能不能被另一个数整除，虽然可以用长除法去判别，但当被除数位数较多时，那是很麻烦的。要判别一个正整数a能否被另一个正整数d整除，往往可变为只要找出另一（绝对值）较小的整数b,而去判别b能否被d整除。这个新的整数b也就称为判别数。要看一种整除判别法是否优越，就在于能否用较快的速度而得出很小的判别数。因为判别数b越小，就越容易判别能否被d整除。下面我将阐述两种判别法。2.1能被2k或5k整除的判别法令整数a=aa...a（Ova<9,0<a<9,i=1,2,...,n）.aeN.01n0ii因为2k110k，但2k不整除10k-i,故要判别a是否能被2k整除，就是要而且只要判别a—a―财2能否被2k整除•我们可以用一个例子来证实这个判别法.n-k+1n-k+2n-2n例1:试判别51024能否被16整除?解:显然16=24,故相当于来判别a是否能被24整除.但1024=1000+24而2311000,24不整除1000,故知以24除1000的余数为8,而8+24=32可被16整除,故知1651024.与能被2k整除的道理一样，判别a是否能被5k整除，只需要看aa...aan-k+1n-k+2n-2n能否被5k整除就行了•对不同的k如何判别,现分述如下：⑴当k=1时，即要判别a是不是5的倍数，这时的充分必要条件是a=0或5.n⑵当k=2时，即要判别a是否能被25整除，这时只要看厂夕.而25|厂夕的充分必n-1nn-1n要条件是aa=25,70,75或a=a=0.n-1nn-1n(3)当k=3时，即要判别a是否能被125整除，这时只要看a的最右边三位数aaa,而125〔aaa的充分必要条件是n-2n-1nn-2n-1naaa=125,250,375,500,625,750,875或a=a=a=0.n-2n-1nn-2n-1n⑷当k>4时,要判别a是否能被5k整除，则可用“逐步约商”判别法.例2:试判别21401375能否被54整除.解:我们只需要判别1375能否被54整除就行了.75显然可以被52整除.现用“逐步约商”判别法.因为1375=25・55,即25除1375的商为55.而55不能被25整除.可见1375不整除54,从而21401375不整除54.2.2割尾判别法TOC\o"1-5"\h\z先给出一个定理:假定自然数a=aaaa...a，如果a能被奇质数p整01..n-kn-k+1n除，则将a的右端任意割去k位(不妨设割去的k位数不是p的倍数，否则无讨论之必要)，必存在唯一的正整数m<p(只与p和k有关)，使得a的判别数1b=aa...a—m(a...a)(1)01n-k1n-k+1n仍是p的倍数.同时也存在唯一的正整数m<p，使得a的判别数2b=aa...a+m(a...a)(2)01n-k2n-k+1n也是p的倍数.下面我将对此定理作出证明.证明:我们只要就该定理中之(1)式证明就行了(因(2)式完全同理可证).事实上，由于从a的尾部割去的k位数a...a和p互质，则可知同余方程n-k+1

(a...a)x三aa...a(modp)n-k+1n01n-k有唯一解.令它为x三m(modp).于是该定理得到证明.1对于p的倍数a割去k位并按(1)式的要求而定出m后，由于m的唯一性，若a不是p11的倍数，则按(1)式的要求作出的判别数b也一定不是p的倍数.反过来，由b是否为11p的倍数也可判定a是否为p的倍数•而且对(2)式也可同理应用.为了进一步阐述割尾判别法，我们可以看一个例子:例3:试判别816751136124能否被7整除?解:解:我们用(1)式，割去3位或6位.割去3位时，m=1.割去6位时m=6我们用长除法11的形式来解出判别数剖三位的判别法124816751_)012剖三位的判别法124816751_)012012割六隹的判别法由上述过程我们可以看出:割三位的方法经过三步得出的判别数为77，故可断定816751136124能被7整除;而割六位的方法只要一步就得出判别数7，故也能断定816751136124能被7整除.通过上面的例子我们应作几点说明:(1)当将要判别的数割去1位,2位,3位，…时，m是为多少是怎样知道的?确定方法1是:当割去一位时，则可在7的倍数中取一简单的两位数(最好个位数为1).比如21.将21的个位数1割去，此时剩下一个2，而2减去1的2倍就等于零.而零显然可以被7整除.故此法可确定m=2.当割去两位时，则可在7的倍数中取一简单的1三位数.比如301.将301的右端两位数割去，此时剩下一个3，而3减去01的3倍就等于零.故此时可确定m=3.同理可确定其它位数的m,这个m就叫做割尾判111别法的“乘数”.它随割去的位数不同而异.(2)在例3中很碰巧,经三步割三位后的判别法只有两位,经一步割6位数后得判别数只有一位.若有3位或3位以上,则应再割去1位或2位,就是说,有时判别一个数需要几种割尾法交错使用,直到得出最后的判别数是一位或两位为止.将例3加以推广,割尾法同样可以判定a被13,17,19整除.3.利用整除的基本性质解题整除是初等数论中最基本的内容之一，b|a的意思是存在一个整数q,使得等式a=bq成立.因此这一标准作为我们讨论整除性质的基础.也为我们提供了解决整除问题的方法.即当我们无法用整除语言来叙述或讨论整除问题时，可以将其转化为我们很熟悉的等号问题.例4：证明3|n(n+1)(2n+1),这里n是任意整数.证法一：根据题意，n可以写成n=3q+r，这里r=0,1,2,q为整数.对r取不同值进行讨论，得出结论.证法二：根据整除定义，任何连续三个整数的乘积必是3的倍数.12+22+...+说二1n(n+1)(2n+1),证法三：根据n(n+1)(2n+1)，利用来证明.证法四：利用数学归纳法也可以证明.竞赛中关于数论的论证题主要是讨论整除的整除性和整数解，证明方法通常有：直接证明法，间接证明法(反证法).例5：已知24|62742ab，求a,b.由于24=3X8,而(3,8)=1,3和8都是特殊数，故本题往往习惯于利用整除特征加以解决.但利用整除特征解答有两个弊端，即(1)解题过程一般较烦琐;(2)若非特殊数无法解.可利用整除的因式分解法得出一般的解法.对于特殊数的整除规律要求能掌握其一般定理的证明,并熟记一些特殊数的整除规律,这对解题大有帮助.例如：1、一个整数被2整除的充要条件是它的末位为偶数.2、一个整数被3整除的充要条件是它的各位数字之和能被3整除.3、一个整数被9整除的充要条件是它的各位数字之和能被9整除.4、一个整数被5整除的充要条件是它的末位数字为0或5.

5、一个整数被4，25整除的充要条件是它的末二位能被4，25整除.6、一个整数被8，125整除的充要条件是它的末三位能被8，125整除.例6:证明：对于整数x与y,2x+3y与9x+5能同时被17整除或不可整除.证:记u=2x+3y,v二9x+5,贝V有3v—5u=17x即3v=5u+17x(1)5u=3v—17x(2)若对xyez,17|u.其中u=2x+3y，由⑴0,00000知1713v，其中v=9x+5y.又(17,3)=1,所以17|v.00000同理可证，对x,yez,17|v，其中v=9x+5y侧17|u，其中u=2x+3y.1111111111证毕.【分析】将本题加以推广:用ax+by,cx+dy代替2x+3y与9x+5y.令u=ax+by,v=cx+dy.设ad—bc丰0消去y,du—消去y,du—bv=(ad—bc)x=abcdx.记s=abcddu=bv+sx,bv=du—sx若(d,s)=(b,s)=1,则对同样的x,y,u与v同时被s整除(或同时不被s整若(a,s)=(c,s)=1,结论成立.例6中例6中2395=—17,而(3,—17)=(5,—17)=1,(2,—17)=(9,—17)=1.所以例4成立.例7:1000!的末尾有几个零?解:考虑1000!的标准分解式中2与5这两个素数的指数,若1000!=2r15r2A,AeN,A不能被2与5整除，则1000!中末尾有r个零，r是r和r中12较小者.在1,2,3,…，1000中，有200个数能被5整除，在这200个数中，有40个能被52整==7(7k+2+82k+1)+82(82k+1+7k+2)—7殆2k+1—82gk+2除,在这40个数中,有8个能被53整除,在这8个数中,有1个能被54整除.不大于1000的自然数中没有能被5的5次幂或更高次幂整除的数.可见在1000!的标准分解式中,5的指数r二200+40+8+1二249.2显然r>r，所以r二249,即1000!的末尾有249个零.124.最大公因数和整除性一样，二个数的最大公约数实质上也是用等号来定义的，因此在解决此类问题是如果有必要的话可化为等式问题.最大公约数的性质中最重要的性质之一为：若a二bq+c，则一定有(a,b)=(b,c),这就是求二个整数的最大公约数的理论根据.最小公倍数实际上与最大公因数为对偶命题•特别要指出的是a和b的公倍数是有无穷多个.所以一般地在无穷多个数中寻找一个最小数是很困难的，为此在定义中所有公倍数的最小的正整数.这一点实际上是应用自然数的最小自然数原理.即自然数的任何一个非空子集一定有一个最小自然数存在•最小公倍数的问题一般都可以通过以下式子转化为最大公因数的问题.两者的关系为a,beN,[a,b]—“(a,b)例8：对于任意的非负整数n,求形式为7n+2+8n+2=57的一切数的最大公因子.在解答初等数论的习题中,如果我们把题目有关的概念,例如整除,最大公因子,互素等用等式表示出来,再经过这些等式的恒等变形,常常能够找到解题的方法.解：当n二0日寸,7(k+i)+2+82(k+i)+i=57;假设n=k时，57|7k+2+82k+i;当n=k+1寸,7(k+1)+2+82(k+1)+1=7k+2g7+82k+1g8=57q-(7殆2k+i+64g7k+2)=57q-(7殆2k+i+7g7k+2+57g7k+2)=57q-[7(7k+2+82k+1)+57g7k+2]=57p(p,qeN)故形为7n+2+82n+2的一切数的最大公因子为57.例9:证明:若a,beN，那么等差数列a,2a,3a,...ba中能被b整除的项数等于a与b的最大公约数.证明:设(a,b)=d，于是a=dr,b=ds,r,seN.(r,s)=1.a,2a,3a,...ba被b整除之后为r2r(ds)rsss由于(r,s)=1.上式中各项为整数者的项数，仅为1,2,…，竺中为整数的项数，所以sss共计d项,证毕.5.抽屉原理在数论中的应用抽屉原理又称鸽巢原理，它是组合数学的一个基本原理，最先是由德国数学家狄利克雷明确地提出来的，因此，也称为狄利克雷原理。把3个苹果放进2个抽屉里，一定有一个抽屉里放了2个或2个以上的苹果。这个人所皆知的常识就是抽屉原理在日常生活中的体现。用它可以解决一些相当复杂甚至无从下手的问题。原理1：把n+1个元素分成n类，不管怎么分，则一定有一类中有2个或2个以上的元素。原理2：把m个元素任意放入n(nWm)个集合，则一定有一个集合至少要有k个元素。其中k=m/n(当n能整除m时)或k=〔m/n〕+1(当n不能整除m时)，这里〔m/n〕表示不大于m/n的最大整数，即m/n的整数部分。原理3：把无穷多个元素放入有限个集合里，则一定有一个集合里含有无穷多个元素。原理2也可以变为：把m个元素任意放入n(nWm)个集合，则一定有一个集合至多要有k个元素。其中k=〔m/n〕，这里〔m/n〕表示不大于m/n的最大整数，即m/n的整数部分。应用抽屉原理解题的步骤:第一步：分析题意。分清什么是“东西”，什么是“抽屉”，也就是什么作“东西”，什么可作“抽屉”。第二步：制造抽屉。这个是关键的一步，这一步就是如何设计抽屉。根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽屉及其个数，为使用抽屉铺平道路。第三步：运用抽屉原理。观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，以求问题之解决。利用上述原理容易证明：“任意7个整数中，至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能，所以7个整数中至少有3个数除以3所得余数相同，即它们两两之差是3的倍数。1958年6/7月号的《美国数学月刊》上有这样一道题目：“证明在任意6个人的集会上，或者有3个人以前彼此相识，或者有三个人以前彼此不相识。”这个问题可以用如下方法简单明了地证出：在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人。如果两人以前彼此认识，那么就在代表他们的两点间连成一条红线；否则连一条蓝线。考虑A点与其余各点间的5条连线AB,AC,...,AF,它们的颜色不超过2种。根据抽屉原理可知其中至少有3条连线同色，不妨设AB,AC,AD同为红色。如果BC,BD,CD3条连线中有一条(不妨设为BC)也为红色，那么三角形ABC即一个红色三角形，A、B、C代表的3个人以前彼此相识：如果BC、BD、CD3条连线全为蓝色，那么三角形BCD即一个蓝色三角形，B、C、D代表的3个人以前彼此不相识。不论哪种情形发生,都符合问题的结论。例10：从1〜100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个数是另一个数的整数倍.【分析】现在的‘苹果'数定了51个,我们怎么来构造出符合要求的50层抽屉来?显然抽屉的构造只能从I〜100个数中选取，从整数倍这点提示我们,在构造抽屉时应重点考虑这个问题.有一种方法,我们可以按奇数的2的n次方的倍数分组（因为刚好50个奇数）.即{1,2,4,6,-,64};{3,6,12,•••,96};{5,10,20,40,80};{7,14,28,55};•••{97};{99}.共50组.任取51个数,必有两个数落在同一组里.显然,同一组的两个数,必定有一个数是另一个数的整数倍.在这里运用了构造抽屉的思想,在整除问题中有时题目太复杂,构造抽屉可以缩小题目的范围,达到简化的目的.例11:a,b,c,d为任意给定的整数,求证:以下六个差数b—a,c—a,d—a,c—b,d—b,d—c的乘积一定可以被12整除.证明把这6个差数的乘积记为p,我们必须且只需证明:3和4都可以整除p,以下分两步进行.第一步，把a,b,c,d按以3为除数的余数来分类,这样的类只有三个,故知a,b,c,d中至少有2个除以3的余数相同，/