高中数学竞赛资料数论部分

1、初等数论简介绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。1 .请看下面的例子:（1） 证明：对于同样的整数x和y,表达式2x+3y和9x+5y能同时被整除。（1894年首届匈牙利 数学竞赛第一题） 设n Z ,证明132n 1是168的倍数。具有什么性质的自然数 n,能使1 2 3 m n能整除12 3|n? （ 1956年上海首届数学竞赛第一题）31（3） 证明：n3 -n2 -n 1对于任何正整数 n都是整数，且用 3除时余2。（ 1956年北京、天津市首22届数学竞赛第一题）（4） 证明：对任彳S自然数 n ,分数21n 4不可约简。（1956年首届国际

2、数学奥林匹克竞赛第一题）14n 3（5） 令（a,b,|M，g）和a,b,Q,g分别表示正整数a,b,|,g的最大公因数和最小公倍数，试证：2a, b,c2a,b,ca,b b,c c, a a, b b, c c, a（1972年美国首届奥林匹克数学竞赛第一题）这些例子说明历来数论题在命题者心目中首当其冲。2 .再看以下统计数字:（1）世界上历史最悠久的匈牙利数学竞赛，从18941974年的222个试题中，数论题有41题，占18.5%。（2）世界上规模最大、规格最高的IMO （国际数学奥林匹克竞赛）的前 20届120道试题中有数论13题,占 10.8% 。这说明：数论题在命题者心目中总是占有

3、一定的分量。如果将有一定“数论味”的计数型题目统计在内, 那么比例还会高很多。3 .请看近年来国内外重大竞赛中出现的数论题:方程x3 6x2 5x y3 y 2的整数解（x, y）的个数是（）A、 0B、1C、3D、无穷多（2007全国初中联赛5）21（2）已知a,b都是正整数，试问关于 x的万程x abx - a b 0是否有两个整数解?2如果有，请把它们求出来；如果没有，请给出证明。（2007全国初中联赛 12）(3)是否存在正整数 m,n ,使得m(m 2) n(n 1) ?设k(k 3)是给定的正整数，是否存在正整数m,n,使得m(m k) n(n 1)?(2007全国初中联赛14)(

4、4)关于x,y的方程x2 xy 2y2 29的整数解(x, y)得组数为()A、2B、3C、4D、无穷多(2009全国初中联赛5)(5)已知a1，a2,a3,a4,a5是满足条件a1 a2 a3 aa5 9的五个不同的整数，若 b是关于x的方程(xa1)xa2xa3xa4xa52009的整数根，则b的值为(2009全国初中联赛8)(6)已知正整数a满足192a3 191,且a 2009,求满足条件的所有 可能的正整数a的和。(2009全国初中联赛 12) n个正整数|自满足如下条件：1 a a? an 2009 ；且&e2,|小小中任意n 1个 不同的数的算术平均数都是正数，求n的最大值。(2

5、009全国初中联赛14)一 一k 1 k 2(8)在一列数x1，x2,x3，中，已知x1 1 ,且当k 2时，xk xk 1 1 4( )(取整符号 a44表示不超过实数a的最大整数，例如2.62,0.20）则 x2010 等于（）11 / 191 / 19A、1B 、2C、3D、4(2010全国初中联赛4)(9)求满足2p2 p 8 m2 2m的所有素数P和正整数 m。(2010全国初中联赛13)(10)从1,2，2010这2010个正整数中，最多可以取出多少个数，使得所取出的数中任意三个数之和(2010全国初中联赛14)都能被33整除?（11）设四位数abcd满足a3 b3 c3 d3 1

6、10c d ,则这样的四位数的个数为 (2011全国初中联赛10)(12)已知关于x的一元二次方程x2 cx a0的两个整数根恰好比方程2x ax b 0的两个根都大1,求a+b+c的值（2011全国初中联赛11）（13）若从1,2,3，n中任取5个两两互素的不同的整数 a1,a2,a3,a4,a5其中总有一个整数是素数，求 n的最大值。（2011全国初中联赛 13）（14）把能表示成两个正整数平方差的这种正整数，从小到大排成一列：2,222a，a2,an,例如 a1213 , a2 325 ,那么 22007 =（2007福建省高一数学竞赛 12）（15）求最小的正整数 n,使得集合1,2,

7、3，2007的每一个n元子集中都有2个元素（可以相同），它们的和是2的哥。（2007福建省高一数学竞赛14）（16）两条直角边长分别是整数a和b（其中b1000）,斜边长是b+1的直角三角形有（）A、20 个B、21 个C、22 个D、43 个（2008福建省高一数学竞赛 5）99 ,则 7x 5y 的（17）设x、y为非负整数，使得x 2y是5的倍数，x y是3的倍数，且2x y最小值为（2008福建省高一数学竞赛11)（18）正整数a a? a12中，若任意三个都不能成为三角形的三边长，则a2的最小值是a1（2008福建省高一数学竞赛 12）（19）设S 1,2,3，n （ n为正整数），

8、若S得任意含有100个元素的子集中必定有两个数的差能被25整除，求n的最大值。（2008福建省高一数学竞赛 17）（20）设x是不超过x的最大整数，则 log；log：Iog3500iog3（2009福建省高一数学竞赛11)（21）已知集合M是集合S 1,2,3，,2009的含有m个元素的子集，且对集合M的任意三个元素x,y,z均有x+y不能整除z,求m的最大值。（2009福建省高一数学竞赛17)111(22)已知 a,b,c为正整数，且 c b a 1, (a )(b )(c )为整数，则 a+b+c= cab(2011福建省高一数学竞赛 12)1(23)正整数n 500,具有如下性质：从集

9、合1,2，500中任取一个兀素 m,则m整除n的概率是 一，100则n的最大值是(2008福建省预赛12)(24)设f(x)施周期函数，T和1是f (x)的周期且0 T 1,证明：1(1)若T为有理数，则存在素数 P,使是f(x)的周期；P(2)若T为无理数，则存在各项均为无理数的数列an满足1 an am 0 , (n=1,2,)且每个an都是f (x)的周期(2008全国高中联赛加试二)x 9(25)万程x的实数解事 (其中x表示不超过x的最大整数)2(2009福建初赛9)(26)设 xi近 1诉 1 ,i 1,2,，2010,令 S x#2 x3x4 X2OO9X2010(1) S能否等

10、于2010?证明你的结论；(2) S能取到多少个不同的整数值？(2009福建初赛14)(27)设k,l是给定的两个正整数，证明：有无穷多个正整数m k ,使得C；与l互素。(2009全国高中联赛加试三)(28)已知集合A xxa0a17a272a373，其中ai0,1,2,3,4,5,6 , i 0,1,2,3 ,且a3 0 ,若正整数 m,n A,且m n 2010, m n ,则符合条件的正整数 m有 个。(2010福建预赛6)33333(29)将万程x33 x 4的实数解从小到大排列得X1,X2，Xk,则X1X2X3Xk的值为(2010福建预赛8)(30)设 k是给定的正整数，r k 1

11、,记 f (r) f (r)rr, f (l)(r) f (f (l 1)(r) , l 2。证明：2存在正整数m,使得f (m)(r)为一个整数。这里，x表示不小于实数x的最小整数。(2010全国高中联赛加试二)(31)已知正整数 x,y,z 满足条件 xyz (14 x)(14 y)(14 z),且 x y z 28,则 x2 y2 z2 的最大值为(2011福建预赛7)(32)证明：对任意整数 n 4,存在一个n次多项式f (x) xn anxn1ax a0具有如下性质：(1) a0,a1, , an 1 均为正整数； 对任意正整数 m ,及任意k(k 2)个互不相同的正整数 口，2,，

12、rk均有f (m)f (r1) f (r2)f (rk)(2011全国高中联赛加试二)(33)证明：存在无穷多个正整数n ,使得n2 1有一个大于2n J2n的质因子。(2008 第 49 届 IMO.3 )(34)设n是一个正整数，a1,a2,ak(k 2)是集合1,，n中互不相同的整数，使得对于i 1,，k 1都有n整除4(、 1)。证明：n不整除ak(4 1)(2009第50届IMO.1 )本资料主要介绍中学代数课程里未能深入谈到的整数的性质及其应用，初等数论的解题过程通常不涉及很多的基础知识，重要的是机智和灵活。本资料除打上“*”的是少数内容外，初二年以上的学生均可学习掌握。为叙述方便

13、，本资料中的字母均表示整数。交有Z, N*, Z*分别表示整数集，正整数集和非零整数集。带余除法与整除整数的概念、分类、自然数两种理论(基数理论，序数理论)基数用于表示“多少”：将所有有限集分类，使所含元素个数一样多的集合成为同一类，对每一类用 一个记号来表示它们(这一类的集合)所含元素个数一样多这个共同特征。这个记号就是一个自然数。公理化的方法：对已有的知识进行深入的分析，选择其中一些基本关系作为不定义的概念，一些基本性质作为不加证明的公理，建立起公理系统。然后由所建立的公理系统出发，应用形式逻辑的方法，来给 出其它有关概念的定义，并证明各种命题。序数表示“第几”* （peano定理）如果非

14、空集合 N*中的某些元素之间有一个基本关系“直接后继”（元素a的直接后继记为 a）,且N*满足以下条件： 一一*一一*一.1. 1 N , a N ,必有 a 1. . .* . . . *2. aba b a N ,b N*3. ab a ba N ,b N4. N*的子集M若具有下面的性质i 1 M ii a M a M,则M N定理1带余除法、.* . . . . . . 、 . . . . . . . _ .设a Z , b Z则有且只有一对整数 q与r ,使得a bq r其中0 r b定义1、定理1中的q与r分别称a除以b的不完全商与最小非负余数，简称商和余数。定义2、定理1中的r

15、0时（即a bq时）就称a为b的倍数,b是a的约数（或因数）a能被b整除,b整除a ,记作b a性质1、0是任何数白倍数（0除外）；1是任何数的约束;b aa 0b a *c Zb ab a ;b | aa b ;bc ac;b ab ac;c Zbai n ki Zb Kai 1,2,3,|,n i1n nn 1 n 2n 2 n1、公式 1、xy(xy)(x xyxy y)公式 2、xnyn(xy)(xn1 xn2yxyn2 yn1)*(n N )(n是正偶数)公式 3、xn yn (x y)(xn 1 xn 2y例1、设b 99 99 (31位数)a例2、设a cab cd求证a cad

16、定义3、能被2整除的数称偶数，不能被IIbc 。n 2 n 1、xy y )(n是正奇数)(以上三个公式中的 x, y可以是任意实数)99(1984位数)，求证b a。2整除的数称奇数。性质2、用“ 0”代表偶数，“1”代表奇数，则有 0+0=0,0+1=1 , 1+0=1,1+1=00 0=0,0 1=0,1 0=0,1 1=1奇数个奇数的和还是奇数任意个奇数之积是奇数*例3、设p,q都是正奇数，且 p q 2,求证p qqq pp注意：奇偶分类在处理很多问题时有用。求末位数问题:令G(a)表示a的末位数，则有性质 3、 G(a b) G G(a) G(b) G(a b) G G(a) G(

17、b) G(am) G G(a)m任一自然数的正整数次哥的末位数有周期变化的规律。例4、求171988的末位数例5、设n, R为自然数，求证 G(a4R n) G(an);设n为自然数，求证G(a4n) G(a4)67例 6、G(67 )bc性质4、设b为奇数，c为偶数，则 G(ab) G(a)设b为偶数，c为奇数(c 1)则G(abc) G(a4)设b为偶数，c为偶数，则G(abc) G(a4)设b为奇数，c为奇数，(c 1)则G(abc) G(ab)19n个,19 1例 7、求 G(2219),212111*例8、求a 13 的末两位数。例9、设a1,a2,a3,|a7是1,2,3,|,7这

18、七个自然数的任何一种次序的排列，求证：(41)(a2 2)(a3 3)|(a7 7)总是一个偶数。例10、某班有49位同学，坐成七行七列，每个座位的前、后、左、右的座位叫做它的“邻座”，要让这49位同学中的每一位都换到他邻座上去，问这种调换座的方案能否实现？作为本节内容的结束，请注意以下两个重要的命题：在m(m 2)个相邻整数中，有且只有一个数能被m整除。若整数g 1 ,则任一正整数a能够唯一表示为a angn an 1gn 1a1g a0这里 ai Ln 0,且 0 ai1)是素数(N*1 )定理二：素数有无限多个。定理三：若N*是合数，P (P1)是N*的最小正因数,则 p jn以上的例子

19、和定理分别刻画了素数的某些分布特征和判断素数的方法。定理四：若ai Z,i 1,2,3, |“,n, P是素数，p a1a2H|an则P整除某个ai定理五：(唯一分解定理)每个大于1的整数，都可唯一地分解成素因数(不计因数的顺序)的积。推论：任一大于1的整数a可以唯一分解成a p11P22Mlpk k这里Pi是相异的素数，i是正整数。有时为了表述方便，允许 i 0,上式称为a的标准分解式。例2、设2m 1(m N)是素数，求证：m是2的非负整数次募。定理六：若a,b得标准分解式为a p11P22Mlpnn, b p11P22mpn n ,则(a,b) p；1 p2r2|( pnrn , a,b

20、 Pi 1 p22|pnn。# / 1911 / 19这里 ri min( i, i), i max( i, i) , i 1,2,|,n例 3、求证a, b,c(ab,bc,ca) abcn定理七：若a的标准分解式为a pi 1 P2 2 1I Pn n ,则a的一切正因数的个数 (a)( i 1),i 1n n i 1一切正因数的和为(a)-p。i 1 R 1例4、证明形如4n 1(n N)的素数有无限个。哥德巴赫于1742年在和欧拉的通信中提出的猜想：1 .每个大于5的偶数都是两个奇素数之和2 .每个大于8的奇数都是三个奇素数之和1973年5月中国科学杂志刊出陈景润研究G氐猜想的结果：“

21、任一充分大的偶数是一个素数和另一个素数的和，后者或为素数，或仅另两个素数的乘积。”此定理被简称为“ 1+2”当然离“1 + 1”还有一段距离，不过这已经是当今最优成果了。习题： 2/1、设p是异于3的奇素数，求证24 P 12、设p,q是素数，且p q 5,求证240 p4 q43、设整数 a,b,c都大于 1,证明(a,c),(b,c) (a,b,c)224、求证：a,b, c (a,b)(b, c)(c,a) (a,b,c) a,b b,c c, a5、设a,n都是大于1, an 1是素数，求证：a 2,且n是素数6、从1到100这100个自然数中，任意选出 51个数，求证其中至少有两个数

22、，它们中的一个是另一个的 倍数。7、设 a,b N,(a,b) 1,证明(a,b)(a) (b); (ab) (a) (b)8、证明：形如3n 2的素数有无限多个。9、设n 2,证明：在n与n!之间至少有一个素数。2n10、设Pn是表示由小到大排列的第 n个素数，证明pn 221同余1定义给定正整数 m,如果用它除任意两个整数a,b,所得余数相同，就说a,b对于模m同余，记作a b modm 。若所得余数不同，就说a,b对于模m不同余，记作a b modm 。定理与性质例1 正整数a能被9整除的充要条件是 a的各个数码之和能被 9整除。例2 设2=2e- a1a0 ,求证：11 a a0 a1

23、a21 n an 0 modn 。例3 求正整数a能被7正处的充要条件。4444 例4 设4444 的各个数码之和为 a, a的各个数码之和为 b,求b的各个数码之和为 c。例5 环形公路上有几个汽车站，海拔高度只有5米和10米两种，若相邻两站的海拔高度相等，则称连接它们的公路是水平的；如果两相邻汽车站海拔高度不等，则称相连公路是有坡的。有一旅行者坐汽车环行东路一周，发现水平公路的段数与有坡公路的段数相等，求证4整除n。例6设Pn 1n 2n 3n 4n n N，问：怎样的n使得10|Pn。例7 求证：任何整数x1,x2, ,x14都不能满足方程习题1 .设 a b modn ,求证： a,m

24、 b,m。22 .设 a 5 mod10 ,求证：a 25 mod1003 .设ABCDE是按逆时针方向排列的五角棋盘，从 证明无论移动多少次， C、E处永远不可能停留棋子。P4 .设a、b Z , P是素数，求证 a b ap444x1x2x14 1599ooA沿逆时针方向移动棋子，第K次移动K步,bp mod p。# / 1913 / 1922.25 .证明 n n 1 n 40 mod360 。6 .设 n, a N , 2恒,求证 a2 1 mod 2n2 。7 .已知n 4 mod9 ,求证n不能表为3个立方数的和。8 .已知n 7 mod8 ,求证n不能表为3个平方数的和。9 .求

25、出一个整数能被 101 （或37）整除的充要条件。779910 .求下列各数的末两位数：77和9 。101011 .记 0 a 7,且 10 a mod7 ,求 a。12 .已知 792 113ab45c,求 a、b、c。补充题：1. （1）有几个住鞫书，其积为 n,其和为零。求证 4| n。（2）设4| n,求证：可以找出几个整数，使其积为n,其和为零。（十八届全苏中学生竞赛）2.设a, b, c是三个互不相等的正整数，求证：在a3b ab3, b3c bc3, c3a ca3三个数中，至少有一个数能被10整除。（86.全国初中联赛，二试，四）3.把19,20,，79,80诸数连写成数 A=

26、1920217980,试证1980 | A。（全苏 14 届 1980.8.1）4.试求所有能被11整除的三位数，且除得之商等于被除数中各数字的平方和。（二届 IMO 1960）不定方程若方程或方程组中未知数的个数多于方程的个数，它们的解又限制为正整数、整数、有理数或其它类别的数，则称此方程或方程组为不定方程。不定方程常联系到一些有趣的问题。竞赛中也时有所见。例1在等式x5 3yz 7850中还原数学x, y, z。（1987年全俄中学生竞赛题）例2解方程xyz zyx xzyyx。（1978年广东省中学数学竞赛题）例3求方程2w+2x+2y+2z=20.625满足条件：wxyz的整数解。（1

27、979年湖南省中学数学竞赛数论函数17 / 1914 / 19定义1设x为任一实数， x表示不超过x的最大整数。函数x称数论函数，也称高斯函数、阶梯函数等。数论问题是竞赛中的热门课题，而则是热门中的热门。由定义,x Z 小 x x x 1 显然有；。定义x x 、称为乂的小数部分，显然0 x 1。19 / 1915 / 191 ,n N2解方程x x 。3x2x 1已知方程2,求所有根的和。（1987年初中联考）习题5 6x15x1.2.3Q3.x x 3。（英斯科第20届奥林匹克数学竞赛题）有时也常令x =x0,1通过对的讨论来解题。例5方程2_4x 40 x51 0 ,51 0的实数解的个

28、数是（）。（1985美国数学竞赛题）(A) 0 ；(B) 1 ；(C) 2 ；(D) 3 ；(E) 4 .表示不超过x的最大整数，设n是自然数，且I= n22n 1 n 1,那么(）。（1986年全国初中联考）(A)(B) I N;(B) M=N ;(C) MN ;（D）以上答案都不对HI1988 ,那么 JS的值是x3.找出一个实数x,满足证明，满足上述等式的 x都不是有理数。n+2k-k+14.（1968第十届IMO ）2a设n N ,计算和k=0 25.设a , b为互素的正整数，求证:6.然数集。min k2求所有自然数n ,使得（1991年中国数学奥林匹克）nk219911 2表示不

29、超过k的最大整数，N是自不定方程若方程或方程组中未知数的个数多于方程的个数，它们的解又限制为正整数、整数、有理数或其它类 别的数，则称此方程或方程组为不定方程。不定方程联系到一些有趣的问题。竞赛中也时有所见。例1.在等式中还原数字 x,y,z.（1987全俄中学生竞赛题）例2.解方程：例3.求方程2w 2x 2y 2z 20.625满足条件：w x y z的整数解。（1979年湖南省中学数学竞赛题）线性不定方程ax+by=c定理1设a,b,c Z,（a,b） d,a ad,b b d,则线性不定方程ax+by=c有整数解的充要条件是 d Co在有整数解的情形下，如果 x x0, y y0是一组整数解，