数学竞赛中的数论问题

罗增儒引言研究正整数的一个数学分支.什么是正整数呢?人们借助于“集合”和“后继”关系给正整数(当时也即自然数)作过本质的描述，正整数1,2,3,…是这样一个集合N:(1)有一个最小的数1.(2)每一个数a的后面都有且只有一个后继数a';除1之外，每一个数的都是且只是一个数的后继数.(3)对N_的子集M,假设1∈M,且当a∈M时，有后继数a¹∈M,那么M=N.没有成熟到解决它的程度.比方，哥德巴赫猜测：1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和.后者是前者的推论，也可独立证明(已解决).“表示为两个素数和的形式”就是著名的哥德巴赫猜测，简称1+1.1900年希尔伯特将其归入23个问题中的第8个问题.1966年陈景润证得：一个素数+素数×素数(1+2),至今仍无人超越.的话：“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜测那么是皇冠上的明珠.……”陈景的明珠”仅一步之遥.●数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了.任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他(她)将来去从事数学方面的工作(U.Dudley《数论根底》前言).下面，是一个有趣的故事.题加以考察(1959):如果你手头上有n+1个正整数，这些正整数小于或等于2n,那么你一定有一对不到12岁的波萨只用了1分半钟，就给出了问题的解答.他将1～2n分成(1,2),(3,4),…,(2n-1,2n)共n个抽屉，手头的n+1必定互素.数，几何，初等数论，组合初步(俗称代数题、几何题、算术题和智力题).高中竞赛加试四道题正好3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分方程.根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型：(1)奇数与偶数(奇偶分析法、01法);(3)平方数；(4)整除；(5)同余；(6)不定方程；(7)数论函数、[x]高斯函数、φ(n)欧拉函数；(8)进位制(十进制、二进制).下面，我们首先介绍数论题的根本内容(10个定义、18条定理),然后，对数学竞赛中的数论问题中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理.定义1(带余除法)给定整数a,b,b≠0,如果有整数q,r(O≤r<|b1)满足定义5大于1且除1及其自身外没有别的正整数因子的正整数，称为素数(也称质数).其余大于1的正整数称为合数；数1既不是素数也不是合数.证明1先证存在性.作序列相减(q-q₂)b=r₂-r,注：如果取消O≤r<b,当r<0或r>b,不保证唯一.经典方法：紧扣定义，构造法证存在性，反证法证唯一性.证明2.只证存在性，用高斯记号，由有,故存在a=qb+r=qb+(b+r)=b(q即M有r比r更小，这与r为最小值矛盾.证明设A={a,b的公约数},B={b,c的公约数}.任J得A=B.有A中元素的最大值=B中元素的最大值，即注：这是辗转相除法求最大公约数的理论根底.经典方法：要证明A=B,只需证AB且BA定理3对任意的正整数a,b,有的公倍数，那么存在正整数m使k=m[a,b],有(2)ax₀+by₀=(a,b).得得r=a(x-qx₀)x+b(y-qY₀)<ax〔2〕由(1)有p=P·P₂…较P,+1>1.2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数.注：这个证明中，包含着数学归纳法的早期因素：假设假设有n个素数，便有n+1个素数.(构造法、反证法〕秒定理8(整除的性质)整数a,b,c通常指非零整数定理9(同余的性质)设a,b,c,d,m为整数，m>0,(1)假设a=b(modm)且b=c(modm),那么a=c(modm);证明由a=b(modm)且b=c(modm),a-b=mq,b-c=mq₂'(2)假设a=b(modm)且c=d(modm),那么a+c=b+d(modm)且ac=bd(modm).a-b=mg₁,c-d=mq₂,对①直接相加,有对①分别乘以c,b后相加，有ac-bd=(ac-bc)-(bc-bd)=m(c(3)假设a=b(modm),那么对任意的正整数n有a*=b°(modm)且an=bn(modmn).得a²*¹+b³¹=(a+b)(a²~²-a²~>b+a²**b²-…-ab²~³+b²*2)·a²”-b²”=(a+b)(a²~¹-a²~-b+a²~*b²-…+ab²~²-b^*')设 定理11给定整数k≥2,对任意的正整数n,都有唯一的k进制表示.如定理12(算术根本定理)每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，证明1先证明，正整数n可分解为素数的乘积①下面证明分解式是唯一的.假设n还有另一个分解式n=q₁9₂*9’P₁=9₁·P₂P₃…Pm=q₂Q₃…q₁·证明2用第二数学归纳法证明P₁=9;,q₁=P;’又P₁=q₁≥q₁=P;≥所以P₁=9P₂P₃…P=9₂Q₃…q₁·n=P“P₂“²…P.注省略号其实是有限项之和.画线示意50!中2的指数.假设不然，存在t,s,l≤t<s≤p-1,使sa=pq₅+r₅,再把上述p-1个等式相乘，有其中M是一个整数.亦即〔1〕a=1,命题显然成立.故有这说明，命题对a=k+1是成立.由容斥原理得注示意n=3的容斥原理.(1)必要性(方程有解必须满足的条件).假设方程存在整数解，记为那么(2)充分性(条件能使方程有解).假设d|c,可设c=de由于形如ax+by的数中有最小正数ax₀+by₀=(a,b).两边乘以e,得这说明方程有解方程的一切整数解可以表示为①证明直接代入知①是方程的整数解，下面证明任意一个整数解都有①的形式.由(x₀,yo)是方程的一个解，有ax+by=c,相减a(x-x₀)+b(y-y₀)=0.3有得方程的任意一个整数解可以表示为定义10(平面整点)在平面直角坐标系上，纵横坐标都是整数的点称为整点(也称格点).类似地可以定义空间整点.第二讲数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数(素数与合数),平方数，整除，同余，不定方程，数论函数等.重点是通过典型范例来分析解题思路、提炼解题方法和稳固根本内容.整数按照能否被2整除可以分为两类，一类余数为0,称为偶数，一类余数为1,称为奇数.偶数可以表示为2n,奇数可以表示为2n-1或2n+1.一般地，整数被正整数m去除，按照余数可以分为m类，称为模m的剩余类C;={x|x=i(modm)},从每类中各取出一个元素a,∈C,可得模m的完全剩余系(剩余类派出的一个代表团),0,1,2,…,m-1称为模m的非负最小完全剩余系.数字化都有联系，在数学竞赛中有广泛的应用.关于奇数和偶数，有下面的简单性质：(1)奇数≠偶数.(2)偶数的个位上是0、2、4、6、8;奇数的个位上是1、3、5、7、9.〔3〕奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；(4)奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数.〔5〕除2外所有的正偶数均为合数；〔6〕相邻偶数的最大公约数为2,最小公倍数为它们乘积的一半.(7)偶数乘以任何整数的积为偶数.(9)乘积为奇数的充分必要条件是各个因数为奇数.〔10〕n个偶数的积是2”的倍数.是偶数.例1-1(1986,英国)设q₁,a₂,…,a₇是整数，b,b₂,…,b,是它们的一个排列，证明数减小数),所得的14个差恰好为1,2,…,14?解考虑14个差的和S,一方面解(1)4堆是不能保证的.如4堆的奇偶性为：(反例)(奇奇),(偶偶),(奇偶),(偶奇).例4有n个数xj,x₂,…,X₇-,x₁,它们中的每一个要么是1,要么是-1.假设xX₂+X₂X₃+…+…+Xr-X+x,X₁=0,求证4|n.x₁X₂+X₂X₃+…+…+X₇-Xn(-1)(+1)⁴=xX₂*X₂5;…*-×,*X所以，n为4的倍数，4|n.(q₁,a₂,…,a,-,a中至少有2个偶数)第二步证至少有2个偶数.连一线段，可得n+1条互不重叠的线段，证明在此n+1条线段中，以一个有理点和一个无理点为端点(q₁a₂)(a₂a₃)(a₃a₄)…(q₁₄Q₁₂)=(-1=a₁(a₂a₃…a₁-)²an+₂=q(1)短除法.(2)分解质因数法.设b=pp₂·…P₄²,β≥0,i=1,2,…,k.那么(a,b)=p*p₂…P,解(1)方法1分解质因数法.由得得方法2辗转相除法.或(2)方法1短除法.由得得方法2.分解质因数法.由得正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9,那么n的最小解依题意，对最小的n,那么n+1是2,3,4,5,6,7,8,9,10的公倍数得n=2519.解相当于求不定方程15x+27y=6的整数解.即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升.成立.即命题对n=k+1时成立.由数学归纳法知命题对n≥2成立.证明1(反证法)假假设可约，那么存在①②③④⑤解题分析：(1)去掉反证法的假设与矛盾就是一个正面证法.(2)式④是实质性的进展，说明由此获得2个解法.消去n,②×3-①×2,得①②③④⑤=1.解题分析：第④相当于①-②;第⑤相当于②-2〔①-②〕=②×3-①×2;所以③式与⑤式的效果是一样的.例12不存在这样的多项式f(n)=a₂n"+am|n"*+…+n+a₀p使f(b)=a,b"+aw-b"~¹+…+a;进而对任意的整数k,有f(b+kp)=a(b+kp)"+a(b+(1)平方数的个位数只有6个：0,1,4,5.6.9(2)平方数的末两位数只有22个：00,01,21,41,61,81,04,24,44,64,84,25,16,36,56,76,96,09,29,49,69,89.(4)(2n-1}²=1(mod8).〔6〕但凡不能被3整除的数，平方后被3除余1.(7)在两个相邻整数的平方数之间，不能再有平方数.2.平方数的证明方法(1)反证法.(2)恒等变形法.(4)约数法.证明该数有奇数个约数.3.非平方数的判别方法(2)约数有偶数个的数不是平方数.〔3〕个位数为2,3,7,8的数不是平方数.(4)同余法：满足下式的数n都不是平方数.(5)末两位数不是：00,01,21,41,61,81,04,24,44,64,84,25,16,36,56,76,96,09,29,49,69,89.如个位数与十位数都是都是奇数的数，个位数是6、而十位数是偶数的数.例13有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1,2,…,99,100.每盏灯由一个拉线开关控制着.最初，电灯全是关着的.另外有100个学生，第一个学生走过来，把但凡号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把但凡号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把但凡号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的?讲解(1)直接统计100次拉线记录，会眼花缭乱.(2)拉电灯的开关有什么规律：电灯编号包含的正约数〔学生〕才能拉、不是正约数(学生〕不能拉，有几个正约数就被拉几次.(3)灯被拉的次数与亮不亮(开、关)有什么关系：0123456789关开关开关开关开关开灯被拉奇数次的亮!(4)哪些数有奇数个约数：平方数.(5)1～100中有哪些平方数：共10个：答案：编号为1,4,9,16,25,36,49,64,81,100共10个灯还亮.例14直角三角形的两条直角边分别为正整数a,b,斜边为正整数c,假设a为素数，求证证明由勾股定理c²=a²+b²,有为平方数.例152(a+b+1)=2a+(a²-1)+2求证，任意3个连续正整数的积不是平方数.证明设存在3个连续正整数n-1,n,n+1(n>1)的积为平方数，即存在整数m,使这一矛盾说明，3个连续正整数的积不是平方数.个不同元素a,b,使得ab-1不是完全平方数.证明因为2×5-1=3²,2×13-1=5²,5×13-1=8²,所以不是完全平方数只能是2d-1,5d-1,13d-1.假设结论不成立，那么存在正整数x,y,z,使同时成立，由①知x是奇数，设x=2n-1①②③代入①得2d=q²-p²=(q+p)(q-p).证明k是正整数.式中a,b是对称的，不妨设a≥b.(1)假设a=b,那么(2)假设a>b,由带余除法定理，可设a=bs-t(s≥2,0≤t<b,s,t是整数),那么由且得化简b²+t²=sbt+s这种证明的方法叫“无穷递降法”,是17世纪法国数学家费马(Fermat.1601一1665)首创和应用的一种方法.整除的判别方法主要有7大类.(2)具体找出q,滿足a=bq.例18任意一个正整数m与它的十进制表示中的所有数码之差能被9整除.2.数的整除判别法.〔1〕任何整数都能被1整除.(2)如果一个整数的末位能被2或5整除，那么这个数就能被2或5整除.(3)如果一个整数的末两位能被4或25整除，那么这个数就能被4或25整除.(4)如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除.(5)如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除.a₁×10⁴+a₁×10¹+…+q₁×10+q₀=a₄a×10⁴+a₄-×10~¹+…+q₁×10+q₀=〔6〕如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7或11或13整除，那么这个数就能被7或11或13整除.又由1001=7×11×13,而7,11,13均为素数知，m能被7或11或13整除.(7)如果一个整数的奇位数字之和与偶位数字之和的差能被11整除，那么这个数能被11整除.3.分解法.主要用乘法公式.如=(1+8)m,+(2+7)m₂+(3+6)m₃得9|S.=(1+9)m₁+(2+8)m₂+(3+7)m₃证明例20-1.2009年9月9日的年、月、日组成“长长久久、永不别离”的桔祥数字20090909,而它也恰好是一个不能再分解的素数.假设规定含素因子20090909的数为桔祥数，请证明最简分数的分子m是桔祥数.其中p为正整数，有20090909×n×p=1×2×…×20090907×2009这说明，20090909整除1×2×…×20090907×20090908×m,但20090909为素数，不能整除1×2×…×20090907×20090908,所以20090909整除m,得m是桔祥数.4.余数分类法.证明1任何整数n被3除其余数分为3类n=3k,n=3k+1,n=3k+2,(1)n=3k时，有证明2得5.数学归纳法.6.反证法.7.构造法.例22k个连续整数中必有一个能被k整除.假设这k个数被k除没有一个余数为0,那么这k个数的余数只能取1,2,…,k-1,共k-1种情况，a+i,a+j,0<i-j<k,与i-j<k矛盾.故k个连续整数中必有一个能被k整除.例23k个连续整数之积必能被k!整除.(1)假设这k个连续整数为正整数，那么只须证明，对任何一个素数p,分子中所含p的方次不低于分母中所含p的方次，由高斯函数的〔2〕假设这k个连续整数中有0,那么连乘积为0,必能被k!整除.为整数.例24有男孩、女孩共n个围坐在一个圆周上(n≥3),假设顺序相邻的3人中恰有一个男孩的那么“3人组”数值化为其中a+j=aj·有a个，得3(a₁+a₂+…+a₁)=(a₁+a₂+a₃)+(a₂+a=3p+(-3)q+(-1)a+b=3(p-q)例25〔1956,中国北京〕证明对任何正整数n都是整数，并且用3除时余2.分析只需说明为整数，但不便说明“用3除时余2”,应说明是3的倍数.作变形命题可证.①根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解例26正方体的顶点标上+1或-1,面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0.证明记14个数的和为S,易知，这14个数不是+1就是-1,假设八个顶点都标上+1,那么S=14,命题成立.对于顶点有-1的情况，我们改变-1为+1,那么和S中有4的数a,b,c,d改变了符号，用S'表示这说明，改变一个-1,和S关于模4的余数不变，重复进行，直到把所有的-1都改变为+1,那么①②f(x₀)=0(mod2)⇔q+q₁+与①矛盾.与②矛盾.未知数的个数多于方程个数的整系数代数方程，称为不定方程.求不定方程的整数解，叫做解不定方程.解不定方