高中数学竞赛资料-数论部分.doc

初等数论简介
绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。
1． 请看下面的例子：
（1） 证明：对于同样的整数x和y，表达式2x+3y和9x+5y能同时被整除。(1894年首届匈牙利 数学竞赛第一题)
（2） ①设，证明是168的倍数。
②具有什么性质的自然数，能使能整除？（1956年上海首届数学竞赛第一题）
（3） 证明：对于任何正整数都是整数，且用3除时余2。（1956年北京、天津市首届数学竞赛第一题）
（4） 证明：对任何自然数，分数不可约简。（1956年首届国际数学奥林匹克竞赛第一题）
（5） 令和分别表示正整数的最大公因数和最小公倍数，试证：（1972年美国首届奥林匹克数学竞赛第一题）
这些例子说明历来数论题在命题者心目中首当其冲。
2.再看以下统计数字：
（1）世界上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占。
（2）世界上规模最大、规格最高的IMO（国际数学奥林匹克竞赛）的前20届120道试题中有数论13题，占10.8% 。
这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。
3.请看近年来国内外重大竞赛中出现的数论题：
(1)方程的整数解的个数是（ ）
A、 0 B、1 C、3 D、无穷多 （2007全国初中联赛5）
（2）已知都是正整数，试问关于的方程是否有两个整数解？
如果有，请把它们求出来；如果没有，请给出证明。
（2007全国初中联赛12）
（3）①是否存在正整数，使得？
②设是给定的正整数，是否存在正整数，使得？
（2007全国初中联赛14）
（4）关于的方程的整数解得组数为（ ）
A、2 B、3 C、4 D、无穷多
（2009全国初中联赛5）
（5）已知是满足条件的五个不同的整数，若是
关于的方程的整数根，则的值为
（2009全国初中联赛8）
（6）已知正整数满足，且，求满足条件的所有可能的正整数的和。 （2009全国初中联赛12）
（7）个正整数满足如下条件：；且中任意个不同的数的算术平均数都是正数，求的最大值。
（2009全国初中联赛14）
(8)在一列数中，已知，且当时，（取整符号表示不超过实数a的最大整数，例如）则等于（ ）
A、 1 B 、 2 C、 3 D、 4
（2010全国初中联赛4）
（9）求满足的所有素数P和正整数m。
（2010全国初中联赛13）
（10）从这2010个正整数中，最多可以取出多少个数，使得所取出的数中任意三个数之和都能被33整除？ （2010全国初中联赛14）

（11）设四位数满足，则这样的四位数的个数为
（2011全国初中联赛10）
（12）已知关于的一元二次方程的两个整数根恰好比方程的两个根都大1，求a+b+c的值
（2011全国初中联赛11）
（13）若从中任取5个两两互素的不同的整数其中总有一个整数是素数，求n的最大值。
（2011全国初中联赛13）
（14）把能表示成两个正整数平方差的这种正整数，从小到大排成一列：
，例如，，……那么=
（2007福建省高一数学竞赛12）
（15）求最小的正整数n，使得集合的每一个n元子集中都有2个元素（可以相同），它们的和是2的幂。
（2007福建省高一数学竞赛14）
（16）两条直角边长分别是整数a和b(其中b<1000)，斜边长是b+1的直角三角形有（ ）
A、20个 B、21个 C、22个 D、43个
（2008福建省高一数学竞赛5）
（17）设、为非负整数，使得是5的倍数，是3的倍数，且，则的最小值为
（2008福建省高一数学竞赛11）
（18）正整数中，若任意三个都不能成为三角形的三边长，则的最小值是
（2008福建省高一数学竞赛12）
（19）设（n为正整数），若S得任意含有100个元素的子集中必定有两个数的差能被25整除，求n的最大值。 （2008福建省高一数学竞赛17）

（20）设是不超过x的最大整数，则=

（2009福建省高一数学竞赛11）
（21）已知集合M是集合的含有m个元素的子集，且对集合M的任意三个元素x,y,z均有x+y不能整除z，求m的最大值。
（2009福建省高一数学竞赛17）
（22）已知a,b,c为正整数，且，为整数，则a+b+c=

（2011福建省高一数学竞赛12）
（23）正整数，具有如下性质：从集合中任取一个元素m，则m整除n的概率是，则n的最大值是
（2008福建省预赛12）
（24）设施周期函数，和1是的周期且，证明：
（1）若T为有理数，则存在素数P，使是的周期；
（2）若T为无理数，则存在各项均为无理数的数列满足，（n=1,2, ）且每个都是的周期 （2008全国高中联赛加试二）

（25）方程的实数解事 （其中表示不超过的最大整数）
（2009福建初赛9）
（26）设，令
（1）S能否等于2010？证明你的结论；
（2）S能取到多少个不同的整数值？
（2009福建初赛14）

（27）设是给定的两个正整数，证明：有无穷多个正整数，使得与互素。
（2009全国高中联赛加试三）

（28）已知集合，其中，，且，若正整数，且，则符合条件的正整数有 个。
（2010福建预赛6）
（29）将方程的实数解从小到大排列得，则的值为
（2010福建预赛8）
（30）设是给定的正整数，，记，。证明：存在正整数，使得为一个整数。这里，表示不小于实数的最小整数。 （2010全国高中联赛加试二）

（31）已知正整数x,y,z满足条件，且，则的最大值为
（2011福建预赛7）
（32）证明：对任意整数存在一个次多项式具有如下性质：
（1）均为正整数；
（2）对任意正整数，及任意个互不相同的正整数均有
（2011全国高中联赛加试二）
（33）证明：存在无穷多个正整数，使得有一个大于的质因子。
（2008第49届IMO.3）
（34）设是一个正整数，是集合中互不相同的整数，使得对于都有整除。
证明：不整除 （2009第50届IMO.1）

本资料主要介绍中学代数课程里未能深入谈到的整数的性质及其应用，初等数论的解题过程通常不涉及很多的基础知识，重要的是机智和灵活。本资料除打上“*”的是少数内容外，初二年以上的学生均可学习掌握。
为叙述方便，本资料中的字母均表示整数。交有Z，N*，Z*分别表示整数集，正整数集和非零整数集。

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

序数表示“第几”*（peano定理）如果非空集合N*中的某些元素之间有一个基本关系“直接后继”（元素a的直接后继记为a’），且N*满足以下条件：
1．，必有
2．
3．
4．N*的子集M若具有下面的性质

定理1 带余除法
设，则有且只有一对整数与，使得其中
定义1、定理1中的与分别称除以的不完全商与最小非负余数，简称商和余数。
定义2、定理1中的时（即时）就称为的倍数，是的约数（或因数）能被整除，整除，记作
性质1、① 0是任何数的倍数（0除外）； ② 是任何数的约束；
③ ； ④ ；
⑤ ； ⑥ ；
⑦ ； ⑧ ；
⑨ ； ⑩

公式1、
公式2、 （是正偶数）
公式3、 （是正奇数）
（以上三个公式中的可以是任意实数）

例1、设（31位数）(1984位数)，求证。
例2、设求证。

定义3、能被2整除的数称偶数，不能被2整除的数称奇数。
性质2、用“0”代表偶数，“1”代表奇数，则有
① 0+0=0,0+1=1，1+0=1,1+1=0 ②00=0,01=0,10=0,11=1
③奇数个奇数的和还是奇数
④任意个奇数之积是奇数
*例3、设都是正奇数，且，求证
注意：奇偶分类在处理很多问题时有用。求末位数问题：
令表示的末位数，则有
性质3、①
②
③
④任一自然数的正整数次幂的末位数有周期变化的规律。
例4、 求的末位数
例5、 ①设为自然数，求证；
②设为自然数，求证
例6、

性质4、①设为奇数，为偶数，则
②设为偶数，为奇数（）则
③设为偶数，为偶数，则
④设为奇数，为奇数，（）则

例7、求
*例8、求的末两位数。
例9、设是这七个自然数的任何一种次序的排列，
求证：总是一个偶数。
例10、某班有49位同学，坐成七行七列，每个座位的前、后、左、右的座位叫做它的“邻座”，要让这49位同学中的每一位都换到他邻座上去，问这种调换座的方案能否实现？

作为本节内容的结束，请注意以下两个重要的命题：
① 在个相邻整数中，有且只有一个数能被整除。
② 若整数，则任一正整数能够唯一表示为
这里，且

习题：
1. 用票面为3分和5分的邮票可以支付任何（整数）分的邮资。
2. 把十个数码0，1,2,3,4……，9任意两两搭配，组成没有重复数码的5个两位数，求证这样5个两位数的和是9的倍数。
3. 设，求证：
4. 设是奇数，求证：
5. 证明：各位数码全是1的数中，有且只有一个是平方数。
6. 证明：前个自然数和的个位数码不能是2,4,7,9
7. 设，求证时奇数的平方。
8. 设，为自然数，是非负整数，求证：的末三位数是189。
9. 证明：整数能够表示成两个整数平方和的充要条件是也具有相同性质。
10. 设整数互不相等，且，求证
11. 设，求证。
12. 设，证明：当且仅当时，。
13. 已知，求证：
14. 证明：在任意个整数中，总可以找到个整数，使它们的和是的倍数。
15. 能否把这些数排成一行，使得两个1之间夹着一个数，两个2之间夹着两个数，……，两个1986之间夹着1986个数？请证明你的结论
（首届全国数学冬令营竞赛试题五）
16. 设正整数不等于，证明集合中可以找到两个不同元素使不是完全平方数 （第27届IMO）

公因数与公倍数
定义1、若就称是这几个数的公因数；
定义2、个不全为零的整数的公因数中的最大数叫做这几个整数的最大公因数，记
性质一：
定义3、若，则称互素（互质）
定义4、若，则称是的公倍数；
定义5、非零整数的一切正的公倍数中的最小正数叫最小公倍数，记
定理1、若不全为零，且则
性质二：
定理2、若
定理3、若整数不全为零，则存在整数使得
性质三：，
性质四：若，则
定理4、若，则
定理5、若是同号整数，则

例1、 形如的数称费尔马数，求证，这里都是非负整数，且
例2、 设且，证明
例3、 已知，求证
例4、 设使非零整系数多项式，，求证
例5、 求证
例6、 设，证明：当且仅当时，
例7、 已知是两两互素的正整数，求证：
例8、 求证平方数的正因数有奇数个，非平方数的正因数有偶数个。
例9、 有一百盏电灯，排成一行，自左向右，编号。每灯由一拉线开关控制，最初灯全关着。另有一百个学生顺次走过，第个学生把凡是编号为的倍数的电灯开关拉一下，问：100个学生全部过去之后，有哪几个编号的灯还亮着？

习题：
1、设表示各位数码都是1的（）位数，求证：
的充要条件是，这里，且
2、设是形如（不全为0）的数中最小正数。
求证：（1）； （2）
3、设，求证
4、设，求证
5、已知：为非零自然数，
求证：（1）；（2）
6、设，证明：数列中的倍数共有个。
7、设，求证
8、已知：，求证
9、设是奇数，，求证
10、设，证明：各位数码全是1的数中有的倍数
11、求证

本节的定义、定理、性质较为繁杂，为便于记忆，整理成以下图式：

素数与合数
自然数集的进一步分类：素数、合数、1
定义 如果大于1的整数恰有两个正因数1与P，就说P是素数，如果正整数N*有多于两个的正因数，就说N*是合数。
例1：证明：对任给的正整数N*，总可找到N*个相邻的合数。

定理一：任一整数N*的最小因数P（P>1）是素数（N*>1）
定理二：素数有无限多个。
定理三：若N*是合数，P（P>1）是N*的最小正因数，则
以上的例子和定理分别刻画了素数的某些分布特征和判断素数的方法。
定理四：若，P是素数，则P整除某个
定理五：（唯一分解定理）每个大于1的整数，都可唯一地分解成素因数（不计因数的顺序）的积。
推论：任一大于1的整数可以唯一分解成这里是相异的素数，是正整数。有时为了表述方便，允许，上式称为的标准分解式。
例2、设是素数，求证：是2的非负整数次幂。
定理六：若得标准分解式为，，
则，。
这里， ，、

例3、求证

定理七：若的标准分解式为，则的一切正因数的个数，的一切正因数的和为。
例4、证明形如的素数有无限个。

哥德巴赫于1742年在和欧拉的通信中提出的猜想：
1． 每个大于5的偶数都是两个奇素数之和
2． 每个大于8的奇数都是三个奇素数之和
1973年5月《中国科学》杂志刊出陈景润研究G氐猜想的结果：
“任一充分大的偶数是一个素数和另一个素数的和，后者或为素数，或仅另两个素数的乘积。”
此定理被简称为“1+2”当然离“1+1”还有一段距离，不过这已经是当今最优成果了。

习题：
1、 设是异于3的奇素数，求证
2、 设是素数，且，求证
3、 设整数都大于1，证明
4、 求证：
5、 设都是大于1，是素数，求证：，且是素数
6、 从1到100这100个自然数中，任意选出51个数，求证其中至少有两个数，它们中的一个是另一个的倍数。
7、 设，证明
8、 证明：形如的素数有无限多个。
9、 设，证明：在与之间至少有一个素数。
10、设是表示由小到大排列的第个素数，证明

同余
定义 给定正整数m，如果用它除任意两个整数a,b，所得余数相同，就说a,b对于模m同余，记作。若所得余数不同，就说a,b对于模m不同余，记作。
定理与性质

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

习题
1. 设，求证：。
2. 设，求证：。
3. 设ABCDE是按逆时针方向排列的五角棋盘，从A沿逆时针方向移动棋子，第K次移动K步，证明无论移动多少次，C、E处永远不可能停留棋子。
4. 设，P是素数，求证。
5. 证明。
6. 设，，求证。
7. 已知，求证n不能表为3个立方数的和。
8. 已知，求证n不能表为3个平方数的和。
9．求出一个整数能被101（或37）整除的充要条件。
10．求下列各数的末两位数：和。
11．记，且，求a。
12．已知，求a、b、c。

补充题：
1. （1）有几个住鞥书，其积为n，其和为零。求证4 | n 。
（2）设4 | n，求证：可以找出几个整数，使其积为n，其和为零。
（十八届全苏中学生竞赛）
2. 设a，b，c是三个互不相等的正整数，求证：在，，三个数中，至少有一个数能被10整除。
（86. 全国初中联赛，二试，四）
3. 把19,20，…，79,80诸数连写成数A=192021…7980，试证1980 | A。
（全苏14届 1980.8.1）
4. 试求所有能被11整除的三位数，且除得之商等于被除数中各数字的平方和。
（二届IMO 1960）

不定方程
若方程或方程组中未知数的个数多于方程的个数，它们的解又限制为正整数、整数、有理数或其它类别的数，则称此方程或方程组为不定方程。不定方程常联系到一些有趣的问题。竞赛中也时有所见。
例1 在等式中还原数学x, y, z。（1987年全俄中学生竞赛题）
例2 解方程。（1978年广东省中学数学竞赛题）
例3 求方程满足条件：的整数解。（1979年湖南省中学数学竞赛题）
数论函数
定义1 设x为任一实数，表示不超过x的最大整数。
函数称数论函数，也称高斯函数、阶梯函数等。数论问题是竞赛中的热门课题，而则是热门中的热门。
由定义，显然有①；②。
定义2 称为x的小数部分，显然。
例1 计算。
例2 求。
例3 解方程。
例4 已知方程，求所有根的和。（1987年初中联考）
习题
1. 。
2. 。
3. 。（英斯科第20届奥林匹克数学竞赛题）
有时也常令通过对的讨论来解题。

例5 方程的实数解的个数是（ ）。（1985美国数学竞赛题）
(A) 0 ; (B) 1 ; (C) 2 ; (D) 3 ; (E) 4 .
例6 记表示不超过x的最大整数，设n是自然数，且
，那么（ ）。（1986年全国初中联考）
（A）I > 0 ; （B）I < 0 ; （C）I = 0 ;
（D）当n取不同的值时，以上三种情况都有可能出现
例7 求正数x ，使得。
性质1 是不减函数。
性质2 当且仅当时成立。
性质3 对任意实数x 、y ，有。
性质4 设m 、n为正整数，在数列1，2，…，（n-1），n 中，m的倍数有个。
定理 设p为一素数，在n! 中p的方次数等于
例8 在的十进制展开中，以多少个0为结尾？

例9 求证方程无实数解。

例10 设N为一正整数，问方程在区间中有多少个解？（1982年瑞典数学竞赛题）
例11 试决定的小数点前一位数字和后一位数字。（1980年芬兰等欧洲四国数学竞赛题）
例12 在整数列中，含有多少个互不相等的自然数？（1980苏联列宁格勒中学生数学竞赛试题）

习题
1． 设，（其中）。则一定有（ ）
（1985年北京市中学生数学竞赛高一年试题）
（A）M>N ; (B) M=N ; (C) M<N ; (D) 以上答案都不对
2．设，那么的值是
3． ①找出一个实数x，满足；
②证明，满足上述等式的x都不是有理数。
4． 设，计算和。（1968第十届IMO）
5． 设a , b为互素的正整数，求证：。

6． 求所有自然数n , 使得，这里表示不超过的最大整数，N是自然数集。（1991年中国数学奥林匹克）
不定方程
若方程或方程组中未知数的个数多于方程的个数，它们的解又限制为正整数、整数、有理数或其它类别的数，则称此方程或方程组为不定方程。不定方程联系到一些有趣的问题。竞赛中也时有所见。
例1．在等式中还原数字x,y,z.(1987全俄中学生竞赛题)
例2．解方程：
例3．求方程满足条件：的整数解。
（1979年湖南省中学数学竞赛题）
线性不定方程
定理1 设，则线性不定方程有整数解的充要条件是。在有整数解的情形下，如果，是一组整数解，那么该方程的一切整数解（简称通解）可以写成

例 4 求方程的整数解。
例5 今有物，不知其数（百个以下）。三三数之，剩二；五五数之，剩三；七七数之，剩二。问物几何？（该题目出自1600年前的《孙子算经》）

“韩信点兵”或“秦王暗点兵”的歌诀：
“三岁孩儿七十稀，五留廿一事尤奇，七度上元重相会，寒食清明便可知。”
注：该诀出自宋朝周密，“上元”指15，“寒食清明”指105，每年冬至至次年清明正好105天。

“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。”
注：该诀出自明朝程大位《算法统宗》。
定理2 勾股不定方程满足，的一切整数解可表示为，这里，，中一个为奇数，另一个为偶数。
例6 设，证明方程有正整数解。

例7 证明不定方程没有正整数解。
费马猜想：整数时，方程 无正整数解是数论中的一个著名的难题。1760年欧拉证明了n = 3 的情形。1828年勒让德余狄里赫勒各自证明了n = 5的情形。1840年拉梅证明n = 7的情形。库莫尔于1844年首创“理想数论”，并利用这个工具一举证明了n是小于100的奇素数但除去n=37,59,67的情形.1892年米利曼诺夫证明了n=37的情形。1978瓦格斯塔夫借助大型电子计算机证明了2 < n < 125000的情形。…………29岁的讲师又对此做出了重大发展，然而至今还无法宣布此猜想是一条定理。

例8 确定（并加以证明）方程所有的整数解。（1976年美国竞赛题）

例9 证明方程只有唯一的有理数解。
例10 正整数与使得整除。求证是某个正整数的平方。（1988年第29届IMO）
习题
1. 不定方程是否有整数解？
2. 方程有多少组正整数解？
3. 求方程的整数解（）。
4. 求方程的整数解。