高中数学竞赛专题讲座竞赛中的数论问题

数学竞赛中的数论问题引言数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支．什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，…是这样一个集合N +：（1）有一个最小的数1．（2）每一个数a 的后面都有且只有一个后继数/a ；除1之外，每一个数的都是且只是一个数的后继数．这个结构很像数学归纳法，事实上，有这样的归纳公理：（3）对N +的子集M ，若1M ∈，且当a M ∈时，有后继数/a M ∈，则M N +=． 就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度．比如，哥德巴赫猜想：1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和”．后者是前者的推论，也可独立证明（已解决）．“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1．欧拉认为这是对的，但证不出来．1900年希尔伯特将其归入23个问题中的第8个问题．1966年陈景润证得：一个素数+素数⨯素数（1+2），至今仍无人超越．●陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠．……”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥．●数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了．任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（U ．Dudley 《数论基础》前言）．下面，是一个有趣的故事．当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有1n +个正整数，这些正整数小于或等于2n ，那么你一定有一对整数是互素的，你知道这是什么原因吗？不到12岁的波萨只用了1分半钟，就给出了问题的解答．他将1～2n 分成（1，2），（3，4），…，（21,2n n -）共n 个抽屉，手头的1n +个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素．通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”．●重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）．高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题．数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目．数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程．在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x ]，费马小定理，格点及其性质，无穷递降法，欧拉定理*，孙子定理*．根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型：（1）奇数与偶数（奇偶分析法、01法）；（2）约数与倍数、素数与合数；（3）平方数；（4）整除；（5）同余；（6）不定方程；（7）数论函数、[]x 高斯函数、()n ϕ欧拉函数；（8）进位制（十进制、二进制）．下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解．第一讲 数论题的基本内容中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理．首先约定，本文中的字母均表示整数．定义1 （带余除法）给定整数,,0,a b b ≠如果有整数(),0q r r b ≤<满足a qb r =+，则q 和r 分别称为a 除以b 的商和余数．特别的，0r =时，则称a 被b 整除，记作b a ，或者说a 是b 的倍数，而b 是a 的约数．（,q r 的存在性由定理1证明）定义2 （最大公约数）设整数12,,,n a a a 中至少有一个不等于零，这n 个数的最大公约数是能整除其中每一个整数的最大正整数，记作()12,,,n a a a ．()12,,,n a a a 中的i a 没有顺序，最大公约数也称最大公因数．简单性质：()()1212,,,,,,n n a a a a a a = ．一个功能：可以把对整数的研究转化为对非负整数的研究．定义3 （最小公倍数）非零整数12,,,n a a a 的最小公倍数是能被其中每一个()1i a i n ≤≤所整除的最小正整数，记作[]12,,,n a a a ．简单性质：如果k 是正整数,a b 的公倍数，则存在正整数m 使[],k ma b = 证明：定义4 如果整数,a b 满足(),1a b =，则称a 与b 是互素的（也称互质）．定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）．其余大于1的正整数称为合数；数1既不是素数也不是合数．定理1 若,a b 是两个整数，0b >，则存在两个实数,q r ，使()0a qb r r b =+≤<，并且,q r 是唯一性．证明1：注：如果取消0r b ≤<，当0r <或r b >，不保证唯一．经典方法：紧扣定义，构造法证存在性，反证法证唯一性．证明2：证明3：定理 2 设,,a b c 是三个不全为0的整数，满足a qb c =+，其中q 也为整数，则()(),,a b b c =．证明：注：这是辗转相除法求最大公约数的理论基础．经典方法：要证明A B =，只需证A B ⊆且B A ⊆．定理3 对任意的正整数,a b ，有()[],,a b a b ab ⋅=．证明：定理4 ,a b 是两个不同时为0的整数，若00ax by +是形如ax by +（,x y 是任意整数）的数中的最小正数，则（1）00ax by +|ax by +；（2）00ax by +(),a b =．证明：推论 若(),1a b =，则存在整数,s t ，使1as bt +=．（很有用）定理5 互素的简单性质：（1）()1,1a =．（2）(),11n n +=．（3）()21,211n n -+=．（4）若p 是一个素数，a 是任意一个整数，且a 不能被p 整除，则(),1a p =． 证明：推论 若p 是一个素数，a 是任意一个整数，则(),1a p =或(),a p p =．（5）若(),1a b =，则存在整数,s t ，使1as bt +=．（定理4推论）（6）若()(),1,,1a b a c ==，则(),1a bc =．证明：（7）若(),1a b =，则(),1a b a ±=，(),1a b b ±=， (),1a b ab ±=．证明：（8）若(),1a b =，则(),1m n a b =，其中,m n 为正整数． 证明：定理6 设a 是大于1的整数，则a 的除1之外的最小的正约数q 必是素数，且当a 是合数时，q ≤证明：定理7 素数有无穷多个，2是唯一的偶素数．证明：注：这个证明中，包含着数学归纳法的早期因素：若假设有n 个素数，便有1n +个素数．（构造法、反证法）定理8（整除的性质）整数,,a b c 通常指非零整数（1）1a ，1|a -；当0a ≠时，|a a ，|0a ．（2）若b a ，0a ≠，则b a ≤;若b a ，b a >，则0a =;若0ab >，且,b a a b ，则a b =．证明：（3）若a b c d +=+，且|,|,|e a e b e c ，则|e d ．（4）若c b ，b a ，则c a ．证明：（5）若c a ，则bc ab ．（6）若c a ，c b ，则对任意整数,m n ，有c ma nb +．证明：（7）若(),1a b =，且a bc ，则a c ．证明：注意 不能由a bc 且|a b /得出a c ．如649⨯，但6|4/且6|9/．（8）若(),1a b =，且,a c b c ，则ab c ．证明：注意 不能由a c 且b c 得出ab c ．如不能由630且10|30得出60|30．（9）若a 为素数，且a bc ，则a b 或a c ．证明：注意 没有a 为素数，不能由a bc 推出a b 或a c ．如649⨯，但6|4/且6|9/． 定义6 对于整数,,a b c ，且0c ≠，若()c a b -，则称,a b 关于模c 同余，记作(mod )a b c ≡；若()|c a b -/，则称,a b 关于模c 不同余，记作a(mod )b c ．定理9（同余的性质）设,,,,a b c d m 为整数，0,m >（1）若(mod )a b m ≡且(mod )b c m ≡，则(mod )a c m ≡；证明： （2）若(m o d )a b m ≡且(mod )c d m ≡，则(m o d )a c b d m +≡+且(mod )ac bd m ≡．证明：（3）若(m o d )a b m ≡，则对任意的正整数n 有(mod )n na b m =且(mod )an bn mn ≡. （4）若(mod )a b m ≡，且对非零整数k 有(,,)k a b m ，则mod a b m k k k ⎛⎫= ⎪⎝⎭． 证明：定理10 设,a b 为整数，n 为正整数，（1）若a b ≠，则()()n n a b a b --． ()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++ ．（2）若a b ≠-，则()()2121n n a b a b --++．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+ ．（3）若a b ≠-，则()()22n n a b a b +-．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+- ．定义7 设n 为正整数，k 为大于2的正整数, 12,,,m a a a 是小于k 的非负整数，且10a >．若12121m m m m n a k a k a k a ---=++++ ， 则称数12m a a a 为n 的k 进制表示．定理11 给定整数2k ≥，对任意的正整数n ，都有唯一的k 进制表示．如12121101010m m m m n a a a a ---=++++ ，109,0i a a ≤≤>（10进制）12121222m m m m n a a a a ---=++++ ．101,0i a a ≤≤>（２进制）定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的1212k k n p p p ααα= ，其中12k p p p <<< 为素数，12,,,k ααα 为正整数． （分解唯一性） 证明1：证明2：定理13 若正整数n 的素数分解式为 1212k k n p p p ααα= 则n 的正约数的个数为()()()()12111k d n a a a =+++ ，n 的一切正约数之和为()121111212111111k k k p p p S n p p p ααα+++---=⋅⋅⋅--- ． 证明：注 构造法．定义8 （高斯函数）对任意实数x ，[]x 是不超过x 的最大整数．亦称[]x 为x 的整数部分，[][]1x x x ≤<+．定理14 在正整数!n 的素因子分解式中，素数p 作为因子出现的次数是 23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦． 证明：注 省略号其实是有限项之和．画线示意50!中2的指数．35678912450!23571113171923293137414347ααααααααα==定理15 （费玛小定理）如果素数p 不能整除整数a ，则()11p p a --． 证明1：证明2：定义9 （欧拉函数）用()n ϕ表示不大于n 且与n 互素的正整数个数．定理16 设正整数1212k k n p p p ααα= ，则()12111111k n n p p p ϕ⎛⎫⎛⎫⎛⎫=--- ⎪ ⎪⎪⎝⎭⎝⎭⎝⎭ ． 证明：注 示意3n =的容斥原理．推论 对素数p 有()()11,p p p p p αααϕϕ-=-=-． 定理17 整系数不定方程ax by c +=（0ab ≠）存在整数解的充分必要条件是(),a b c ．证明：定理18 若0ab ≠,(),1a b =，且00,,x x y y =⎧⎨=⎩是整系数不定方程ax by c +=的一个整数解，则方程的一切整数解可以表示为00,,x x bt y y at =-⎧⎨=+⎩()t Z ∈． ① 证明：定义10 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）．类似地可以定义空间整点．。

高中数学奥赛竞赛题选讲1. 引言高中数学奥赛竞赛是一项通过解决复杂、富有挑战性的数学问题来培养学生创造力和解决问题能力的活动。

本文将介绍一些常见的高中数学奥赛竞赛题目，并提供详细的解答和解题思路，帮助读者更好地理解和应用其中的数学知识。

2. 数论2.1 素数与因子分解2.1.1 素数的定义和性质•介绍素数和合数的概念及其区别•讨论素数的性质：只有两个因子为1和自身2.1.2 因子分解与最大公因数、最小公倍数•解释因子分解的概念，例如将一个整数表示为其所有素因子相乘的形式•解释最大公因数(GCD)和最小公倍数(LCM)的概念，并给出计算方法2.2 同余定理与剩余类方程2.2.1 同余定理的基本原理•引入同余符号和模运算的概念，例如"a ≡ b (mod m)" 表示"a"与"b"在模m下同余•介绍同余定理的基本原理和性质2.2.2 解决线性同余方程组的方法•引入线性同余方程组的概念，例如：•a₁x ≡ b₁ (mod m₁)•a₂x ≡ b₂ (mod m₂)•提供解决线性同余方程组的方法，如中国剩余定理2.3 数论函数及其应用2.3.1 欧拉函数•定义欧拉函数φ(n)，表示小于等于n且与n互质的正整数个数。

•给出计算欧拉函数值的方法2.3.2 应用：费马小定理、欧拉定理与RSA加密算法•介绍费马小定理和欧拉定理，并给出证明过程•讨论RSA加密算法的基本原理和步骤3. 解析几何与三角函数的应用3.1 直线与曲线方程3.1.1 直线的一般方程和截距式方程•解释直线一般方程(Ax + By + C = 0)和截距式方程(x/a + y/b =1)的含义及其转换关系•给出构造直线方程的方法和示例3.1.2 平行线和垂直线的性质及判定•讨论平行线和垂直线的定义和性质•提供判定两条直线平行或垂直的方法3.2 三角函数3.2.1 常见三角函数及其基本性质•介绍正弦、余弦、正切等常见三角函数的定义和性质•解释三角函数在单位圆上的几何意义3.2.2 角度与弧度制之间的转换•讲解角度制和弧度制之间的转换关系3.3 三角函数与几何应用3.3.1 正弦定理与余弦定理•引入正弦定理(a/sinA = b/sinB = c/sinC)和余弦定理(c²=a²+b²−2abcosC)的概念•解释如何运用这些公式求解三角形边长和角度3.3.2 应用：海伦公式和面积公式•引入海伦公式(面积S=sqrt(s(s-a)(s-b)(s-c)))以及面积公式(三角形面积S=1/2 * a * b * sinC)的概念•提供应用海伦公式和面积公式求解三角形面积的问题4. 组合数学与概率论4.1 排列与组合4.1.1 排列和组合的基本概念•解释排列(permutation)和组合(combination)的定义和区别•讲解计算排列数和组合数的方法4.1.2 应用：鸽笼原理•引入鸽笼原理及其基本思想，并提供应用示例4.2 概率论4.2.1 基本概率计算方法与条件概率•讲解基本事件和复合事件的概念，以及如何计算它们的概率•解释条件概率及其计算方法4.2.2 应用：排列组合与概率问题•提供运用排列组合知识解决实际生活中的概率问题的示例5. 数学建模与实际问题求解思路5.1 数学建模方法论与实例分析5.1.1 数学建模基本步骤•阐述从现实问题到数学模型的转化过程，包括定义目标、收集数据、制定假设等步骤•提供一个数学建模的实例分析5.2 实际问题求解思路5.2.1 利用数学工具和方法解决实际问题•强调在解决实际问题时，应根据具体情况选择合适的数学工具和方法•提供一个简单实际问题的求解思路示例结语本文对高中数学奥赛竞赛题选讲进行了详细介绍，涵盖了数论、解析几何与三角函数、组合数学与概率论以及数学建模等方面内容。

解：令（）。

若中有一个数被m 整除，则结论成立。

i i a a a b +++= 21m i ,,2,1 =m b b b ,,,21 否则，各均不能被m 整除，此时可设。

这样，m 个余数i b )11(-≤≤+=m r r mq b i i i i 只能从1至m -1这m -1个数中取值，由抽屉原理知，必有，使得m r r r ,,,21 )1(,m j k j k ≤<≤，于是，故取即得到结论。

j k r r =)(k j k j q q m b b -=-)()(|21j k k k j a a a b b m +++=-++ 1+=k s 3. 互素性的条件当（a ，b ）=d >1时，我们总是作如下考虑：令，则必有。

这种互素d b b d a a 11,==1),(11=b a 条件的增置往往对解题有很大作用。

例7. （波兰64—65）设整数a ，b 满足，试证及都是完全平方数。

b b a a +=+2232b a -122++b a 解：变形可得：，故只要能证一个，则另一个必是。

我b b a a +=+22322)122)((b b a b a =++-们在排除了字母取零或相等的情况后，可设。

这时令，d b a b a b a =≠≠),(,,0,d b b d a a 11,==，从而方程变为。

显然有。

另一方面又1),(11=b a 21112132db b a da =-+)(|11b a d -212111(223d da db b a -=-=-，有。

注意到，于是有21212121211)(223db b a d da db b +--=-=2111|)(db b a -1),(),(11111==-b a b b a 。

这样就有。

至此已十分容易获得命题的结论了。

这里，由a 1与b 1互素导出d b a |)(11-||11b a d -=a 1—b 1与b 1互素，是证明的关键。

高中数学竞赛课程讲座：初等数论
本课程讲座旨在介绍初等数论的基础知识，帮助学生为高中数学竞赛做最好的准备。

我们将深入探讨数论中的基础概念，如质数分解和
算术难题，并探讨一些实际应用的技巧和常用方法，帮助学生在数学
竞赛中取得好成绩。

本次讲座将向您介绍初等数论，它是一门关于形式化、有限数论等术语和方法的数学分支。

简而言之，初等数论在研究有关有限结构的
问题和计算方法时是不可或缺的。

在这个课程中，我们将探讨整数质
因数分解、质数及其应用、素数概念、余数定理、线性算术等，帮助
您为数学竞赛中的第一题做准备。

我们还将深入讨论有关如何构造有
限结构的问题，利用它们来探究多项式的性质；研究几何图形；通过
图论剖析算法，及解决整数方程组等方面的相关内容。

我们相信您在
学习初等数论时会有所收获，从而在高中数学竞赛中尽显实力！
此外，我们还将为您介绍数论的发展和历史，例如，古希腊的Euclid
的元素书、中国的Sunzi的求积算，以及17世纪的Fermat的大定理等，一起探究中国数学家在数论中的贡献。

在讲座中，我们还会解释完整
的幂的概念，从中分析总结出幂的工具，比如抽象代数和提高多项式
的方法等，以帮助您从大量的幂等式中获取实质性的知识，理清思路。

最后，在考试期间，我们将重点讨论质因数分解原理、构造，以及如
何将数论应用于实际情况中，例如Cryptography，帮助您在考试中取得高分。

数学竞赛中的数论问题定理4 ,a b 是两个不同时为0的整数，若00ax by +是形如ax by +（,x y 是任意整数）的数中的最小正数，则（1）00ax by +|ax by +；（2）00ax by +(),a b =．证明 （1）由带余除法有()00ax by ax by q r +=++，000r ax by ≤<+， 得 ()()0000r a x qx x b y qy ax by =-+-<+，知r 也是形如ax by +的非负数，但00ax by +是形如ax by +的数中的最小正数，故0r =，即00ax by +|ax by +． （2）由（1）有00ax by +|10a b a +=g g ，00ax by +|01a b b +=g g ，得00ax by +是,a b 的公约数．另一方面，,a b 的每一个公约数都可以整除00ax by +，所以00ax by +是,a b 的最大公约数，00ax by +(),a b =．推论 若(),1a b =，则存在整数,s t ，使1as bt +=．（很有用）定理5 互素的简单性质： （1）()1,1a =．（2）(),11n n +=．（3）()21,211n n -+=． （4）若p 是一个素数，a 是任意一个整数，且a 不能被p 整除，则(),1a p =． 推论 若p 是一个素数，a 是任意一个整数，则(),1a p =或(),a p p =． （6）若()(),1,,1a b a c ==，则(),1a bc =．证明 由(),1a b =知存在整数,s t ，使1as bt +=．有 ()a cs bct c +=，得 ()(),,1a bc a c ==． （7）若(),1a b =，则(),1a b a ±=，(),1a b b ±=， (),1a b ab ±=．证明 ()()(),,,1a b a b a b a ±=±==，()(),,1a b b a b ±==，由（6）(),1a b ab ±=． （8）若(),1a b =，则(),1m n a b =，其中,m n 为正整数．证明 据（6），由(),1a b =可得(),1m a b =．同样，由(),1m a b =可得(),1m n a b =． 定理7 素数有无穷多个，2是唯一的偶素数．证明 假设素数只有有限多个，记为12,,,n p p p L ，作一个新数 1211n p p p p =+>g gL g ． 若p 为素数，则与素数只有 n 个12,,,n p p p L 矛盾．若p 为合数，则必有{}12,,,i n p p p p ∈L ，使|i p p ，从而|1i p ，又与1i p >矛盾． 综上所述，素数不能只有有限多个，所以素数有无穷多个． 2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．注：这个证明中，包含着数学归纳法的早期因素：若假设有n 个素数，便有1n +个素数．（构造法、反证法）定理8（整除的性质）整数,,a b c 通常指非零整数 （1）1a ，1|a -；当0a ≠时，|a a ，|0a ．（2）若b a ，0a ≠，则b a ≤;若b a ，b a >，则0a =;若0ab >，且,b a a b ，则a b =．证明 由b a ，0a ≠，有a bq =，得a b q b =≥．逆反命题成立“若b a ，b a >，则0a =”; 由b a ≤且b a ≥得a b =，又0ab >，得a b =． （7）若(),1a b =，且a bc ，则a c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有()()a cs bc t c +=， 因为a a ，a bc ，所以a 整除等式的左边，进而整除等式的右边，即a c ．（8）若(),1a b =，且,a c b c ，则ab c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有acs bct c +=，又由,a c b c 有12,c aq c bq ==代入得()()21ab q s ab q t c +=，所以ab c ．注意 不能由a c 且b c 得出ab c ．如不能由630且10|30得出60|30． （9）若a 为素数，且a bc ，则a b 或a c ．证明 若不然，则|a b /且|a c /，由a 为素数得()(),1,,1a b a c ==，由互素的性质（6）得(),1a bc =，再由a 为素数得|a bc /，与a bc 矛盾．定义6 对于整数,,a b c ，且0c ≠，若()c a b -，则称,a b 关于模c 同余，记作(mod )a b c ≡；若()|c a b -/，则称,a b 关于模c 不同余，记作a(mod )b c ．定理9（同余的性质）设,,,,a b c d m 为整数，0,m >若(mod )a b m ≡且(mod )c d m ≡，则(mod )a c b d m +≡+且(mod )ac bd m ≡．证明 由(mod )a b m ≡且(mod )c d m ≡，有12,a b mq c d mq -=-=， ① 对①直接相加 ，有()()()12a c b d m q q +-+=+，得 (mod )a c b d m +≡+.对①分别乘以,c b 后相加，有()()()12ac bd ac bc bc bd m cq bq -=---=+，得 (mod )ac bd m ≡． （3）若(mod )a b m ≡，则对任意的正整数n 有(mod )nna b m =且(mod )an bn mn ≡.（4）若(mod )a b m ≡，且对非零整数k 有(,,)k a b m ，则mod a b m k k k ⎛⎫= ⎪⎝⎭． 证明 由(mod )a b m ≡、，有 a b mq =+，又(,,)k a b m ，有,,a b mk k k均为整数，且 a b mq k k k=+，得 mod a b m k k k ⎛⎫≡ ⎪⎝⎭．定理10 设,a b 为整数，n 为正整数， （1）若a b ≠，则()()nna b a b--．()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++L ．（2）若a b ≠-，则()()2121n n a b ab --++．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+L ．（3）若a b ≠-，则()()22nn a b ab +-．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+-L ．定义7 设n 为正整数，k 为大于2的正整数, 12,,,m a a a L 是小于k 的非负整数，且10a >．若 12121m m m m n a ka k a k a ---=++++L ，则称数12m a a a L 为n 的k 进制表示．定理11 给定整数2k ≥，对任意的正整数n ，都有唯一的k 进制表示．如12121101010m m m m n a a a a ---=++++L ，109,0i a a ≤≤>（10进制） 12121222m m m m n a a a a ---=++++L ．101,0i a a ≤≤>（２进制）定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的1212kkn p p p ααα=L ，其中12k p p p <<<L 为素数，12,,,k αααL 为正整数． （分解唯一性）定理13 若正整数n 的素数分解式为 1212kkn p p p ααα=L 则n 的正约数的个数为()()()()12111k d n a a a =+++L ，n 的一切正约数之和为 ()121111212111111k k k p p p S n p p p ααα+++---=⋅⋅⋅---L ． 证明 对于正整数1212kk n p p p ααα=L ，它的任意一个正约数可以表示为1212kkm p p p βββ=L ，0i i βα≤≤ ， ①由于i β有0,1,2,,i αL 共1i α+种取值，据乘法原理得n 的约数的个数为()()()()12111k d n a a a =+++L ．考虑乘积()()()12010101111222k k k k p p p pp p p p p ααα+++++++++L L L L ， 展开式的每一项都是n 的某一个约数（参见①），反之，n 的每一个约数都是展开式的某一项，于是，n 的一切约数之和为()()()11101111kk kS n p p p pp p αα=++++++L L L 121111212111111k k k p p p p p p ααα+++---=⋅⋅⋅---L ． 注 构造法．定义8 （高斯函数）对任意实数x ，[]x 是不超过x 的最大整数．亦称[]x 为x 的整数部分，[][]1x x x ≤<+． 定理14 在正整数!n 的素因子分解式中，素数p 作为因子出现的次数是 23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦L ． 证明 由于p 为素数，故在!n 中p 的次方数是1,2,,n L 各数中p 的次方数的总和（注意，若p 不为素数，这句话不成立）．在1,2,,n L 中，有n p ⎡⎤⎢⎥⎣⎦个p 的倍数；在n p ⎡⎤⎢⎥⎣⎦个p 的倍数的因式中，有2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数；在2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数的因式中，有3n p ⎡⎤⎢⎥⎣⎦个3p 的倍数；…，如此下去，在正整数!n 的素因子分解式中，素数p 作为因子出现的次数就为23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦L ．注 省略号其实是有限项之和． 定理15 （费玛小定理）如果素数p 不能整除整数a ，则()11p p a--．证明2 改证等价命题：如果素数p 不能整除整数a ，则()mod pa a p ≡． 只需对1,2,,1a p =-L 证明成立，用数学归纳法． （1）1a =，命题显然成立．（2）假设命题对()11a k k p =≤<-成立，则当1a k =+时，由于()|1,2,,1ip p C i p =-L ，故有()11111ppp p p p k k C kC k --+=++++L ()11mod p k k p ≡+≡+．（用了归纳假设） 这表明，命题对1a k =+是成立． 由数学归纳法得()mod pa a p ≡．又素数p 不能整除整数a ，有(),1a p =，得()11p p a--．定义9 （欧拉函数）用()n ϕ表示不大于n 且与n 互素的正整数个数． 定理16 设正整数1212kkn p p p ααα=L ，则 ()12111111k n n p p p ϕ⎛⎫⎛⎫⎛⎫=--- ⎪ ⎪⎪⎝⎭⎝⎭⎝⎭L ． 推论 对素数p 有()()11,p p p pp αααϕϕ-=-=-．．第二讲 数论题的范例讲解（12）()()()()()()22220mod 4,211mod 4,211mod8n n n ≡-≡-≡． （13）任何整数都可以表示为()221m n k =-．例1-1（1986，英国）设127,,,a a a L 是整数，127,,,b b b L 是它们的一个排列，证明()()()112277a b a b a b ---L 是偶数．（127,,,a a a L 中奇数与偶数个数不等）例1-2 π的前24位数字为 3.14159265358979323846264π=，记1224,,,a a a L 为该24个数字的任一排列，求证()()()12342324a a a a a a ---L 必为偶数．（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等）例2 能否从1,2,,15L 中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为1,2,,14L ？解 考虑14个差的和S ，一方面1214105S =+++=L 为奇数．另一方面，每两个数,a b 的差与其和有相同的奇偶性 (mod2)a b a b -≡+，因此，14个差的和S 的奇偶性与14个相应数之和的和/S 的奇偶性相同，由于图中的每一个数a 与2个或4个圈中的数相加，对/S 的贡献为2a 或4a ，从而/S 为偶数，这与S 为奇数矛盾，所以不能按要求给图中的圆圈填数．评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在反证法中，计算两次又可用来构成矛盾．例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？解 （1）4堆是不能保证的．如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）．（2）5堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数．例4 有n 个数121,,,,n n x x x x -L ，它们中的每一个要么是1，要么是1-．若1223110n n n x x x x x x x x -+++++=L L ，求证4|n ．证明 由{}1,1i x ∈-，有{}11,1i i x x +∈-，再由1223110n n n x x x x x x x x -+++++=L L ， 知n 个1i i x x +中有一半是1，有一半是1-，n 必为偶数，设2n k =．现把n 个1i i x x +相乘，有2222122311121(1)(1)1k kn n n n n x x x x x x x x x x x x ---+===g gL g g g L g ，可见，k 为偶数，设2k m =，有4n m =，得证4|n ．例6 在数轴上给定两点1，在区间内任取n 个点，在此2n +个点中，每相邻两点连一线段，可得1n +条互不重叠的线段，证明在此1n +条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．证明 将2n +个点按从小到大的顺序记为122,,,n A A A +…，并在每一点赋予数值i a ，使1, 1,i i i A a A ⎧=⎨-⎩当为有理数点时，　当为无理数点时.与此同时，每条线段1i i A A +也可数字化为1i i a a +（乘法） 1111,, 1,,i i i i i i A A a a A A +++-⎧=⎨⎩　当一为有理数点，另一为无理数时， 当同为有理数点或无理数点时,记11i i a a +=-的线段有k 条，一方面112233412()()()()(1)(1)(1)k n k k n n a a a a a a a a -+++=-+=-... 另一方面 12233412()()()()n n a a a a a a a a ++ (2)1231212()1n n n a a a a a a a -++===-…，得()11k-=-，故k 为奇数．评析 用了数字化、奇偶分析的技巧． 二、约数与倍数最大公约数与最小公倍数的求法． （1） 短除法．（2）分解质因数法．设1212,0,1,2,,k k i a p p p i k αααα=≥=L L ，1212,0,1,2,,k k i b p p p i k ββββ=≥=L L ．记 {}{}min ,,max ,i i i i i i γαβδαβ==，则 ()1212,k k a b p p p γγγ=L ，[]1212,k k a b p p p δδδ=L ．（3）辗转相除法 ()()()()()121,,,,,0n n n n a b b r r r r r r r -======L ． 例7 （1）求()8381,1015，[]8381,1015； （2）()144,180,108，[]144,180,108．解（1）方法1 分解质因数法．由283811729,10155729,=⨯=⨯⨯得()8381,101529=，[]28381,1015571729293335=⨯⨯⨯=． 方法2 辗转相除法．或 ()()()()()8381,1015261,1015261,23229,23229,029=====．[]()83811015838110158381,10158381352933358381,101529⨯⨯===⨯=．（2）方法1 短除法．由()22144,180,1082336=⨯=，得2144 180 108272 90 54336 30 27312 10 9 4 5 3[]43144,180,1082352160=⨯⨯=．方法2 分解质因数法．由42222314423,180235,10823,=⨯=⨯⨯=⨯，得 ()22144,180,1082336=⨯=，[]43144,180,1082352160=⨯⨯=．例8 正整数n 分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n 的最小值为 ． 解 依题意，对最小的n ，则1n +是2,3,4,5,6,7,8,9,10的公倍数3212357n +=⨯⨯⨯，得2519n =． 例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？ 解 相当于求不定方程15276x y +=的整数解．由()15,273=知，存在整数,u v ，使15273u v +=，可得一个解2,1u v ==-，从而方程 ()1542726⨯+⨯-=．即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升．例10 对每一个2n ≥，求证存在n 个互不相同的正整数12,,,n a a a L ，使i j i j a a a a -+，对任意的{},1,2,,,i j n i j ∈≠L 成立．证明 用数学归纳法．当2n =时，取121,2a a ==，命题显然成立．假设n k =时，命题成立，即存在12,,,k a a a L ，使 i j i j a a a a -+，对任意的{},1,2,,,i j k i j ∈≠L 成立． 现取b 为12,,,k a a a L 及它们每两个数之差的最小公倍数，则1k +个数12,,,,k b a b a b a b +++L 满足 ()()()()()(),,t t ij i j a b b a b b a b a b a b a b ⎧+-++⎪⎨+-++++⎪⎩即命题对1n k =+时成立．由数学归纳法知命题对2n ≥成立．例11 ()111959,IMO -证明对任意正整数n ，分数214143n n ++不可约．证明1 （反证法）假若214143n n ++可约，则存在1d >， ①使 ()214,143n n d ++=，从而存在(),,,1p q p q =，使214, 143, n dp n dq +=⎧⎨+=⎩②③消去n ，()()3322⨯-⨯，得 ()132d q p =-， ④的 1d =． ⑤由（1）、（5）矛盾，得1d =． 解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法．（2）式④是实质性的进展，表明 ()()131432214n n =+-+，可见 ()214,1431n n ++=．由此获得2个解法． 证明2 设()214,143n n d ++=．存在(),,,1p q p q =，使214, 143, n dp n dq +=⎧⎨+=⎩①② 消去n ，②×3-①×2，得()132d q p =- ③ 得 1d =．证明3 由()()131432214n n =+-+ 得 ()214,1431n n ++=．证明4 ()214,143n n ++ ()71,143n n =++ ④()71,1n =+ ⑤ 1=． 解题分析：第④ 相当于 ①-②；第⑤ 相当于②-2（①-②）=②×3-①×2；所以③式与⑤式的效果是一样的．例12 不存在这样的多项式 ()1110mm m m f n a n a na n a --=++++L ，使得对任意的正整数n ，()f n 都是素数．证明 假设存在这样的多项式,对任意的正整数n ，()f n 都是素数，则取正整数n b =，有素数p 使 ()1110mm m m f b a b a ba b a p --=++++=L ，进而对任意的整数,k 有 ()()()()1110mm m m f b kp a b kp a b kp a b kp a --+=+++++++L()1110m m m m a b a b a b a Mp --=+++++L （二项式定理展开）()1P M =+，其中M 为整数，这表明()f b kp +为合数．这一矛盾说明，不存在这样的多项式,对任意的正整数n ，()f n 都是素数．三、平方数若a 是整数，则2a 就叫做a 的完全平方数，简称平方数． 1．平方数的简单性质（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．（3）()()()()2220mod 4,211mod 4n n ≡-≡．（４）()()2211mod8n -≡．（6）凡是不能被3整除的数，平方后被3除余1．（7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个．（9）直角三角形的三边均为整数时，我们把满足222a b c +=的整数(),,a b c 叫做勾股数．勾股数的公式为2222,2,,a m n b mn c m n ⎧=-⎪=⎨⎪=+⎩其中,m n 为正整数，(),1m n =且,m n 一奇一偶．这个公式可给出全部素勾股数．2．平方数的证明方法（1）反证法．（2）恒等变形法．（3）分解法．设a 为平方数，且a bc =，(),1b c =，则,b c 均为平方数． （4）约数法．证明该数有奇数个约数． 3．非平方数的判别方法（1）若()221n x n <<+，则x 不是平方数．（2）约数有偶数个的数不是平方数．（3）个位数为2，3，7，8的数不是平方数．（4）同余法：满足下式的数n 都不是平方数．()2mod3n ≡， ()23mod4n ≡或， ()23mod5n ≡或， ()23567mod8n ≡或或或或，()2378mod10n ≡或或或．（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）灯被拉的次数与亮不亮（开、关）有什么关系：灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数． （5）1～100中有哪些平方数：共10个：1，4，9，16，25，36，49，64，81，100．答案：编号为1，4，9，16，25，36，49，64，81，100共10个灯还亮．例14 已知直角三角形的两条直角边分别为正整数,a b ，斜边为正整数c ，若a 为素数，求证()21a b ++为平方数．证明 由勾股定理222c a b =+，有 ()()2c b c b a +-=，但a 为素数，必有 2,1,c b a c b ⎧+=⎨-=⎩解得 ()2112b a =-，从而 ()()()22212121a b a a a ++=+-+=+，为平方数．例15 求证，任意3个连续正整数的积不是平方数．证明 设存在3个连续正整数1,,1n n n -+（1n >）的积为平方数，即存在整数m ，使 ()()211n n n m -+=，即 ()221n n m -=，但()21,1n n -=，故21,n n -均为平方数，有2221,,,n a n b m ab ⎧-=⎪=⎨⎪=⎩得 ()222211211n a n n n =-≥--=->，（注意1n >）这一矛盾说明，3个连续正整数的积不是平方数．四．整除整除的判别方法主要有7大类．1．定义法．证b a a bq ⇔=，有三种方式．（1）假设a qb r =+，然后证明0r =．（定理4）（2）具体找出q ，满足a bq =．（3）论证q 的存在． 例18 任意一个正整数m 与它的十进制表示中的所有数码之差能被9整除．证明 设1110101010n n n n m a a a a --=⨯+⨯++⨯+L ，其中09,0i n a a ≤≤≠，则()()()(){{110111121111101101101911111111,n n nn n n n n n n m a a a a a a a a a a a ------++++=-+-++-⎛⎫=⨯-+⨯++⨯+ ⎪⎝⎭L L L L L 个个按定义 ()1109n n m a a a a --++++L ． 2．数的整除判别法．（1）任何整数都能被1整除．（2）如果一个整数的末位能被2或５整除，那么这个数就能被2或５整除． （3）如果一个整数的末两位能被４或25整除，那么这个数就能被4或25整除． （4）如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除． （5）如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除．证明 由()()101mod3,101mod9≡≡，有()1110110101010mod3n n n n n n a a a a a a a a ---⨯+⨯++⨯+≡++++L L ，3．分解法．主要用乘法公式．如()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++L ．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+L ．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+-L ．例19 试证()()555129129++++++L L ．证明 改证()55545129+++L ．设555129S =+++L ，则()()()()()()()()()555555555512344123418273645918273645999,S m m m m m m m m =++++++++=++++++++=++++得9S ．又 ()()()()555555555192837465S =++++++++()()()()()5123441234192837465522225,m m m m m m m m =++++++++=++++得5S ．但()9,51=，得45S ，即()()555129129++++++L L ．例20 ()2111979,IMO -设p 与q 为正整数，满足111112313181319p q =-+--+L ，求证p 可被1979整除（1979p ） 证明111112313181319p q =-+--+L 1111111122313181319241318⎛⎫⎛⎫=+++++-+-+ ⎪ ⎪⎝⎭⎝⎭L L111111111231318131923659⎛⎫⎛⎫=+++++-++-+ ⎪ ⎪⎝⎭⎝⎭L L111166066113181319=++++L 6601319661131898999066013196611318989990+++=+++⨯⨯⨯L 19796606611319659!19791319!MM=⨯⨯⨯⨯=⨯L得1979整除1319!p ，但1979为素数，()1979,1319!1=，得p 可被1979整除．例20-1 2009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数．若规定含素因子20090909的数为吉祥数，请证明最简分数111220090908m n =+++L 的分子m 是吉祥数．证明：由111220090908m n =+++L 1111111200909082200909071004545410045455200909092009090920090909120090908220090907100454541004545520090909,122009090720090908p⎛⎫⎛⎫⎛⎫=++++++ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭=+++⨯⨯⨯=⨯⨯⨯⨯⨯L L L 其中p 为正整数，有 20090909122009090720090908n p m ⨯⨯=⨯⨯⨯⨯⨯L ，这表明，20090909整除122009090720090908m ⨯⨯⨯⨯⨯L ，但20090909为素数，不能整除122009090720090908⨯⨯⨯⨯L ，所以20090909整除m ，得m 是吉祥数．4． 余数分类法．例21 试证()()3121n n n ++．证明1 任何整数n 被3除其余数分为3类 3,31,32,n k n k n k k Z ==+=+∈，（1）3n k =时，有 ()()()()12133161,n n n k k k ++=++⎡⎤⎣⎦有()()3121n n n ++．（2）31n k =+时，有()()()()()1213313221,n n n k k k ++=+++⎡⎤⎣⎦ 有()()3121n n n ++．（3）32n k =+()()()()()121332165,n n n k k k ++=+++⎡⎤⎣⎦ 有()()3121n n n ++．综上得，()()3121n n n ++． 证明 2 ()()()()222211214n n n n n n ++++=，得 ()()322221n n n ++，又()3,41=，得()()3121n n n ++．5．数学归纳法．6．反证法．7．构造法． 例22 k 个连续整数中必有一个能被k 整除． 证明 设k 个连续整数为,1,2,,1a a a a k +++-L ，若这k 个数被k 除没有一个余数为0，则这k 个数的余数只能取1,2,,1k -L ，共1k -种情况，必存在两个数 ,,0a i a j i j k ++<-< ，使 1,a i kq r +=+2,a j kq r +=+ 其中12q q ≠，相减 ()12i j k q q -=-，有 12i j k q q k -=-≥， 即 i j k -≥与i j k -<矛盾．故k 个连续整数中必有一个能被k 整除．也可以由()12i j k q q -=-得 ()120i j k q q k <-=-<，推出1201q q <-<，与12q q -为整数矛盾．例23 k 个连续整数之积必能被!k 整除．证明 设k 个连续整数为,1,2,,1n n n n k +++-L ， （1）若这k 个连续整数为正整数，则()()()()121!!!!n n n n k n k k n k +++-=+L ()k nC =只须证明，对任何一个素数p ，分子中所含p 的方次不低于分母中所含p 的方次，由高斯函数的性质[][][]x y x y +≥+，有()s s s s k n k n k n k p p p p +-⎡⎤⎡⎤⎡⎤⎡⎤-=≥+⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦∑∑∑∑ 得k nC为整数（证实了组合数的实际意义）（2）若这k 个连续整数中有0，则连乘积为0，必能被!k 整除．（3）若这k 个连续整数为负整数，则()()()()()()()()()121!1211!1,k kk nn n n n k k n n n n k k C-+++--------+=-=-L L由（1）知kn C -为整数，故()()()121!n n n n k k +++-L 为整数．例24 有男孩、女孩共n 个围坐在一个圆周上（3n ≥），若顺序相邻的3人中恰有一个男孩的有a 组，顺序相邻的3人中恰有一个女孩的有b 组，求证3a b -．证明 现将小孩记作(1,2,,)i a i n =…，且数字化1,1, i i i a a a ⎧=⎨-⎩　表示男孩时表示女孩时则“3人组”数值化为12121212123,,,3,,,1,,,1,,,i i i i i i i i i i i i i i i i a a a a a a A a a a a a a a a a ++++++++++⎧⎪-⎪=++=⎨⎪⎪-⎩ 均为男孩 均为女孩 恰有一个女孩 恰有一个男孩其中n j j a a +=．又设取值为3的i A 有p 个，取值为3-的i A 有q 个，依题意，取值为1的i A 有b 个，取值为1-的i A 有a 个，得 12123234123()()()()n n a a a a a a a a a a a a +++=+++++++++……3(3)(1)3()()p q a b p q b a =+-+-+=-+-， 可见3a b -．例25 （1956，中国北京）证明3231122n n n ++-对任何正整数n 都是整数，并且用3除时余2． 分析 只需说明()23131222n n n n -+=为整数，但不便说明“用3除时余2”，应说明()()3212131222n n n n n n ++++=是3的倍数．作变形 ()()()32222213111,3,81228n n n n n n ++++-=-= ， 命题可证．证明 已知即()()321213111222n n n n n n ++++-=-， ① 因为相邻2个整数(),1n n +必有偶数，所以3231122n n n ++-为整数．又①可变为 ()()32222213111228n n n n n n ++++-=-，因为相邻3个整数()()2,22,21n n n ++必有3的倍数，故()()22221n n n ++能被3整除；又()3,81=，所以()()222218n n n ++能被3整除；得3231122n n n ++-用3除时余2．五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．例26 正方体的顶点标上1+或1-，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0．证明 记14个数的和为S ，易知，这14个数不是1+就是1-，若八个顶点都标上1+，则14S =，命题成立．对于顶点有1-的情况，我们改变1-为1+，则和S 中有4的数,,,a b c d 改变了符号，用/S 表示改变后的和，由()0mod2a b c d +++≡知 ()/20mod 4S S a b c d -=+++≡， 这表明，改变一个1-，和S 关于模4的余数不变，重复进行，直到把所有的1-都改变为1+，则()/111142mod4S S ≡≡+++≡≡L ，所以，0S ≠．例27 设多项式()n n n n a x a x a x a x f ++++=--1110Λ的系数都是整数，并且有一个奇数α及一个偶数β使得()αf 及()βf 都是奇数，求证方程()0=x f 没有整数根．证明 由已知有()()()0121mod21mod2n fa a a a α≡⇔++++≡L ， ①()()()1mod21mod2n f a β≡⇔≡， ②若方程()0=x f 存在整数根0x ，即()00f x =．当0x 为奇数时，有()()()00120mod20mod2n f x a a a a ≡⇔++++≡L ，与①矛盾．有0x 为偶数时，有()()()00mod20mod2n f x a ≡⇔≡，与②矛盾．所以方程()0=x f 没有整数根． 六、不定方程未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．例28 解方程719213x y +=． 解法1 由()7,191=知方程有整数解． 观察特解，列表得一个特解0025,2,x y =⎧⎨=⎩从而通解为2519,27.x t y t =-⎧⎨=+⎩方法总结：第1步，验证(),a b c ，经常是(),1a b =．第2步，求特解（观察、列举、辗转相除等）． 第3步，代入公式．方法总结：()mod ax by c ax c b +=⇔≡或()mod by c a ≡． 例29 求方程3222009x x y +=的整数解． 解 由2009的分解式，有 ()222212009741xx y +=⨯=⨯，有 21,1,1,1004,1005,22009,x x x y y x y ==-⎧=⎧⎧⇒⎨⎨⎨==+=⎩⎩⎩ 227,7,7,17,24.241,x x x y y x y ==-⎧=⎧⎧⇒⎨⎨⎨==+=⎩⎩⎩例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，…直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 ．（1988，高中联赛）解法1 设甲、乙两队的队员按出场顺序分别为1234567,,,,,,A A A A A A A 和1234567,,,,,,B B B B B B B ．如果甲方获胜，设i A 获胜的场数是i x ，则07,17i x i ≤≤≤≤而且1277x x x +++=L ， ①容易证明以下两点：在甲方获胜时（i ）不同的比赛过程对应着方程①的不同非负整数解；（ii ）方程①的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：1A 胜1B 和2B ；3B 胜1A 、和3A ；4A 胜3B 后负于4B ；5A 胜4B 、5B 和6B 但负于7B ；最后6A 胜7B 结束比赛．下面求方程①的非负整数解个数，设1i i y x =+，问题等价于方程123456714y y y y y y y ++++++=，正整数解的个数，将上式写成1111111111111114+++++++++++++=，从13个加号取6个的方法数613C 种．得甲方获胜的不同的比赛过程有613C 种．同理，乙方获胜的不同的比赛过程也有713C 种，合计61323432C =种比赛过程例31（1989，高中）如果从数1，2，…，14中按由小到大的顺序取出123,,a a a ，使同时满足 21323, 3a a a a -≥-≥，那么，所有符合上述要求的不同取法有多少种？解 由已知得121323 10,30 30, 140,a a a a a a -≥--≥--≥-≥4项均为非负数，相加得()()()()121323133 147a a a a a a -+--+--+-=，于是123,,a a a 的取法数就是不定方程 12347x x x x +++=的非负整数解的个数，作一一对应11i y x =+，问题又等价于不定方 123411y y y y +++= 的正整数解．由 11111+++=L ，得310C 个解，即符合要求的不同取法有310C 种．七．数论函数主要是[]x 高斯函数，()n ϕ欧拉函数．例32 某学校要召开学生代表大会，规定各班每10人推选一名代表，当各班人数除以10的余数大于．．6．时再增选一名代表．那么，各班可推选代表人数y 与该班人数x 之间的函数关系用取整函数[]y x =（[]x 表示不大于x 的最大整数）可以表示为(A)10x y ⎡⎤=⎢⎥⎣⎦ (B)310x y +⎡⎤=⎢⎥⎣⎦ (C) 410x y +⎡⎤=⎢⎥⎣⎦ (D)510x y +⎡⎤=⎢⎥⎣⎦ （2010年全国高考数学陕西卷理科第10题）解法1 选（B ）．（求解对照）．规则是“六舍七入”，故加3即可进1． 选310x y +⎡⎤=⎢⎥⎣⎦． 解法2 选（B ）．（特值否定）．取56x =，按规定应选5人，可否定(C)、(D)；再取57x =，按规定应选6人，可否定(A)．注：主要错误选(C) ，误为“五舍六入”．例33 用[]x 表示不大于x 的最大整数，求122004366366366366⎡⎤⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦L ． 讲解 题目的内层有2004个高斯记号，外层1个高斯记号．关键是弄清[]x 的含义，进而弄清加法谁与谁加、除法谁与谁除：（1）分子是那些数相加，求出和来；由36651830200421963666⨯=<<=⨯，知分子是0～5的整数相加，弄清加数各有几个（2）除法谁除以366，求出商的整数部分．原式()036536612345175366⨯+++++⨯⎡⎤=⎢⎥⎣⎦1036687536614310236612.⨯+⎡⎤=⎢⎥⎣⎦⎡⎤=++⎢⎥⎣⎦= 命题背景2004年有12个月、366天．例34 50!的标准分解式中2的指数．解 35678912450!23571113171923293137414347ααααααααα=gg g g g 2的指数为2345505050505025126314722222⎡⎤⎡⎤⎡⎤⎡⎤⎡⎤++++=++++=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦． 图示（5条横线，25个偶数中2的方次，按横线求和）八、综合练习例35 整数勾股形中，证明（1）必有一条直角边长是3的倍数；（2）必有一条直角边长是4的倍数； （3）必有一条边长是5的倍数；（4）三角形的面积是6的倍数．证明 当整数勾股形的三边有公约数时，可以先约去，使三边长,,x y z 互素，且满足222x y z +=.这时，若,x y 两个均为偶数，则z 也为偶数，与,,x y z 互素矛盾；若,x y 两个均为奇数，有()()221mod4,1mod4x y ≡≡，得 ()2222mod4z x y ≡+≡， 这与平方数模4只能取0，1矛盾.所以，,x y 中有且只有一个为偶数，不妨设x 为偶数.（1）设,x y 中无一为3的倍数，则()()221mod3,1mod3x y ≡≡，得 ()2222mod3z x y ≡+≡，这与平方数模3只能取0，1矛盾，故,x y 中有一个为3的倍数. （2）由x 为偶数.，必有,y z 均为奇数，记2,21,21x m y p z q ==+=+有 ()()()22222222421214m x z y q p q q p p ==-=+-+=+--则 ()()211m q q p p =+-+右边是两个偶数的差，必为偶数，从而x 为4的倍数.（3）若,x y 中有5的倍数，命题已成立. 若,x y 均不是5的倍数，则若,x y 只能是形如51k ±或52k ±的正整数.若,x y 均为51k ±型，则()222112mod5z x y ≡+≡+≡这与平方数模5只能取0，1，4矛盾若,x y 均为52k ±型，则()222443mod5z x y ≡+≡+≡这与平方数模5只能取0，1，4矛盾.所以，,x y 只能分别取51k ±与52k ±型，有 ()222410mod5z x y ≡+≡+≡得25z ，但5是素数，得5z .（4）由上证（1）、（2）及()3,41=知，xy 是12的倍数，则12xy 是6的倍数，得三角形的面积是6的倍数． 例36 已知ABC V 内有n 个点，连同,,A B C 共有3n +个点，以这些点为顶点，把ABC V 分割为若干个互不重叠的小三角形，现把,,A B C 分别染上红色、蓝色、黄色，而其余n 个点，每点任意染上红、蓝、黄三色之一，证明三顶点都不同色的小三角形的总数必是奇数．（斯潘纳定理）证明1 给这些小三角形的边赋值：当边的两端点同色时，记为0；当边的两端点异色时，记为1；再用三边之和给小三角形赋值：当三角形的三顶点同色时，和值为0，记这样的小三角形有a 个；当三角形的三顶点中仅有两点同色时，和值为2，记这样的小三角形有b 个；当三角形的三顶点两两异色时，和值为3，记这样的小三角形有c 个.下面用两种方法计算所有三角形赋值的总和S ，一方面02323S a b c b c =⨯+⨯+⨯=+. ①另方面，,,AB BC CA 的赋值均为1，和为奇数；而ABC V 内的每一条连线，在上述S 的计算中都被计算了两次，和为偶数；这两者之和得S 为奇数，记为21S k =+ ②由①，②得 2123k b c +=+可见c 为奇数，即三顶点都不同色的小三角形的总数必是奇数．（证明：n 个连续整数的乘积一定能被n!整除设a 为任一整数，则式： (a+1)(a+2)...(a+n) =(a+n)!/a! =n!*[(a+n)!/(a!n!)]而式中[(a+n)!/(a!n!)]恰为C(a+n,a),也即是从a+n 中取出a 的组合数，当然为整数。

数学竞赛的精华数论数论是数学中的一个分支，研究数字的性质和相互关系。

在数学竞赛中，数论经常被认为是其中最具挑战性和精华的部分。

本文将探讨数论在数学竞赛中的重要性、常见的数论问题和一些解题技巧。

一、数论在数学竞赛中的重要性数论在数学竞赛中的重要性不言而喻。

首先，数论是一门富有深度的数学学科，其问题常常需要较高的抽象思维和逻辑推理能力。

这对于培养学生的数学思维、推理能力以及严谨的数学证明能力具有显著的作用。

其次，数论问题在数学竞赛中普遍存在，考察了学生对于基本数论概念的掌握和应用能力。

因此，掌握数论成为了数学竞赛中获胜的关键。

二、常见的数论问题在数学竞赛中，数论问题多种多样。

以下是一些常见的数论问题：1. 质数判定：给定一个正整数，判断其是否为质数。

质数判定是数论中的基本问题，可以通过试除法、欧拉筛法等方法解决。

2. 最大公约数与最小公倍数：给定两个正整数，求它们的最大公约数和最小公倍数。

最大公约数和最小公倍数是数论中的重要概念，可以通过辗转相除法等方法求解。

3. 同余关系与模运算：给定两个整数a和b，判断它们是否满足同余关系。

模运算是数论中的重要概念，在解决同余关系问题时起到了关键作用。

4. 整数分解：给定一个正整数，将其分解为质因数的乘积。

整数分解是数论中的重要问题，可以通过试除法等方法解决。

三、解题技巧在数论问题中，解题技巧起到了至关重要的作用。

以下是一些解题技巧：1. 利用举反例法：在数论问题中，举一反三往往是解题的核心。

通过运用举反例法，可以揭示问题的本质，帮助我们找到解题的思路。

2. 利用归纳法：数论问题中的递推和归纳思想常常被用来解决问题。

通过观察数列的规律，可以推导出问题的通用解法。

3. 利用模数的选择：模数的选择对于解决同余关系和模运算问题至关重要。

选择合适的模数可以简化计算，加快解题速度。

4. 利用逆元与同余定理：逆元和同余定理是解决同余关系问题的重要工具。

运用逆元和同余定理可以简化问题的分析与计算。

高一竞赛数论专题1.整除设,,0.a b Z a ∈≠如果存在,q Z ∈使得,b aq =那么就说b 可被a 整除(或a 整除b ),记做|.a b 且称b 是a 的倍数,a 是b 的约数(也可称为除数、因数).b 不能被a 整除就记做a b Œ. 整除关系的基本性质(1)|,||.a b b c a c ⇒(2)|,|a b a c ⇔对任意的,,x y Z ∈有|.a bx cy +设12,a a 是两个不全为零的整数,如果1|d a 且2|,d a 那么d 就称为1a 和2a 的公约数,我们把1a 和2a 的公约数中的最大的称为1a 和2a 的最大公约数,记做12(,).a a 若12(,)1,a a =则称1a 和2a 是既约的,或是互素的.设12,a a 是两个均不为零的整数,如果1|,a l 且2|,a l 那么l 就称为1a 和2a 的公倍数,我们把1a 和2a 的公倍数中的最小的称为1a 和2a 的最小公倍数,记做12[,].a a1.设12,a a 是两个不全为零的整数,证明对任意整数q ,都有12121(,)(,).a a a a qa =+2.设(,)1,a b =证明(1)若|,|a c b c 则|.ab c(2)若|a bc 则|.a c3.(Bezout 定理)设,a b 是不全为零的整数,证明(,)1a b =的充要条件是存在整数,x y 使得 1.ax by +=4.证明对任意整数n ,65222n n n n +--能被120整除.5.设m 是一个大于2正整数,若存在正整数n 使得21|21m n -+.求m 的所有可能取值.6.证明：正整数M 是完全平方数的充要条件是对于任意正整数n ,22(1),(2),,M M M M +-+-2()M n M +-中至少有一项可以被n 整除.7.已知整数,x y 满足1,1,x y ≠-≠-且使得441111x y y x --+++是整数,求证4441x y -能被1x +整除.8.证明：对于任何自然数n 和k ,数3(,)2410k k f n k n n =++都不能分解成若干个连续的自然数之积.9.对于所有素数p 和所有正整数()n n p ≥,证明：p n n C p ⎡⎤-⎢⎥⎣⎦能被p 整除.10.(1)求所有的素数数列12n p p p <<<,使得11(1)n k kp =+∏是一个整数. (2)是否存在n 个大于1的不同正整数*12,,,,,n a a a n N ∈使得211(1)n k ka =+∏为整数?.11.设,m n 是正整数, 证明(,)(21,21)21.m n m n --=-12.任给2n ≥,证明：存在n 个互不相同的正整数,其中任意两个的和整除这n 个数的积.高一竞赛数论专题1.整除解答设,,0.a b Z a ∈≠如果存在,q Z ∈使得,b aq =那么就说b 可被a 整除(或a 整除b ),记做|.a b 且称b 是a 的倍数,a 是b 的约数(也可称为除数、因数).b 不能被a 整除就记做a b Œ. 整除关系的基本性质(1)|,||.a b b c a c ⇒(2)|,|a b a c ⇔对任意的,,x y Z ∈有|.a bx cy +设12,a a 是两个不全为零的整数,如果1|d a 且2|,d a 那么d 就称为1a 和2a 的公约数,我们把1a 和2a 的公约数中的最大的称为1a 和2a 的最大公约数,记做12(,).a a 若12(,)1,a a =则称1a 和2a 是既约的,或是互素的.设12,a a 是两个均不为零的整数,如果1|,a l 且2|,a l 那么l 就称为1a 和2a 的公倍数,我们把1a 和2a 的公倍数中的最小的称为1a 和2a 的最小公倍数,记做12[,].a a1.设12,a a 是两个不全为零的整数,证明对任意整数q ,都有12121(,)(,).a a a a qa =+证明：记121(,),a a d =1212(,)a a qa d +=.121(,),a a d =即1112|,|.d a d a 于是11121|,|.d a d a qa +所以12.d d ≤1212(,)a a qa d +=,即21221|,|.d a d a qa +于是2122112|,|().d a d a qa qa a +-=所以21.d d ≤所以12.d d =命题得证.2.设(,)1,a b =证明(1)若|,|a c b c 则|.ab c(2)若|a bc 则|.a c证明(,)1,a b =则1.ax by =+于是1().c c c ax by acx bcy =⋅=+=+(1)|,|a c b c ,则12,.c aq c bq ==于是2121().c abq x baq y ab q x q y =+=+所以|.ab c(2)|,a bc 则|.a acx bcy +即|.a c3.(Bezout 定理)设,a b 是不全为零的整数,证明(,)1a b =的充要条件是存在整数,x y 使得 1.ax by +=证明：当,a b 中有一个为零时,结论是显然的.不妨设,a b 都不为零,且||||.a b ≤一方面若存在整数,x y 使得 1.ax by +=注意到(,)|,(,)|a b a a b b .所以(,)|.a b ax by +即(,)|1.a b 所以(,)1a b =.另一方面设11111,0||,,b aq r r a q r =+≤<为整数,若10,r =则辗转相除到此为止；否则继续.1222122,0,,a r q r r r q r =+≤<为整数,若20,r =则辗转相除到此为止；否则继续.12333233,0,,r r q r r r q r =+≤<为整数,若30,r =则辗转相除到此为止；否则继续.由于123r r r >>>且123,,,r r r 均为自然数,所以经过有限步辗转相除可得0.k r =即3211.k k k k r r q r ----=+21(0).k k k k k r r q r r --=+=引理：设,a b 是两个整数且0,a ≠,0||,,b aq r r a q r =+≤<为整数.则(,)(,).a b a r =证明：因为(,)(,).a b a b aq =-又.r b aq =-所以(,)(,).a b a r =回到原题：利用引理我们可得112211(,)(,)(,)(,)(,).k k k k a b a r r r r r r r ---=====注意到0.k r =所以11(,)(,0).k k a b r r --==由辗转相除的过程知道1321.k k k k r r r q ----=- 2432.k k k k r r r q ----=-3123.r r r q =-212.r a r q =-11r b aq =-所以11,r b aq =-212122()(1),r a b aq q q q a q b =--=+-311223123123[(1)][(1)](1),r b aq q q a q b q q q q q a q q b =--+-=+-++所以1k r -是,a b 的线性组合即存在整数,x y 使得1.k r ax by -=+即(,).a b ax by =+所以若(,)1,a b =则存在整数,x y 使得 1.ax by +=4.证明对任意整数n ,65222n n n n +--能被120整除.证明：65254222(2)(2)(2)(1)(2)(1)(1)(1)n n n n n n n n n n n n n n n n +--=+-+=+-=+-++ 22(2)(1)(1)(45)(2)(1)(1)(2)5(1)(1)(2)n n n n n n n n n n n n n n =+-+-+=--+++-++.5!|(2)(1)(1)(2),n n n n n --++4!|(1)(1)(2),5!|5(1)(1)(2),n n n n n n n n -++-++所以65222n n n n +--能被120整除.5.设m 是一个大于2正整数,若存在正整数n 使得21|21m n -+.求m 的所有可能取值.解: 因为21|21m n -+,所以2121n m +≥-所以n m ≥(若不然,则 1.n m ≤-于是1212121m n m -+≥+≥-,即2m ≤矛盾).因为n m ≥,所以存在正整数,q r 使得,0.n mq r r m =+≤<1212122212(21)212(21)[(2)21]21n mq r mq r r r r mq r r m m q m r ++-+=+=-++=-++=-+++++. 因为21|21m n -+,所以21|21m r -+.从而212 1.r m+≥- 注意到0.r m ≤<所以 1.r m ≤-于是121212 1.m r m -+≥+≥-即2m ≤矛盾.所以不存在这样的.m6.证明：正整数M 是完全平方数的充要条件是对于任意正整数n ,22(1),(2),,M M M M +-+-2()M n M +-中至少有一项可以被n 整除.证明：()⇒正整数M 是完全平方数,则2.M d = 222222()()()()M i M d i d d d i d d i +-=+-=++-+.2d d i -+对于1,2,,i n =是连续n 个正整数,所以一定存在某个i 使得2|.n d d i -+于是2|().n M i M +- 所以对于任意正整数n ,22(1),(2),,M M M M +-+-2()M n M +-中至少有一项可以被n 整除.()⇐假设正整数M 不是完全平方数,则M 中一定有一个素因数p ,它的指数是奇数即存在正整数k 使得212|,.k k p M p M -Œ因为对于任意正整数n ,22(1),(2),,M M M M +-+-2()M n M +-中至少有一项可以被n 整除. 故取2k n p =,对于21,2,,k i p =一定存在某个i 使得22|().k p M i M +-注意到2k p M Œ.所以22()k p M i +Œ( 若不然, 22|(),k p M i +又22|().k p M i M +-于是2k p M Œ矛盾). 由于22|(),k p M i M +-于是212|().k p M i M -+-注意到21|k p M -.所以212|().k p M i -+我们得到212|()k pM i -+且22()k p M i +Œ.这与2()M i +是完全平方数矛盾. 所以假设错误.所以正整数M 是完全平方数.7.已知整数,x y 满足1,1,x y ≠-≠-且使得441111x y y x --+++是整数,求证4441x y -能被1x +整除.证明：设4411,.11x a y cy b x d--==++其中(,)1,(,)1,0,0.a b c d b d ==>> 则a c ad bcb d bd++=是整数.即|.bd ad bc + 从而|,|.b ad bc d ad bc ++于是|,|.b ad d bc 注意到(,)1,(,) 1.a b c d == 所以|,|.b d d b 又0,0b d >>,所以.b d =因为44222211(1)(1)(1)(1)(1)(1)(1)(1)(1)(1).1111a c x y x x x y y y x x y yb d y x y x ---++-++⋅=⋅=⋅=-+-+++++ 所以a cb d⋅是整数,结合.b d = 所以2|.b ac 于是|b ac ,又(,)1a b =,则|,b c 又(,) 1.b c =且0.b >所以 1.b =也就是411y c x -=+.即41| 1.x y +-又44444444441049421(1)1(1)[()()1](1)(1)(1)x y x y x x y y y y x x x -=-+-=-++++++-+.所以4441| 1.x x y +-8.证明：对于任何自然数n 和k ,数3(,)2410k kf n k n n =++都不能分解成若干个连续的自然数之积.证明: 我们知道数(,)f n k 能分解成n 个连续的自然数之积,则一定能被!n 整除.所以只需要证明数(,)f n k 不能被一个很小的自然数n 整除即可.33333(,)2410(339)13(3)()1k k k k k k k k k k f n k n n n n n n n n n n =++=++-++=++--+ 33(3)(1)(1)1k k k k k n n n n n =++--++. 33|3(3),3|(1)(1),3 1.k k k k k n n n n n ++-+Œ所以3(,).f n k Œ也就是数(,)f n k 不能分解成3个或3个以上的连续的自然数之积. 下面再证明数(,)f n k 不能分解成2个连续的自然数之积.由上可知(,)31f n k q =+.因此只需要证明31(1)q x x +=+无自然数解. 当3x m =时,(1)3(31)3[(31)]x x m m m m +=+=+,故无解.当31x m =+时,2(1)(31)(32)3(33)2x x m m m m +=++=++,故无解.当32x m =+时,(1)(32)(33)3(1)(32)x x m m m m +=++=++故无解. 所以数(,)f n k 不能分解成2个连续的自然数之积.于是我们证明了对于任何自然数n 和k ,数3(,)2410k kf n k n n =++都不能分解成若干个连续的自然数之积.9.对于所有素数p 和所有正整数()n n p ≥,证明：pn n C p ⎡⎤-⎢⎥⎣⎦能被p 整除. 证明：,1,2,,1n n n n p ---+这连续p 个数有且仅有一个被p 整除,设这个数为.N 则,.N pq q Z =∈则.n Nq p p⎡⎤==⎢⎥⎣⎦且,1,,1,1,1n n N N n p -+--+除以p 的余数不计次序为1,2,,1p -.于是(1)(1)(1)(1)(1)!.n n N N n p p pA -+--+=-+(1)(1)(1)(1)(1)(1)(1)(1)1!(1)!p n n n n N N N n p n n N N n p C q q p p p ⎡⎤⎡⎤-+--+-+--+-=-=-⎢⎥⎢⎥-⎣⎦⎣⎦(1)!1(1)!(1)!p pA pqAq p p ⎡⎤-+=-=⎢⎥--⎣⎦. 因为p 与1,2,,1p -互素,所以(,(1)!) 1.p p -=于是(1)!|..(1)!p n n qAp qAC p p p ⎡⎤--=⋅⎢⎥-⎣⎦所以|.pn n p C p ⎡⎤-⎢⎥⎣⎦10.(1)求所有的素数数列12n p p p <<<,使得11(1)nk kp =+∏是一个整数. (2)是否存在n 个大于1的不同正整数*12,,,,,n a a a n N ∈使得211(1)nk k a =+∏为整数?.解(1)111(1)1(1).nk nk n k k kk p p p ===++=∏∏∏ 当3n ≥时,1,1 1.n k p p k n >+≤≤-故11((1),) 1.n knk p p -=+=∏所以|1.nn pp +又|.n n p p 所以|1.n p于是1n p =矛盾.所以2n ≤.当1n =时,111N p +∉. 当2n =时,1212121212(1)(1)111(1)(1)1.p p p p N p p p p p p ++++++==+∈ 1212|1p p p p ++,21221|1,|1.p p p p p +++又211p p ≥+.所以211.p p =+于是1111|11,|2.p p p p +++ 所以122, 3.p p ==综上,所求的数列只有一个122, 3.p p == (2)不存在. 当121n a a a <<<<时,设.n a m ≤2222222212222111(!)21(1)(1) 2.(1)!1(1)(1)1(1)!2nm m m m k k k k k k k k k m mm a k k k k k m m =====+<+≤+=<===<+--++-∏∏∏∏∏所以211(1)nk k N a =+∉∏.所以不存在n 个大于1的不同正整数*12,,,,,n a a a n N ∈使得211(1)nk k a =+∏为整数.11.设,m n 是正整数, 证明(,)(21,21)21.m n m n --=- 解：不妨设.m n ≥有带余除法得1111(1,0)m q n r q r n =+≥≤<.我们有111111111212122212(21)2 1.q n r q n r r r r q n r m++-=-=-+-=-+-因为121|21q nn--,所以1(21,21)(21,21).r m n n --=--注意到1(,)(,).m n n r =若10,r =则1(,)(,).m n n r n ==于是1(21,21)(21,21)(0,21)2 1.rm n n n n--=--=-=-结论成立.若10,r >则作辗转相除.,212221(1,0)n q r r q r r =+≥≤<.我们有212221221212(21)2 1.q r r r q r r n+-=-=-+-因为12121|21rq r --,所以112(21,21)(21,21)(21,21)r r r m n n --=--=--.若20,r >则继续处理,直到10k r +=为止.由辗转相除法知(,).k m n r =1112(,)(21,21)(21,21)(21,21)(21,21)(21,0)212 1.k k k k r r r r r r r m n n m n +--=--=--==--=-=-=-至此,我们证得了结论.12.任给2n ≥,证明：存在n 个互不相同的正整数,其中任意两个的和整除这n 个数的积.证明：我们任取n 个互不相同的正整数12,,,,n a a a 并选取一个正整数参数,K 希望12,,,n Ka Ka Ka 的积12n n K a a a 被任意两项的和i j Ka Ka +()i j ≠整除,取1().i j i j nK a a ≤<≤=+∏12,,,n Ka Ka Ka 互不相同, 1()().i j i j i j i j nKa Ka a a a a ≤<≤+=++∏12121(()).n n n i j n i j nK a a a a a a a a ≤<≤=+∏显然有12|.ni j n Ka Ka K a a a +。

初等数论简介绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。

1． 请看下面的例子：（1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。

(1894年首届匈牙利 数学竞赛第一题) （2） ①设n Z ∈，证明2131n -是168的倍数。

②具有什么性质的自然数n ，能使123n ++++能整除123n ⋅⋅⋅（1956年上海首届数学竞赛第一题）（3） 证明：3231122n n n ++-对于任何正整数n 都是整数，且用3除时余2。

（1956年北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数214143n n ++不可约简。

（1956年首届国际数学奥林匹克竞赛第一题）（5） 令(,,,)a b g 和[,,,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数，试证：[][][][]()()()()22,,,,,,,,,,a b c a b c a b b c c a a b b c c a =⋅⋅（1972年美国首届奥林匹克数学竞赛第一题）这些例子说明历来数论题在命题者心目中首当其冲。

2.再看以下统计数字：（1）世界上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占18.5%。

（2）世界上规模最大、规格最高的IMO （国际数学奥林匹克竞赛）的前20届120道试题中有数论13题，占% 。

这说明：数论题在命题者心目中总是占有一定的分量。

如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。

3.请看近年来国内外重大竞赛中出现的数论题：(1)方程323652x x x y y ++=-+的整数解(,)x y 的个数是（ ）A 、 0B 、1C 、3D 、无穷多（2007全国初中联赛5）（2）已知,a b 都是正整数，试问关于x 的方程()2102x abx a b -++=是否有两个整数解如果有，请把它们求出来；如果没有，请给出证明。

高中数学竞赛 数论剩余类与剩余系1.剩余类的定义与性质(1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类((2)2.(1)a r ，得m 个数特别地,完全为偶数时,,2-m (2)证明:即证a 0,a 1,…,a m-1与aa 0+b, aa 1+b,…,aa m-1+b 同为模m 的完全剩余系,因a 0,a 1,…,a m-1为模m 的完系时,若aa i +b ≡aa j +b(modm),则a i ≡a j (modm),矛盾!反之,当aa 0+b, aa 1+b,…,aa m-1+b 为模m 的完系时,若a i ≡a j (modm),则有aa i +b ≡aa j +b(modm),也矛盾!(ⅲ)设m 1,m 2是两个互质的正整数,而x,y 分别遍历模m 1,m 2的完系,则m2x+m1y历遍模m1m2的完系.证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y// (modm2),从而x/≡x//(modm1),y/≡y//(modm2),矛盾!3.(1).在与模m的一个(2)(ϕm)x1≡x2,则a1,a2,…,aφ(m)是模m的一个既约剩余系.证明:因a1,a2,…,aφ(m)是)m(ϕ个与m互质的整数,并且两两对模m不同余,所以,a1,a2,…,aφ(m)属于)m(ϕ个剩余类,且每个剩余类都与m互质,故a1,a2,…,aφ(m)是模m的一个既约剩余系.(ⅴ)设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m 2x+m 1y 历遍模m 1m 2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y 分别历遍模m 1,m 2的完系时,m 2x+m 1y 历遍模m 1m 2的完系.由(m 1,x )=(m 2,y )=1,(m 1,m 2)=1得(m 2x,m 1)=(m 1y,m 2)=1,所以,(m 2x+m 1y,m 1)=1,(m 2x+m 1y,m 2)=1,故 (m 2x+m 1y, m 1m 2)=1.反之若(m 2x+m 1y, m 1m 2)=1,则(m 2x+m 1y,m 1)=(m 2x+m 1y,m 2) =1,1m 2的既)(2m ϕ)., 1,α(4.欧拉欧拉(Euler)定理 设m 是大于1的整数,(a ,m)=1,则)(m od 1)(m a m ≡ϕ. 证明:设r 1,r 2,…,r )(m ϕ是模m 的既约剩余系,则由性质3知a r 1,a r 2,…,a r )(m ϕ也是模m 的既约剩余系,所以, a r 1a r 2…a r )(m ϕ≡r 1r 2…r )(m ϕ(modm),即≡)(21)(m m r r r a ϕϕ)(21m r r r ϕ ,因()(21m r r r ϕ ,m)=1,所以,)(m od 1)(m a m ≡ϕ.推论(Fermat 定理) 设p 为素数,则对任意整数a 都有)(m od p a a p ≡.证明:若(a , p )=1,由1)(-=p p ϕ及Euler 定理得)(m od 11p a p ≡-即)(m od p a a p ≡;若(a , p )≠1,则p |a ,显然有)(m od p a a p ≡.例1设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数.证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a .例(m 整除,.例m,使得2011|f n f 3因所以,例,是整数序列负整数假设对每个正整数:在数列123,,,a a a 中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a 1=0.此时对每个正整数k 必有∣a k ∣<k:若∣a k ∣≥k,则取n=∣a k ∣,则a 1≡a k ≡0(mod n),矛盾.现在对k 归纳证明a 1,a 2,…,a k 适当重排后是绝对值小于k 的k 个相邻整数.k=1显然.设a 1,a 2,…,a k 适当重排后为-(k -1-i),…,0,…,i (0≤i ≤k -1),由于a 1,a 2,…,a k ,a k+1是(mod k+1)的一个完全剩余系,故必a k+1≡i+1(mod k+1), 但∣a k+1∣<k+1,因此a k+1只能是i+1或-(k -i),从而a 1,a 2,…,a k ,a k+1适当重排后是绝对值小于k+1的k+1个相邻整数.由此得到:1).任一整数在数列中最多出现一次;2).若整数u 和v (u<v) 都出现在数列中,则u 与v 之间的所有整数也出现在数列中.得到:例,(i,j)也历mod2n 的和≡例可被,且是周期数列,所以, 数列{a n }中存在无穷多项可被2011整除.例7证明:存在无穷多个正整数n,使得n 2+1∤n!.证明:引理1对素数p >2,⇔≡)4(mod 1p 存在x(1≤x ≤p -1)使)(m od 12p x -≡. 证:充分性:因对1≤x ≤p -1,( p ,x)=1,所以,)(mod 1)(2121p x x p p ≡=--,≡-212)(p x)(mod 1)1(21p p ≡--,所以,21-p 为偶数,即).4(mod 1≡p 必要性:因1≤x ≤p -1时,x,2x,…,(p -1)x 构成modp 的既约剩余系,所以,存在1≤a ≤p -1,使得a x ≡-1(mod p ),若不存在a (1≤a ≤p -1), a =x,使a x ≡-1(mod p ),则这样的a ,x 共配成21-p 对,则有)(mod 1)!1()1(21p p p -≡-≡--,即21-p 为奇数,与 p 2证a =4(p 1p 设2p 1 p 2…12x -≡,相应的x 例(1)(2)n n+1n (n=1,2, …),且每个a n 都是f(x)的周期.证明：(1)设T=nm (正整数m,n 互质,且n ≥2),因(m,n)=1,所以,m,2m,…,nm 构成 modn 的完系,故存在k ∈N *使得km ≡1(modn),即存在t ∈N *使得km=nt+1,因f(x)=f(x+kT)=f(x+n km )=f(x+t+n 1)=f(x+n 1),所以n1是周期. 设n=kp ,其中k ∈N *, p 为素数,则n k p 11⋅=是周期.故存在素数p,使p 1是周期. (2)当T 为无理数时,取a 1=T,则T 为无理数, 0<T<1.设k≤n 时存在无理数a k ,使得0<a k <a k-1<1,且a k 是周期.对k+1,总存在存在u,v ∈N *,使得0<u a k -v<a k <1,取例解:,对任意}包含了modn+1零剩余,≤k ≤n, a 1+a 2+取例. 例11求所有的奇质数p ,使得∑=-11|k p k p .例12求所有质数p ,使得2122213)()()(|-+++p p p p C C C p .例13设n 为大于1的奇数,k 1,k 2,…,k n 是n 个给定的整数,对1,2,…,n 的每一个排列a=(a 1,a 2,…,a n ),记S(a)=∑=ni i i a k 1.证明:存在两个1,2,…,n 的排列b 和c(b ≠c),使得n!|S(b)-S(c).证明:如果对1,2,…,n 的任意两个不同排列b 和c(b ≠c),都有n!∤S(b)-S(c),那么当a 取遍所有排列时(共n!个),S(a)遍历模n!的一个完系, 因此,有∑a a S )(≡1+2+…+n!≡2!2)1!(!n n n ≡+(modn!) ①, 另一方面,我们有 ∑a a S )(=)!(mod 0)1(!])!1[(n k n n j n k a k a k n i n n in i i n i i ≡+=-==∑∑∑∑∑∑∑ ②. 由①∑a .例modm 因(m,2n 例x 例在A同余方程与同余方程组1.同余方程(组)及其解的概念定义1 给定正整数m 及n 次整系数多项式0111)(a x a x a x a x f n n n n ++++=--，则同余式f(x)≡0(modm)①叫做模m 的同余方程,若a n 0(modm),则n 叫做方程①的次数.若x=a是使f(a)≡0(modm)成立的一个整数,则x≡a(modm)叫做方程①的一个解,即把剩余类a(modm)叫做①的一个解.若a1(modm),a2(modm)均为方程①的解,且a1,a2对模m不同余,就称它们是方程①的不同解.由此可见,只需在模m的任一组完系中解方程①即可.例12解:例2解:.2.设a x解,例3解:tx即)8-≡x.3,1-(mod≡t),1,08(mod1=4+例4解方程12x≡6(mod9).因(12,9)=3,且-1是一个特解,所以,方程12x≡6(mod9)的解为:(modx即)8t5,2,1，≡t≡-x.(mod),2,1,083+1=-3.同余方程组定义3给定正整数m 1,m 2,…,m k 和整系数多项式f 1(x),f 2(x),…,f k (x),则同余式组 ⎪⎪⎩⎪⎪⎨⎧≡≡≡)(mod 0)()(mod 0)()(mod 0)(2211k k m x f m x f m x f ②,叫做同余方程组.若x=a 是使f j (a )≡0(modm j )(1≤j ≤k)成立的一个整数,则x ≡a (modm)叫做方程组②的一个解,即把剩余类a (modm)叫做②的一个解.例5解:⎩⎨⎧-≡≡13x x .M=m 1m ⎪⎪⎩⎪⎪⎨⎧≡≡≡21k a x a x a x 其中M j ).(2)j j j j 则x ≡y (modm j ),即m j |x -y ,因m 1,m 2,…,m k 两两互质,所以M| x-y 即x ≡y (modM). 注:(1)存在无穷多个整数x 满足同余方程组③,这些x 属于同一模m 的剩余类;(2)同余方程组③仅有一个解x ≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM).(3)当(a ,m i )=1(=1,2,…,n)时,同余方程组⎪⎪⎩⎪⎪⎨⎧≡≡≡⇔⎪⎪⎩⎪⎪⎨⎧≡≡≡---)(mod )(mod )(mod )(mod )(mod )(mod 12211112211k k k k m a a x m a a x m a a x m a ax m a ax m a ax仍然具有定理结论. 这在数论解题中具有重要应用.例6“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何”.解,352115≡x 例.解:210×210-1≡210-1≡1(mod11)⇔210-1≡1(mod11),所以,同余方程组的解为: )2310(mod 2111637121010330438553462≡=⨯+⨯+⨯+⨯≡x ,即x=2310k+2111(k ∈N).例8证明:对任意n 个两两互质的正整数:m 1,m 2,…,m n ,总存在n 个连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).证明:由剩余定理知,总存在整数k 使得⎪⎪⎩⎪⎪⎨⎧-≡-≡-≡)(mod )(mod 2)(mod 121n m n k m k m k,即存在连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).例9证明:对任意n ∈N *,存在n 个连续正整数它们中每一个数都不是素数的幂(当 数⎪⎪⎩⎪⎪⎨⎧-≡-≡-≡21n m m m例,且A 例 {k +a n }⎩⎨⎧-≡≡)(mod 102p x x 123⎪⎩-≡)(mod 232p x 2的最小正整数a 2=38.假定a 1,a 2,…,a n 都已确定,则取a n+1适合⎪⎪⎩⎪⎪⎨⎧-≡-≡≡+)(mod )(mod 1)(mod 0121n p n x p x p x 且大于a n 的最小正整数,由剩余定理知满足条件的a n+1存在.则上述递推关系定义的数列{a n }满足题意:因对任意k ∈N *,当n ≥k+1时,都有k+a n ≡0(mod p k+1),由{a n }递增可知{k +a n }从第k+2项起每一项都是p k+1的倍数,且都大于p k+1,所以,数列{k +a n }中至多有k+1项为素数.例12是否存在一个由正整数组成的数列，使得每个正整数都恰在该数列中出现一次，且对任意正整数k ，该数列的前k 项之和是k 的倍数？解:,S=a 1+a 2⎩⎨⎧++≡+t r S r S {a n }例的质因数.例例。

【高中数学竞赛专题大全】 竞赛专题15 初等数论 （50题竞赛真题强化训练）一、填空题1．（2020·浙江·高三竞赛）将1~2020的数字按顺时针方向围成一个圆圈，然后从1开始，按顺时针依次隔一个数拿走，即拿走1，3，5，…，这个过程一直进行下去，直到剩下最后一个数字，则最后剩下的数字是___________. 【答案】1992. 【解析】 【详解】在第一轮中，从1开始到拿走1991，共取走996个数，此时余下1024个数， 1991后一项偶数为1992，此后共取10次，余下的数为1992， 故答案为:1992.2．（2021·全国·高三竞赛）关于x 、y 的方程11112007x y xy ++=的正整数解(,)x y 的个数为________． 【答案】48 【解析】 【详解】解析：由11112007x y xy ++=得2007200720070xy x y ---=，整理得 32(2007)(2007)2007200823223251x y --=⨯=⨯⨯⨯，从而，原方程的正整数解有(31)(21)(11)(11)48++++=（个）． 故答案为：48.3．（2021·全国·高三竞赛）{}n a 为正整数列，满足112,n a a +=为213133n n a a -+的最小素因子，12,,,,n a a a ，构成集合A ，P 为所有质数构成的集合，则集合P A 的最小元素为___________． 【答案】5 【解析】由于122,3a a ==，故2,3A ∈，所以集合P A -的最小元素5≥．假设存在正整数n ，使得5(3)n a n =≥，则211513133n n a a ---+，故()21512n a -++，这不可能，因为()212n a ++除以5的余数为1,3， 所以5P A ∈-．集合P A -的最小元素为5． 故答案为：5.4．（2021·全国·高三竞赛）质数p 和正整数m 满足32(2)1p m p m p ++=++，则p m +=___________.【答案】7 【解析】 【详解】由()221(1)p p m m +-=-，易见1m ，所以1p m -.设()1m kp k N +-=∈，则()2222,,(1)p p kp k p p k k p k k +=+==-.所以2k =，2,5p m ==，7p m +=.5．（2021·浙江·高三竞赛）已知集合{}12,,,n A a a a =⋅⋅⋅，n 为正整数.若对任意的1i j n ≤≠≤，i j a a -被4整除，但不被16整除，则n 的最大值为______.【答案】4 【解析】 【分析】 【详解】 考虑同余：对任意的1,i j i j n a a ≤≠≤-被4整除,则有(mod 4)i j a a k ≡≡,其中{0,1,2,3}k ∈, 而这类型的数模16的余数至多只有4种,所以n 最大值为4. 故答案为：4.6．（2021·浙江·高二竞赛）设数列123n n n a a a +⎡⎤⎡⎤=+⎢⎥⎢⎥⎣⎦⎣⎦，1n =，2，…，7这里[]x 表示不超过x的最大整数.若88a =，则正整数1a 有______种可能的取值情况.【解析】 【分析】根据高斯函数的性质，由88a =逐次往前求， 注意先定范围再验证，即可得到答案. 【详解】由88a =，可得710a =或11， 可得612a =或13或14； 可得515a =或16或17； 可得418a =或19或20或21； 可得322a =或23或24或25或26； 可得227a =或28或29或30或31或32；可得133a =或34或35或36或37或38或39，共7种.7．（2021·全国·高三竞赛）所有能使25n ⎡⎤⎢⎥⎣⎦为质数的正整数n 的倒数和为_________．【答案】3760【解析】 【分析】 【详解】1,2,3n =时，25n ⎡⎤⎢⎥⎣⎦都不是质数；4n =时，235n ⎡⎤=⎢⎥⎣⎦是质数；5n =时，255n ⎡⎤=⎢⎥⎣⎦是质数；6n =时，275n ⎡⎤=⎢⎥⎣⎦是质数．当8n ≥时，可设5n k r =±（其中k 为不小于2的正整数，0,1r =或2），则()22222111(5)2510(52)5555n k r k kr r k k r r =±=±+=±+， 所以2(52)5n k k r ⎡⎤=±⎢⎥⎣⎦．因为2k ≥，所以522k r ±>，所以2(52)5n k k r ⎡⎤=±⎢⎥⎣⎦不是质数．因此，能使25n ⎡⎤⎢⎥⎣⎦为质数的正整数n 只有4、5、6，它们的倒数和为1113745660++=．故答案为：3760. 8．（2021·全国·高三竞赛）若2020在p 进制下的各位数字之和为5p +，则质数p 的所有可能值为___________. 【答案】2,107 【解析】 【分析】 【详解】类似于在十进制下，我们有()()120|205p p --+⎡⎤⎣⎦， 于是()12014195|23p -=⨯⨯， 再注意p 为质数，就有2,3,107p =， 逐一验证得2p =或107p =. 故答案为：2,107.9．（2021·全国·高三竞赛）在1，2，3，4，…，1000中，能写成()221a b a N -+∈的形式，且不能被3整除的数有________个． 【答案】501. 【解析】 【详解】 设{}1,2,3,4,,1000S =，若221n a b =-+，则()3mod4n ≠.又()()2242211k k k =--+，()()2241111k k k +=+--+，()()22422121k k k +=+-+，因此，221n a b =-+当且仅当()3mod44n ≠.令(){|3mod44}A a S a =∈≡，(){|0mod3}B b S b =∈≡，则(){|3mod12}A B c S c ⋂=∈≡，因为250A =，333B =，84A B ⋂=，从而符合条件的数的个数为100025033384501--+=. 故答案为50110．（2020·浙江·高三竞赛）设a ，b ，c 为正整数，且2225548450a b c ab ac bc ++-+-=，则所有的解中a b c ++的最大值为___________. 【答案】30. 【解析】 【详解】配方得：222(22)50a c b a c ++--=（a ，c 等价）. 注意到：22250017=++，22250055=++，22250345=++. 不妨设a c ≤且22b a c ≥+，（1）当22017b a c a c --=⎧⎪=⎨⎪=⎩，即1167a b c =⎧⎪=⎨⎪=⎩，此时116724a b c ++=++=.（2）当22055b ac a c --=⎧⎪=⎨⎪=⎩，即5205a b c =⎧⎪=⎨⎪=⎩，此时520530a b c ++=++=.（3）当22534b a c a c --=⎧⎪=⎨⎪=⎩，即3194a b c =⎧⎪=⎨⎪=⎩，此时319426a b c ++=++=.（4）当22435b ac a c --=⎧⎪=⎨⎪=⎩，即3205a b c =⎧⎪=⎨⎪=⎩，此时320528a b c ++=++=.（5）当22345b a c a c --=⎧⎪=⎨⎪=⎩，即4215a b c =⎧⎪=⎨⎪=⎩，此时421530a b c ++=++=.综上所述，所有的解中a b c ++的最大值为30. 故答案为：30.11．（2020·江苏·高三竞赛）设正整数a ，b ，c ，d 满足23a b =，45c d =，且303b d -=，则a c -的值为___________． 【答案】123801 【解析】 【详解】解析：由题意可得a =c =b 必为完全平方数，d 一定能开4次方．设2b n =，4d m =，则()()223101b d n m n m -=+-=⨯，且注意到3，101都是质数，则223031n m n m ⎧+=⎨-=⎩或者221013n m n m ⎧+=⎨-=⎩，解得52n =，7m =，则35123801a c n m -=-=． 故答案为：123801.12．（2020·江苏·高三竞赛）设,m n N ∈，,2m n ≥，若33333333213111213112n m n m ----⋅=++++，则m n +的值为___________． 【答案】6 【解析】 【详解】解析：因为3311(1)111(1)1n n n n n n n n --++=⋅++-+， 累乘可得原式22(1)1222(1)33(1)n n n n n n n n ++++=⋅=++，则232333323122211n n m n n m m ++==+++--， 故223232221n n n n m +-=++-， 从而可得()2326131816162(1)(2)(1)(2)n n m n n n n n n ++⎛⎫-==+=+ ⎪+--+-+⎝⎭， 则()()1218n n -+，且,2m n ≥，在()()12n n -+的值为6，9，18， 故4n =，2m =．故6m n +=． 故答案为：6.13．（2021·浙江·高三竞赛）将顺序为1，2，…，2020的2020张卡片变成1011，1，1012，2，…，2020，1010的顺序，即原先的前1010张卡片移至第2，4，…，2020张，这称为一次操作.若从顺序1，2…，2020开始操作，则至少经过______次操作可以恢复到初始顺序. 【答案】1932 【解析】 【分析】 【详解】记第1i 次调整前的位置为i a ,调整后的位置记为1i a +,初始位置记为0a ,则112,101022021,1010i i i i a a a a a +≤⎧=⎨->⎩,所以102(mod 2021)2(mod 2021)n i i n a a a a +≡⇒≡, 因20214347=⨯,所以(2021)(43)(47)1932ϕϕϕ==, 所以193221(mod 2021)≡,要恢复原样,则0n a a =, 所以1932n =. 故答案为：1932.14．（2019·广西·高三竞赛）满足y =(x ，y )有____________ 对. 【答案】6 【解析】 【详解】设2251,2019,,n x m x n N m N =+=+∈∈. 224()()19682341m n m n m n -=+-==⨯⨯，由(m +n )与(m －n )奇偶性相同，可知它们同为偶数，且(m +n )>(m －n ) 实数对(m +n ，m －n )所有可能的取值共有6对：()32341,2⨯⨯，()322341,2⨯⨯，()32341,2⨯⨯， ()3241,23⨯⨯，()22241,23⨯⨯，()3241,23⨯⨯.由有序数对(x ，y )与(m +n ，m －n )一一对应，可知所求正整数对为6对. 故答案为：6．15．（2019·四川·高三竞赛）若正整数n 使得方程33n x y z +=有正整数解(x ，y ，z )，称n 为“好数”.则不超过2019的“好数”个数是_____ . 【答案】1346 【解析】 【详解】首先易知若n 为“好数”，则n +3也是“好数”又显然1、2是“好数”，从而当1,2(mod3)n ≡时，n 均为“好数”. 由费马(Fermat )大定理知：333x y z +=无正整数解，即3不是“好数”.于是n =3k (k ∈N *)都不是“好数”.否则，存在k ∈N *，使得3k 是“好数”，即方程333k x y z +=有正整数解(x ，y ，z 0)，从而333x y z +=有正整数解()000,,kx y z ，矛盾！故当且仅当n 满足1,2(mod3)n ≡时，n 为“好数”. 所以，不超过2019的“好数”个数是2201913463⨯=. 故答案为：1346． 二、解答题16．（2021·全国·高三竞赛）求证：对于正整数n ，令22n a ⎡⎡=+⎣⎣，数列{}n a 中有无穷多个奇数和无穷多个偶数（[]x 表示不超过实数x 的最大整数）． 【答案】证明见解析 【解析】 【详解】1212101100.101100bb c c =⋅⋅⋅=⋅⋅⋅⋅， 其中{}{}0,1,0,1i i b c ∈∈.用反证法，先证明数列中有无穷多个偶数．假设，数列中只有有限个偶数，那么存在整数N ，n N ∀>，n a 是奇数， 则存在正整数M ，使得1212101100101100M n M a bb b c c c =+，且当n M >时，{},{0,1}n n b c =，12(2)110110011N d d d ⋅∈Q ，矛盾！同理可证明数列中有无穷多个偶数．所以数列{}n a 中有无穷多个奇数和无穷多个偶数．17．（2021·全国·高三竞赛）使得A =n 为_________． 【答案】1或11##11或1 【解析】 【详解】,,,(,)1aa b a b b+=∈=N ，则222222222917647799n a a b b n n b b a b a -+=⇒==-++--． 又(,)1a b =，所以()()22222,9,1b b a b a -==，故22964b a -，所以229(3)(3){1,2,4,8,16,32,64}b a b a b a -=+-∈，229b a -模3余2，故2298b a -=或32，故3831b a b a +=⎧⎨-=⎩或3432b a b a +=⎧⎨-=⎩或33231b a b a +=⎧⎨-=⎩或31632b a b a +=⎧⎨-=⎩或3834b a b a +=⎧⎨-=⎩，所以(,)(1,1)=a b 或(7,3)，因此n 为1或11． 故答案为：1或11.18．（2021·全国·高三竞赛）设n 是正整数，12,,,k d d d 是n 的全部正因数.定义1212()(1)(1)(1)k d d d k f n d d d =-+-++-，已知()f n 是2的幂次，求证：n 没有1之外的平方因数.【答案】证明见解析 【解析】 【分析】设2(1)rn s r =≥，其中1i tai i s p ==∏，利用因数和函数可得()f n 与各质因数的关系，再根据()f n 是2的幂次结合反证法可得1i a =，从而可n 没有1之外的平方因数. 【详解】用()n σ表示n 的正因数之和.如果n 是奇数，则()()0f n n σ=-<，舍去. 当n 是偶数时，设2(1)r n s r =≥，其中1i tai i s p ==∏（i p 为n 的奇质因数，i a +∈N ，3i p ≥）.所以()()()111()2221()23i ta rr r i i f n s p σσ-+==+++-=-∏.其中()21i i a a i i i i p p p p σ=++++，因为()f n 是2的幂次，所以1231,1r r +-==，每个()i ai p σ是2的幂次，且i a 是奇数，又()()()12246111i i i a a a i i i i i i i i i p p p p p p p p p σ-=++++=++++++，故1246,11i a i i i i i p p p p p -++++++均为4的倍数，因为23,1(mod 4)i i p p ≥≡，所以如果1i α>，则1241,,,,i a i i i p p p -这些数的总个数是4的倍数，所以12211i a i i i p p p -++++.因为212(mod 4)i p +≡，所以121i a i i p p -+++不是2的幂次，于是1i a >不成立.所以1i a =，所以1ti i s p ==∏（i p 为互异的奇质因数），12ti i n p ==∏，可见n 没有非平凡的平方因数. 【点睛】思路点睛：竞赛中与正因数和有关的问题，多用因数和函数来分析处理，令注意利用因数分解定理把因数问题转化为即质因数的问题来处理.19．（2021·全国·高三竞赛）用()P n 表示正整数n 的各位数字之和，求所有这样的三位数n ，使得满足：1(3)()3P n P n +=．【答案】117、207、108. 【解析】 【分析】 【详解】由于(),(3)P n P n +都是正整数，则据条件，()P n 是3的倍数，因此n 与3n +都是3的倍数． 设n abc =，且数n 加3后必须产生进位，则7c ≥．（因为，如果6c ≤，则数n 加3后不会产生进位，于是(3)()3()P n P n P n +=+>，矛盾）并且b 不能是9，这是因为，若9b =，则当9a =时，99n c =，数n 加3后成为1100c ，1{0,1,2}c ∈，这时1(3)()3P n P n +<．当9a <时，9n a c =，若1113n a b c +=，则1111,0,310a a b c c =+==+-． 由3(3)()P n P n +=，得3[(1)0(310)]9a c a c ++++-=++， 即2()27a c +=，矛盾！所以9b <．今由3[(1)(310)]a b c a b c ++++-=++得9a b c ++=，其中1,7,8a c b ≥≥≤， 依次考虑c 、a 、b 的取值，得到三个数：117、207、108，验证知，它们皆合题意． 20．（2021·全国·高三竞赛）已知a 、b 、c 、d 是不同的正整数，且满足a b c da b b c c d d a+++++++是整数，求证：+++a b c d 不是质数． 【答案】证明见解析. 【解析】 【分析】 【详解】 由1a b c d a b c da b b c c d d a a b c d a b c d a b c d a b c d +++>+++=++++++++++++++++， 且a b c da b b c c d d a+++++++ 1111b c d aa b b c c d d a=-+-+-+-++++ 43b c d a a b b c c d d a ⎛⎫=-+++< ⎪++++⎝⎭，所以2a b c d a b b c c d d a+++=++++， 故2a c b d c aa b c d b c d a b c d a+=--=+++++++， 因此1111a c a b d a b c c d ⎛⎫⎛⎫-=- ⎪ ⎪++++⎝⎭⎝⎭， 所以()()()()d b d b a c a b d a b c c d --⋅=⋅++++且d b ≠， 所以()()()()a b c c d c a b d a ⋅++=⋅++，即22ac abd a c bcd +=+． 整理得()()0ac c a bd a c -+-=且a c ≠，所以ac bd =． 假设p a b c d =+++是质数，则 2()a a b c d a ab ac ad +++=+++ 2a ab bd ad =+++ ()()a b a d ap =++=，所以()p a b +或()p a d +，而,p a b p a d >+>+，矛盾． 综上+++a b c d 不是质数．21．（2021·全国·高三竞赛）解关于实数x 的方程：{}202020201arctank x x k==∑（这里{}[][],x x x x =-为不超过实数x 的最大整数） 【答案】{}0 【解析】 【分析】【详解】（1）当0x <时，{}202020201arctan 0(1,2,,2020),arctan 0k x x k x k k =<=<≤⋅⋅⋅∑，此时原方程无解．（2）当0x =时，有{}202020001arctan0k x x k===∑． （3）当01x <<时，令arct ()1)2an (0x xf x x =-<<，则211()0(01)12f x x x '=-><<+， 故()f x 在()0,1上递增．有()()00f x f >=，即arctan 2x x > 于是，此时{}202020204202020201111125arctan 2224k k k x x x xx x x k k k =====>>=>∑∑∑，即1x >，矛盾．故无解．（4）当1≥x 时，注意到111123tan(arctan arctan )112316++==-， 且由110arctan arctan arctan1arctan1232π<+<+=，知11arctan arctan 234+=π．则{}20202020202011111arctan arctan arctan1arctan arctan 1232k k x x k k π===≥>++=>∑∑，与{}202001x <<，矛盾．故此时无解．由（1）（2）（3）（4），知原方程的解集为{}0．22．（2021·全国·高三竞赛）两两不等的实数x 、y 、z 满足222(2)(2)(2)y x z y x z ⎧=-⎪=-⎨⎪=-⎩，求x y z ++.【答案】5或6. 【解析】 【分析】 【详解】由原方程变形可得到1(1)(3)1(1)(3)1(1)(3)y x x z y y x z z -=--⎧⎪-=--⎨⎪-=--⎩和4(4)4(4)4(4)y x x z y y x z z -=-⎧⎪-=-⎨⎪-=-⎩，又由x 、y 、z 两两不等知,,1,4x y z ≠， 于是()()()3331x y x xyz ---==.令,p x y z q xy yz zx =++=++，化简得39p q =+. 另一方面，原方程三式相加得2(2)412p p q p =--+， 化简得25122p p q -+=，联立就有26530p p p =-+，即5p =或6. 最后，当22224cos 744cos 784cos 7x y z ππ⎧=⎪⎪⎪=⎨⎪⎪=⎪⎩时可以取到5，当2224cos 924cos 944cos 9x y z πππ⎧=⎪⎪⎪=⎨⎪⎪=⎪⎩时可以取到6.23．（2021·全国·高三竞赛）若关于z 的整系数方程320z pz qz r +++=的三个复数根在复平面内恰好成为一个等腰直角三角形的三个顶点，求这个等腰直角三角形的面积的最小值. 【答案】1 【解析】 【分析】 【详解】设该等腰直角三角形斜边中点对应的复数为1z ，直角顶点对应的复数为()1220z z z +≠， 则另外两个顶点对应的复数分别为12z z i +和12z z i -，依题意有： 32121212()()()z pz qz r z z z z z z i z z z i +++=-----+，化简得223223111221112223,32,z x z p z z z z q z z z z z z r +=-++=+++=-，所以3222221223,489z z q p Z z z pq r Z =-+=-∈∈.进而122z z Q +∈，与123z z p Z +=-∈联立就有2z Q ∈.再由22223x q p Z =-∈知2z Z ∈，于是21z ≥，所以等腰直角三角形的面积最小为1.另一方面，3210z x z +++=的三个复数根恰是面积为1的等腰直角三角形的顶点. 24．（2021·全国·高三竞赛）证明：存在无穷多个奇数n ，使得!1n +是合数． 【答案】证明见解析 【解析】 【分析】 【详解】证明当奇数(3)n n ≥时，!1n +与(!)!1n n -+不均为质数即可： 用反证法，若!1n +为质数，设!1n p +=，则结合威尔逊定理可得： 111(!)!(1)!(1)!(1)(2)()(mod )n n p n p n p ----=--≡----1(1)!(1)1(mod )n n n p +≡--⋅≡--≡-，此时有(!)!1n n -+为合数，而n 奇数得!n n -也是奇数， 从而存在无穷多个奇数n ，使得!1n +是合数．25．（2019·山东·高三竞赛）已知4239n n -+是素数，求正整数n 的所有可能值 【答案】n =1，n =2 【解析】 【详解】因为()()4222393333n n n n n n -+=++-+，所以或n 2－3n +3=1，解得n =1，2.将n =1，n =2代入检验均满足题意，所以n =1，n =2为所求.26．（2021·全国·高三竞赛）求方程(31)(31)(31)34x y z xyz +++=的所有正整数解(,,)x y z ． 【答案】(,,)(28,5,2),(11,7,2)x y z =或其排序，共12组解． 【解析】 【详解】 不妨设x y z ≥≥．若z >31z +<．同理，31,31x y +<+<． 三式相乘得(31)(31)(31)34x y z xyz +++<，与原方程矛盾． 于是，5z ≤<． （1）若1z =，则4(31)(31)346()20x y xy xy x y ++=⇒+++=．显然，无正整数解．（2）若2z =，则7(31)(31)68521()70(521)(521)x y xy xy x y x y ++=⇒-+-=⇒--=24762717=⨯⨯．只有47611941434=⨯=⨯，才有对应的正整数,x y ，此时(,)(28,5)x y =或(11,7)． （3）若3z =，则10(31)(31)102615()50x y xy xy x y ++=⇒-+-=．两边取模3即知矛盾，故无解． （4）若4z =，则13(31)(31)1361939()130x y xy xy x y ++=⇒-+-=3(1939)(1939)176821317x y ⇒--==⨯⨯．故此时(1939)42y -≤，故39y ≤≤，逐一检验后无解. 综上，(,,)(28,5,2),(11,7,2)x y z =或其排序，共12组解．27．（2021·全国·高三竞赛）求方程||1r s p q -=的整数解，其中p ､q 是质数，r ､s 是大于1的正整数，并证明所得到的解是全部解. 【答案】证明见解析 【解析】 【详解】容易看到两个质数中肯定有一个为2，不妨假设2,21r sp q =-=，即21r s q -=±.若21r s q =+，从余数去讨论，3(mod4)q ≡，s 为奇数.()1221(1)1rss s q q qq--=+=+-++，所以121212,12,r r s s q q q --⎧+=⎨-++=⎩()1111111(1)(1)(2)2211222222sr sr s r r r s r s r r s s s s ---⎡⎤=-+=-++=-++⎣⎦，从奇偶性可以看出这种情形方程无解.若21r s q =-为偶数，注意到()1221(1)1r s s q q q q --=-=-+++，所以121212,12,r r s s q q q --⎧-=⎨+++=⎩()11111(1)21221122(1)22sr sr s r r r r s s s s --=+-=+++-+.令2u s v =，其中v 为奇数，则 ()11111(1)21221122(1)22sr sr s r r u r u r s v s v --++=+-=+++-+，观察最后一项，则v 为1，故2u s =，所以221ur q =-，故()()1122211u u r q q --=-+，故1112221212u u r r q q --⎧-=⎪⎨+=⎪⎩，所以12222r r +=，所以121,2r r ==，1u =， 所以3q =，3r =，2s =，综上，考察到对称性，原方程恰有两组解：3,2,2,3.p q r s =⎧⎪=⎪⎨=⎪⎪=⎩或2,3,3,2.p q r s =⎧⎪=⎪⎨=⎪⎪=⎩ 28．（2021·全国·高三竞赛）证明：对任意正整数N ，都存在正整数n N >和n 个互不相同的正整数12,,,n x x x ，使()222222121220202020n n x x x x x x -++++是完全平方数．【答案】证明见解析 【解析】 【详解】对于3m ≥，必存在不同的正整数12,,,m x x x 满足2221212m m x x x x x x S =++++，令{}112121max ,,,m m m x x x x x x x +=->，则有()21211212m m m m x x x x x x x x x x +=-()2121211m m x x x x x x =-+-()()2222121211m m x x x x x x S =-++++-22221211m m x x x x S +=++++-．以此类推，当504S >时，存在不同的正整数11504,,,,,m m m S x x x x ++-满足2221250412504504m S m S x x x x x x +-+-=++++．存在6N ≥，定义(1)k x k k N =≤≤，则()2221212504N N x x x x x x -+++>．由前述结论可得存在n N >使得()2221212504n n x x x x x x -+++=，此时()2222222222121212122020202020201010n n n n x x x x x x x x x x x x -++++=-+()2121010n x x x =-为完全平方数．29．（2021·浙江·高三竞赛）已知素数p ，q 满足21p q =+.证明：存在正整数m 使得mp 的十进制表示的各位数字之和是2或3. 【答案】证明见解析 【解析】 【分析】 【详解】2p =，3不合题意，若5p =则取110mp =即可.下面假设7p ≥.由费马小定理()()12101101101101p q q q p --=-=+-可知101q p +或101q p -.前者意味着取101q mp =+满足条件.若是101qp -，我们断言{}012110,10,10,,10q A -=⋅⋅⋅中的数模p 两两不同余，即有q 个不同的余数.这是因为若有()1010mod a b p ≡，（01a b q ≤<≤-）则()101mod b a p -≡，由b a -与q 互素以及裴蜀定理知存在正整数u ，v 使得()1u b a vq --=，这样 ()()()1110101010mod uvb a vq q p -+≡==⨯.这意味着1019p -=即3p =，不合题意因此{}012110,10,10,,10q A -=⋅⋅⋅中的数模p 两两不同余.设它们的余数是{}{}12,,,1,2,,1q B r r r p =⋅⋅⋅⊆⋅⋅⋅-. 我们考虑下面的52p -个余数对，它们覆盖了除了0，1，12p -，2p -，1p -之外的所有余数：()2,3p -，()3,4p -，…，31,22p p -+⎛⎫⎪⎝⎭ 若某个对子的两个余数都在B 中出现，不妨设10a k ≡，101b p k ≡--，则10101a b mp =++是p 的倍数，满足题意.若每个对子中的余数都在B 至多出现一个的话，由于12p B -=，所以0，1，12p -，2p -，1p -在B 中出现至少两个，已知1B ∈，0B ∉，其余三个余数12p -，2p -，1p -至少有一个在B 中出现. 若12p B -∈，即有某个1102a p -≡，则2101a mp =⨯+满足题意.若2p B -∈，即有某个102a p ≡-，则102a mp =+满足题意. 若1p B -∈，有某个101a p ≡-，则101a mp =+满足题意. 综上所述，存在p 的倍数的十进制数字和是2或3.30．（2021·全国·高三竞赛）设m 是一个给定的正整数，d 是它的一个正因子．已知{}0i i a ∞=和{}0i i b ∞=是两个由正整数构成的等差数列，满足：存在正整数i 、j 、k 、l ，使得()(),1,,ijkla b a b m ==．证明：存在正整数t 、s 使得(),t s a b d =．【答案】证明见解析 【解析】 【分析】 【详解】注意到m 可逐次除以它们若干素因子得到d ，这样只需证对m 的任意素因子p ，存在正整数α、β，使得(),ma b pαβ=． 由于(),k t a b m =，故k a p 、l b p 必有一项不能被m 整除．不妨设k ab不能被m 整除． 设等差数列{}i a 、{}j b 的公差分别为u 、v ，则0i a a iu =+，0j b b jv =+． 下面分两种情况：（1）若p v ．令,k a k l p αβ==+．这时k l a vb b pβ=+． 注意到k m ma b p pβ、，又p v 且k a m p ，所以m b β．这说明m p 是a α、b β的公因子，且m 不是它们的公因子．设q 是a α、b β的一个不同于p 的公因子，则q a α、q b β、a qpα． 故,a q a b v p ααβ⎛⎫- ⎪⎝⎭，即(),k t q a b m =．又p q ，故mq p ．故(),m a b p αβ=．（2）若p v ．先证p u ． (*)事实上，假设p u ，由(),k l a b m =知00,k l p a ku a p b lu b -=-=．因此,i j p a p b ，这与(),1ija b =矛盾！故（*）得证．取正整数s ，使得l s b p能被mp 整除，但不能被m 整除． 令,l sb k l p αβ=+=．这时,l kl s b a a u b b p αβ=+=． 注意到k m a p 、l m b p、lsb m p p ，所以m p 是a α与b β的公因子．又lsb m p ，且p u ，所以m a α，从而m 不是a α、b β的公因子．设质数q 是a α，b β不同于p 的公因子，则q b β，l k sbq a u a p α⎛⎫-= ⎪⎝⎭． 即(),k l q a b m =． 又q p ≠，所以mqp．这说明(),m a b p αβ=．由（1），（2）知结论成立．31．（2021·全国·高三竞赛）设多项式02()()(2)==+≥∑dii i P x a x a d 的系数为正整数．定义数列{}n b ：()101,(1)n n b a b P b n +==≥．证明：对于任意的整数2n ≥，均存在质数p ，使得n p b ，且()121,1n p bb b -=．【答案】证明见解析 【解析】 【分析】 【详解】假设存在整数2n ≥，使得n b 的任意一个质因子均为某个(11)i b i n ≤≤-的因子（对于n b 的不同的质因子，i 的取值可以不同）．令p 为n b 的一个质因子，且rn b p l =，其中,,(,)1r l p l +∈=N ． 则110012()()(mod )dr i r n n i i b P b a p l a a b p ++===+≡=∑假设()1mod ,r n i i b b p i +++≡∈N 成立，则()()()111mod r n i n i i i b P b P b b p +++++=≡=．所以由数学归纳法知对任意的正整数i ，均有()1mod r n i i b b p ++≡．进而有()12mod r n n kn b b b p +≡≡≡，所以1r kn n p b b +-．定义()p V m 表示正整数m 的标准分解中所含的p 的幂次数， 由()p n V b r =，得()p kn V b r =．令i p b 对某个(11)i i n ≤≤-成立，同上可证()()()23p i p i p i V b V b V b ===．于是()()()p n p in p i V b V b V b r ===．从而，若p 为n b 的一个质因子，则它在n b 的中的次数等于在某个(11)i b i n ≤≤-中的次数． 所以121n n b bb b -，进而121n n b b b b -≤．由()211n n n b P b b --=>，得21kn n k n b b b --<，所以111211n i n n i nn i i b bb ---==<<∏∏，矛盾，故原命题成立．32．（2021·全国·高三竞赛）一个大于1的整数m ，如果对所有的正整数n ，都存在正整数x 、y 、z ，使得222n mx y z =--，则称m 为上数，否则称为下数．试问：是否存在无数多的上数？是否存在无数多的下数？【答案】存在无数多个上数也存在无数多个下数． 【解析】 【分析】 【详解】存在无数多个上数也存在无数多个下数．首先，存在无数多个下数．考查93m k =+，其中k 为正整数．考查不定方程2226(93)k x y z =+--，若存在解x 、y 、z 则220(mod 3)y z ≡+， 故有()0mod3y z ≡≡，所以2222(93)36(mod 9)k x y z x +--≡≡，即2(mod3)x ≡，矛盾．故无解． 即所有的93k +为下数．其次，我们证明存在无数多个上数，我们考查21c +，其中222c a b =+（a 、b 、c 为勾股数）．（1）注意到22222(1)(1)21c x c x x x +---=-，可知所有的奇数1n >，均存在解． 又22211c a b =+--，可知所有奇数均存在解．（2）对于n 为偶数的情形，考查222222(1)(1)(2)4454(2)9c x cx x c x c c x c +---+-=-+-=---． 令c 为奇数，故有24(2)9x c ---可以为所有模4余2的数． （3）而对于4|n ，可以转为考查2224222n x y z m ⎛⎫⎛⎫⎛⎫=-- ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭的问题，不断转化．终会归为（1）或是（2）其中的一类．而存在无数多个勾股数a 、b 、c （a 、b 、c 互质），即存在无数多个满足题意的21c +． 即有无数多个上数．33．（2021·全国·高三竞赛）如果正整数n 满足存在正整数a 、b 、c 使得()()()()()(),,,,,,n b c a bc c a b ca a b c ab =⋅+⋅+⋅，则称n 为好数．求证：存在连续2020个正整数这2020个正整数都是好数．注：对于正整数x ，y ，(),x y 表示x ，y 的最大公因数． 【答案】证明见解析 【解析】 【分析】 【详解】取121111121,(2),1,(2)(2,3,,2020)i i i l i i l x y x x x y y x x i -===+=-⋅⋅⋅=+=∏．对2,3,,2020i =，由()()1,1,21i i i i x x x x +=++=，知,2i i x x +均与121,,,i y y y -互质，故i y 与121,,,i y y y -均互质．则122020,,,y y y 两两互质．对1,2,3,,2020i =，考查i y 的一个倍数，设为()22i i i n my mx x ==+．注意到取2,,i i i a mx b mx c x ===，则有()()()()()(),,,,,,n b c a bc c a b ca a b c ab =⋅+⋅+⋅． 故n 为好数．则由n 的任意性，知i y 的一切倍数均为好数． 注意到122020,,,y y y 两两互质，那么由中国剩余定理知关于x 的同余方程组()()mod 1,2,,2020i x i y i ≡-=有正整数解0x ．这意味着对1,2,3,,2020i =，有0x i +是i y 的倍数，因此0x i +是好数． 取()01,2,,2020x i i +=即可满足题意．34．（2021·全国·高三竞赛）设函数:f N N ++→同时满足以下三个条件： （1）对任意x 、y N +∈，有()()()f xy f x f y =； （2）对任意x N +∈，有()()f f x x =； （3）()220()20f x x x ≠≤≤． 求()2f 的最小值． 【答案】1013． 【解析】 【分析】 【详解】在()()()f xy f x f y =中令1x y ==，得()11f =．①设质数p 满足()f p 不是质数，若()1f p =，则由（2）及①， 有()()()11p f f p f ===，矛盾．故()f p 为合数，设()f p xy =（x ﹐y 均为大于1的正整数）， 则()()()()()p f f p f xy f x f y ===．不妨设()1f x =，则()()()11x f f x f ===，与1x >矛盾． 因此，若p 是质数，则()f p 也是质数．由（1）、（2），有()()()()()()222222f f f f f f ==， 则由()22f 是偶数以及（3），得()222022f ≥． 因为()2f 是质数，所以()21013f ≥．另一方面，设小于2020的且不等于2或1013的质数有t 个，从小到大依次为12t p p p <<⋅⋅⋅<， 大于2020的质数中，最小的t 个从小到大依次为12t q q q <<⋅⋅⋅<考虑如下定义的函数:f N N ++→：()()()()()()11,21013,10132,,1,2,,i i i i f f f f p q f q p i t ======，且对质数t p q >，有()f p p =．对于合数1i ki i y r α==∏，其中质数12k r r r <<⋯<，且12k N ααα+⋯∈、、、，12k i i α=≥∑，有1()(())i ki i f y f r α==∏． 此时，不难验证f 满足（1）、（2）．且对于正整数()22020x x ≤≤，若x 为质数，显然()f x x ≠，若x 是合数，设1jlj j x s β==∏，其中质数12l s s s <<⋯<，且121,,,,2ll j j N ββββ+=∈≥∑．于是，由f 的定义知()f x 一定为至少两个，且每个均不小于1013的正整数的乘积， 故()2020f x x ≥≥，则f 满足（3）． 综上，知()2f 的最小值为1013．35．（2021·全国·高三竞赛）对每个正整数n ，定义()f n 为从1到n 中所有与n 不互质的正整数的和.求证：若()()f m f n =且m n ≠，则m n -是合数. 【答案】证明见解析 【解析】 【分析】 【详解】首先计算()f n 的表达式，注意到从1到n 中所有与n 互质的正整数有()n ϕ个，并且它们是以t 和n t -的形式成对出现的，因此111()(1)()(1())222f n n n n n n n n ϕϕ=+-⋅=+-.若()()f m f n =且m n ≠，不妨设m n >，则()()()()11m m m n n n ϕϕ+-=+-.① 因为()11n n n m ϕ≤+-≤<，所以(),1m n >.若m n -不为合数，设为质数p ，则()1n kpm p k ==+﹐， ①式变为()()()()()()11111k k p k p k kp kp ϕϕ+++-+=+⎦-⎡⎤⎣.由(),11k k +=，可设()()()()()111,11k p k p lk kp kp l k ϕϕ++-+=+-=+ 其中0l p <<，相减得()()()1k p kp p l ϕϕ+-=+，1k =时， ()()21p p p l ϕ--<+不合题意，所以2k ≥，2p =时，()()()1,1l k p kp p l ϕϕ=+-=+左右奇偶性不同，所以3p ≥.注意()()()()()1,11p kp p k p ϕϕ--+，因此()()1|p p l -+.又0,3l p p <<≥，所以2l p =-，所以()()()121,23k p k p kp k p ϕϕ+=++=-+. 若|p k ，则()|p kp ϕ，所以()3|2p k p -+，所以3p =， 所以()()()12121k p k k p ϕϕ+=+<++，矛盾，同理若()1|p k +也得矛盾，所以()()1121p k k p ϕ-+=++，()()123p k k p ϕ-=-+，②所以()()12k k ϕϕ+-=，于是()1k ϕ+和()k ϕ恰有一个不是4的倍数，必模4余2，但()s ϕ模4余2当且仅当4,,2a a s q q =，这里q 是模4余3的奇质数，a 是正整数，分别代回②知都无解.综上，若()()f m f n =且m n ≠，则m n -是合数.36．（2021·全国·高三竞赛）已知正整数,1n n >，设A 为正整数满足2|1n n A ⎡⎤+⎢⎥⎣⎦，求所有A 的值．（[]x 表示不超过x 的最大整数）【答案】当2n =时，3A =，或4，当2n >时，1A n =+． 【解析】 【分析】 【详解】（1）如果2A n >，则211n A ⎡⎤+=⎢⎥⎣⎦，由1n >知，2 1n n A ⎡⎤+⎢⎥⎣⎦；（2）如果2A n =，则212n A ⎡⎤+=⎢⎥⎣⎦，由21n n A ⎡⎤+⎢⎥⎣⎦∣及1n >知2n =，从而4A =；（3）如果20A n <<，则令22n n A r A ⎡⎤=+⎢⎥⎣⎦，其中20r A n ≤<<，即221()n n A A r A ⎛⎫⎡⎤=+-- ⎪⎢⎥⎣⎦⎝⎭． ①当2n A n <<时，222,11n n n n n A A A ⎡⎤⎡⎤<<+<+⎢⎥⎢⎥⎣⎦⎣⎦，由21n n A ⎡⎤+⎢⎥⎣⎦∣，可设21n nH A ⎡⎤+=⎢⎥⎣⎦， 于是1nH n <+，即()11n H -<，这样，只有1H =成立，所以21n n A ⎡⎤+=⎢⎥⎣⎦．代入①式得()2n nA A r =--，即21111n r r A n n n --==+---． 若1r ≠，则11r n --是不小于1的正整数，于是A n ≤，与A n >矛盾， 因此1r =，故1A n =+．当A n =时，211n n A ⎡⎤+=+⎢⎥⎣⎦，由n ∈+N 知211n n n A ⎡⎤+=+⎢⎥⎣⎦；当0A n <<时，由①式及21n n A ⎡⎤+⎢⎥⎣⎦∣知，n A r -∣． 又0,0A n r A n <<≤<<，从而0A r n <-<，矛盾． 综上，当2n =时，3A =，或4，当2n >时，1A n =+．37．（2021·全国·高三竞赛）证明：对任何正整数m ，存在无穷多组整数(),x y ，使得 （1）,x y 互质； （2）2|x y m +； （3）2|y x m +． 【答案】证明见解析. 【解析】 【分析】 【详解】显然，当1x y ==时，符合题意．若正整数对()(),x y x y ≤满足条件，由条件（2）可设2xx y m '=+，其中x Z +'∈．下证命题：正整数对(),y x '也满足条件，且y x <'． 由等式2xx y m '=+知，2xx y yx '>≥，即x y '>． 同时还可知，2|x y m '+且()cd ,|g x y m '．若p 是()gcd ,x y '的一个质因子，则有,p m p y ．结合条件（3）有2|p x m +，从而有|p x ． 这与条件（1）矛盾．故()gcd ,1x y '=．最后，还需证2yx m '+∣．由于gcd(,)1x y =，等价证()22y x x m '+∣． 其中()()()2222220(mod )x x m y m x m m m x y '+=++≡+≡．命题得证，且x y x '>≥．反复利用此命题，便可得到无穷数列{}n a ，其中()212211,n n n a m a a a n a ++++===∈N ． 满足1n n a a +>对2n ≥成立，且整数对()()1,n n a a n ++∈N 符合条件．38．（2021·全国·高三竞赛）正整数2n ≥，且n 的素因子个数不超过2，对于任意整数a ，若(),1n a =，则有()mod n a a n ≡成立，求证：n 是质数.【答案】证明见解析. 【解析】 【分析】 【详解】假设n p q αβ=，（其中p q 、均为质数，N αβ∈﹐）. 首先证明：p q ≠，若n p γ=（p 为质数，γαβ=+）.因为(),1n a =，所以取最小整数δ，使得()1mod a p δγ≡（易知δ为a 对模2p 的阶）.又()111(mod )1mod n n an a p γ--≡⇔≡，所以()()1(1),(1)1p p p n p γγγδϕδδ-=--⇔-∣，所以1p δ-∣. 取()()()11111111(1)11mod p p a p p a p p p p p γγγγγγ------=--⇒≡-≡--+≡+，矛盾.所以n p p q γ≠⇒≠.任取与p q 、互质的a ， 由Euler 定理知：()()1(mod ),()(1)(1)n an n p q p q ϕαβϕϕ≡==--.从而()()1|1p q δ--，又因为()|(1)|1n p q αβδδ-⇒-，所以()11111p q p q p q αβαβαβδ----+--∣.所以111111(mod )p qp q p q a n αβαβαβ----+--≡，所以()111mod p q a p αβα--≡，所以()111mod q p q a p αα--≡.同理()111mod p q aq αββ--≡.不妨设p q >，则p 一定是奇质数.因此它存在原根g ，满足()11mod q gp α-≡/.因此，一定存在整数k ，使得q kp g α+，取a kp g α=+，矛盾! 结合2n ≥，知n 只能有一个质因子，即n 是质数. 又由Fermat 小定理知，当n 为质数时，满足题意.39．（2021·全国·高三竞赛）设a ，b 为正奇数，定义数列{}n f 如下：1f a =，2f b =，当3n ≥时，n f 为12n n f f --+的最大奇因子.求证：当n 充分大时，n f 为常数，并确定出这个常数. 【答案】a ，b 的最大公约数. 【解析】 【详解】从题目条件可以知道，如果有相邻两项k f ，1k f +相等，则当n k ≥时，n f 全相等，为常数. 用反证法，如果n f 不为常数，则序列{|}n f n N ∈的任意相邻两项不等.由于1n f -，2n f -皆为奇数，则12n n f f --+为偶数.那么，有(){}12121max ,2n n n n n f f f f f ----≤+<，于是，有 {}{}{}3456max ,max ,max ,...a b f f f f >>>.显然，这无限递降正奇数数列不存在，矛盾.所以，必存在正整数k ，使得1k k f f +=，即当n k ≥时，n k f f =.设此常数为C ，由于122an n n f f f --+=，这里a 是个正整数，以及n f ，1n f -，2n f -均为奇数，可知1n f -，2n f -的最大公约数()12,n n f f --等于n f ，1n f -的最大公约数()1,n n f f -.从而，序列中任意相邻两项的最大公约数相同.那么，()(),...,C C C a b ===，即这常数为a ，b 的最大公约数.40．（2020·全国·高三竞赛）设12121,2,2,3,4,n n n a a a a a n --===+=证明：对整数5n ≥，n a ，必有一个模4余1的素因子． 【答案】证明见解析. 【解析】 【分析】不妨记11αβ==由递推式及数学归纳法得到n a 有奇素因子p ，然后对正整数进行讨论，证明也存在模4余1的素因子. 【详解】证明：记11αβ=+=-n n n a αβαβ-=-．记2n nn b αβ+=，则数列{}n b 满足122(3)n n n b b b n --=+≥ ①因121,3b b ==均为整数，故由①及数学归纳法，可知{}n b 每项均为整数．由222()22n n n n n αβαβαβαβαβ⎛⎫⎛⎫+--⎛⎫-= ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭， 可知222(1)(1)nn n b a n -=-≥ ②当1n >为奇数时，由于1a 为奇数，故由{}n a 的递推式及数学归纳法，可知n a 为大于1的奇数，所以n a 有奇素因子p ．由②得21(mod )n b p ≡-，故112(1)(mod )p p n b p --≡-．又上式表明(),1n p b =，故由费马小定理得11(mod )p n b p -≡，从而12(1)1(mod )p p --≡．因2p >，故必须12(1)1p --=，因此1(mod 4)p ≡．另一方面，对正整数m ，n ，若|m n ，设n km =，则()(1)(2)(2)(1)n n m mk m k m m m k m k m n a αβαβααβαββαβαβ------==⋅++++--()0(212)(212)1(22)(22)1()(),2=(()(),21i im l i m l i m m l i lm im l i m l i m m l a k l a k l αβαβαβαβαβ=-----=---⎧⋅∑+=⎪⎨⎪⋅∑++=+⎩因2s ss b αβ+=为整数（对正整数s ），1αβ=-为整数，故由上式知n a 等于m a 与一个整数的乘积，从而|m n a a ．因此，若n 有大于1的奇因子m ，则由前面已证得的结论知m a 有素因子1(mod 4)p ≡，而|m n a a ，故|n p a ，即n a 也有模4余1的素因子．最后，若n 没有大于1的奇因子，则n 是2的方幂．设2(3)l n l =≥， 因84082417a ==⨯有模4余1的素因子17，对于4l ≥，由8|2l 知82|l a a ， 从而2l a 也有素因子17．证毕． 【点睛】关键点点睛：本题证明的关键是能够运用数论整除的相关知识以及费马小定理进行证明，不漏掉情况.41．（2019·江苏·高三竞赛）设k 、l 、c 均为正整数，证明：存在正整数a 、b 满足(,)b ac a b -=⋅，且()(),(,)a b l kb a a b a b ττττ⋅=⋅⎛⎫⎛⎫ ⎪ ⎪⎝⎭⎝⎭，其中(a ，b )表示a 、b 的最大公因数，()m τ表示正整数m 的所有不同正因子的个数. 【答案】见解析 【解析】 【详解】如果m 的标准分解式为1212n n n m p p p ααα=，那么()()()12()111n m τααα=+++.取定两个不同的素数p 、q 使得(pq ，c )=1.由于(p ，q )=1，利用裴蜀定理，存在正整数00,u v ，使得00k lp u q v c -=.由于(pq ，c )=1，那么0p v 且0q u . 由中国剩余定理，下列同余方程组：0001(mod )1(mod )1(mod )l kl u tq p v tp q u tq c ⎧+≡⎪+≡⎨⎪+≡⎩有正整数解t t =0. 令0000,l ku u t q v v t p =+=+，那么k l p u q v c -=，而且(u ，pqc )=1.因此(,)1,(,)1v pqc u v ==.现在取2211,k l l d p q n q v --==，则l k n c q v c p u +=+=. 从而(,)1n n c +=.令a =nd ，b =(n +c )d ，那么(a ，b )=d ，因此(,)b a cd c a b -==⋅.而且：()()2211()()(),k ll l p q va nd l l la n q v ab ττττττ-+-⋅=⋅=⋅⎛⎫⎪⎝⎭()22221k l l l k l l +==+.()()2211()(())(),kk l kp qub ncd k k k b n c p u a b ττττττ+--+⋅=⋅=⋅+⎛⎫⎪⎝⎭()22221kk l k k l k +==+.所以()()(,)(,)a b l ka b a b a b ττττ⋅=⋅⎛⎫⎛⎫ ⎪ ⎪⎝⎭⎝⎭.42．（2019·江西·高三竞赛）试求所有由互异正奇数构成的三元集{a ，b ，c }，使其满足：2222019a b c ++=.【答案】7个，{1,13,43},{7,11,43},{13,25,35},{5,25,37}，{}11,23,37，{17,19,37},{7,17,41}. 【解析】 【详解】据对称性，不妨设a <b <c ，由于奇平方数的末位数字只具有1、5、9形式，于是222,,a b c 的末位数字，要么是5、5、9的形式，要么是1、9、9的形式.又知，如果正整数n 是3的倍数，那么n 2必是9的倍数；如果n 不是3的倍数，那么n 2被3除余1.由于2019是3的倍数，但不是9的倍数，因此奇数a 、b 、c 皆不是3的倍数. 注意[2019]44c =，即奇数c ≤43，而222232019c a b c >++=， 即c 2>673，且c 不是3的倍数，故奇数c ≥29. 因此奇数{29,31,35,37,41,43}c ∈.。

数学竞赛中的数论问题罗增儒引言数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支．什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，…是这样一个集合N +：（1）有一个最小的数1．（2）每一个数a 的后面都有且只有一个后继数/a ；除1之外，每一个数的都是且只是一个数的后继数． 这个结构很像数学归纳法，事实上，有这样的归纳公理：（3）对N +的子集M ，若1M ∈，且当a M ∈时，有后继数/a M ∈，则M N +=．就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度．比如，哥德巴赫猜想：1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和．后者是前者的推论，也可独立证明（已解决）．“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1．欧拉认为这是对的，但证不出来．1900年希尔伯特将其归入23个问题中的第8个问题． 1966年陈景润证得：一个素数+素数⨯素数（1+2），至今仍无人超越．●陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠．……”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥．●数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了．任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（U ．Dudley 《数论基础》前言）．下面，是一个有趣的故事．当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有1n +个正整数，这些正整数小于或等于2n ，那么你一定有一对整数是互素的，你知道这是什么原因吗？不到12岁的波萨只用了1分半钟，就给出了问题的解答．他将1～2n 分成（1，2），（3，4），…，（21,2n n -）共n 个抽屉，手头的1n +个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素．通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”．●重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）．高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题．数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目．数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程．在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x ]，费马小定理，格点及其性质，无穷递降法，欧拉定理*，孙子定理*．根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型： （1）奇数与偶数（奇偶分析法、01法）； （2）约数与倍数、素数与合数； （3）平方数； （4）整除； （5）同余； （6）不定方程；（7）数论函数、[]x 高斯函数、()n ϕ欧拉函数；（8）进位制（十进制、二进制）．下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解．第一讲 数论题的基本内容中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理． 首先约定，本文中的字母均表示整数．定义1 （带余除法）给定整数,,0,a b b ≠如果有整数(),0q r r b ≤<满足 a qb r =+，则q 和r 分别称为a 除以b 的商和余数．特别的，0r =时，则称a 被b 整除，记作b a ，或者说a 是b 的倍数，而b 是a 的约数．（,q r 的存在性由定理1证明）定义2 （最大公约数）设整数12,,,n a a a 中至少有一个不等于零，这n 个数的最大公约数是能整除其中每一个整数的最大正整数，记作()12,,,n a a a ．()12,,,n a a a 中的i a 没有顺序，最大公约数也称最大公因数．简单性质：()()1212,,,,,,n n a a a a a a =．一个功能：可以把对整数的研究转化为对非负整数的研究． 定义3 （最小公倍数）非零整数12,,,n a a a 的最小公倍数是能被其中每一个()1i a i n ≤≤所整除的最小正整数，记作[]12,,,n a a a ．简单性质：如果k 是正整数,a b 的公倍数，则存在正整数m 使[],k m a b =证明 若不然，有[],k m a b r =+（[]0,r a b <<），由[],,k a b 都是,a b 的公倍数得r 也是,a b 的公倍数，但[]0,r a b <<，与[],a b 的最小性矛盾．故[],k ma b =．定义4 如果整数,a b 满足(),1a b =，则称a 与b 是互素的（也称互质）．定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）．其余大于1的正整数称为合数；数1既不是素数也不是合数．定理1 若,a b 是两个整数，0b >，则存在两个实数,q r ，使()0a qb r r b =+≤<，并且,q r 是唯一性． 证明1 先证存在性．作序列则a 必在上述序列的某两项之间，从而存在一个整数q ，使()1qb a q b ≤<+， 即 0a qb b ≤-<， 取 r a qb =-， 0r b ≤<， 得 a qb r =+，即存在两个实数,q r ，使()0a qb r r b =+≤<． 再证唯一性．假设不唯一，则同时存在11,q r 与12,q r ，使 ()1110a q b r r b =+≤<， ()2220a q b r r b =+≤<， 相减 ()1221q q b r r -=-， 1221q q b r r b -=-<， 1201q q ≤-<，但12q q -为整数，故120q q -=，得12q q =，从而12r r =．注：如果取消0r b ≤<，当0r <或r b >，不保证唯一．经典方法：紧扣定义，构造法证存在性，反证法证唯一性． 证明2 只证存在性，用高斯记号，由 01a a b b ⎡⎤≤-<⎢⎥⎣⎦， 有 0a a b b b⎡⎤≤-<⎢⎥⎣⎦，记a r a b b ⎡⎤=-⎢⎥⎣⎦，故存在,,0a a q r a b r b b b⎡⎤⎡⎤==-≤<⎢⎥⎢⎥⎣⎦⎣⎦使()0a qb r r b =+≤<．证明3 只证存在性，作集合这是一个有下界的非空整数集，其中必有最小的，设x q =时，有最小值r ()0r ≥ a qb r =+．再证r b <，若不然，r b ≥，记1r b r =+，有 即M 有1r 比r 更小，这与r 为最小值矛盾． 故存在两个实数,q r ，使()0a qb r r b =+≤<．定理2 设,,a b c 是三个不全为0的整数，满足a qb c =+，其中q 也为整数，则()(),,a b b c =． 证明 设A =｛,a b 的公约数｝， B =｛,b c 的公约数｝．任取||||d a d c a bq d A d B A B d b d b =-⎧⎧∈⇒⇒⇒∈⇒⊆⎨⎨⎩⎩，任取||||d b d bd B d A B A d c d a bq c⎧⎧∈⇒⇒⇒∈⇒⊆⎨⎨=+⎩⎩， 得 A B =．有A 中元素的最大值B =中元素的最大值，即()(),,a b b c =．注：这是辗转相除法求最大公约数的理论基础．经典方法：要证明A B =，只需证A B ⊆且B A ⊆． 定理3 对任意的正整数,a b ，有 ()[],,a b a b ab ⋅=．证明 因为ab 是,a b 的公倍数，所以,a b 的最小公倍数也是ab 的约数，存在q 使 [],ab q a b =，有 [],a b a qb=且[],a b b为整数，故q 是a 的约数．同理q 是b 的约数，即q 是,a b 的公约数．下面证明，q 是,a b 的最大公约数．若不然，(),q a b <．有[]()[],,,ab q a b a b a b =<． ①设()(),,ab b k a a b a b ==，可见k 是a 的倍数，同样()(),,ab ak b a b a b ==，k 是b 的倍数，即k 是,a b 的公倍数，则存在正整数m 使[],k ma b =，有()[][],,,abm a b a b a b =≥， 得 []()[],,,ab q a b a b a b =≥与①矛盾，所以，(),q a b =，得证()[],,a b a b ab ⋅=．注 也可以由[]()(),1,,aba b kq m ab a b a b q≤===，得(),q a b ≥，与(),q a b <矛盾．两步[](),,,ab q a b ab a b k ==可以交换吗？定理4 ,a b 是两个不同时为0的整数，若00ax by +是形如ax by +（,x y 是任意整数）的数中的最小正数，则（1）00ax by +|ax by +； （2）00ax by +(),a b =． 证明 （1）由带余除法有()00ax by ax by q r +=++，000r ax by ≤<+， 得 ()()0000r a x qx x b y qy ax by =-+-<+，知r 也是形如ax by +的非负数，但00ax by +是形如ax by +的数中的最小正数，故0r =，即00ax by +|ax by +．（2）由（1）有00ax by +|10a b a +=， 00ax by +|01a b b +=，得00ax by +是,a b 的公约数．另一方面，,a b 的每一个公约数都可以整除00ax by +，所以00ax by +是,a b 的最大公约数，00ax by +(),a b =．推论 若(),1a b =，则存在整数,s t ，使1as bt +=．（很有用） 定理5 互素的简单性质： （1）()1,1a =． （2）(),11n n +=． （3）()21,211n n -+=．（4）若p 是一个素数，a 是任意一个整数，且a 不能被p 整除，则(),1a p =．证明 因为(),|a p p ，所以，素数p 的约数只有两种可能：()(),1,,a p a p p ==．但a 不能被p 整除，(),a p p ≠，得(),1a p =．推论 若p 是一个素数，a 是任意一个整数，则(),1a p =或(),a p p =． （5）若(),1a b =，则存在整数,s t ，使1as bt +=．（定理4推论） （6）若()(),1,,1a b a c ==，则(),1a bc =． 证明 由(),1a b =知存在整数,s t ，使1as bt +=． 有 ()a cs bct c +=， 得 ()(),,1a bc a c ==．（7）若(),1a b =，则(),1a b a ±=，(),1a b b ±=， (),1a b ab ±=． 证明 ()()(),,,1a b a b a b a ±=±==， ()(),,1a b b a b ±==， 由（6）(),1a b ab ±=．（8）若(),1a b =，则(),1m n a b =，其中,m n 为正整数． 证明 据（6），由(),1a b =可得(),1m a b =． 同样，由(),1m a b =可得(),1m n a b =．定理6 设a 是大于1的整数，则a 的除1之外的最小的正约数q 必是素数，且当a 是合数时，q ≤证明 用反证法，假设q 不是素数，则存在正整数数1q ，11q q <<，使1|q q ，但|q a ，故有1|q a ，这与q 是a 的除1之外的最小正约数矛盾，故q 是素数．当a 是合数时，设1a a q =，则1a 也是a 的一个正约数，由q 的最小性得1q a ≤，从而21q a q a ≤=，开方得q ≤定理7 素数有无穷多个，2是唯一的偶素数． 证明 假设素数只有有限多个，记为12,,,n p p p ，作一个新数1211n p p p p =+>．若p 为素数，则与素数只有 n 个12,,,n p p p 矛盾．若p 为合数，则必有{}12,,,i n p p p p ∈，使|i p p ，从而|1i p ，又与1i p >矛盾．综上所述，素数不能只有有限多个，所以素数有无穷多个． 2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．注：这个证明中，包含着数学归纳法的早期因素：若假设有n 个素数，便有1n +个素数．（构造法、反证法）秒定理8（整除的性质）整数,,a b c 通常指非零整数 （1）1a ，1|a -；当0a ≠时，|a a ，|0a ．（2）若b a ，0a ≠，则b a ≤;若b a ，b a >，则0a =;若0ab >，且,b a a b ，则a b =．证明 由b a ，0a ≠，有a bq =，得a b q b =≥． 逆反命题成立“若b a ，b a >，则0a =”; 由b a ≤且b a ≥得a b =，又0ab >，得a b =． （3）若a b c d +=+，且|,|,|e a e b e c ，则|e d ． （4）若c b ，b a ，则c a ． 证明 （定义法）由c b ，b a ，有 12,b q c a q b ==， 得 ()12a q q c =， 即 c a ．（5）若c a ，则bc ab ．（6）若c a ，c b ，则对任意整数,m n ，有c ma nb +． 证明 （定义法）由c a ，c b ，有 12,a q c b q c ==， 得 ()12ma nb mq nq c +=+， 即 c ma nb +．（7）若(),1a b =，且a bc ，则a c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有()()a cs bc t c +=，因为a a ，a bc ，所以a 整除等式的左边，进而整除等式的右边，即a c ．注意 不能由a bc 且|a b /得出a c ．如649⨯，但6|4/且6|9/． （8）若(),1a b =，且,a c b c ，则ab c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有acs bct c +=，又由,a c b c 有12,c aq c bq ==代入得()()21ab q s ab q t c +=，所以ab c ．注意 不能由a c 且b c 得出ab c ．如不能由630且10|30得出60|30． （9）若a 为素数，且a bc ，则a b 或a c ．证明 若不然，则|a b /且|a c /，由a 为素数得()(),1,,1a b a c ==，由互素的性质（6）得(),1a bc =，再由a 为素数得|a bc /，与a bc 矛盾．注意 没有a 为素数，不能由a bc 推出a b 或a c ．如649⨯，但6|4/且6|9/．定义6 对于整数,,a b c ，且0c ≠，若()c a b -，则称,a b 关于模c 同余，记作(mod )a b c ≡；若()|c a b -/，则称,a b 关于模c 不同余，记作a(mod )b c ．定理9（同余的性质）设,,,,a b c d m 为整数，0,m > （1）若(mod )a b m ≡且(mod )b c m ≡，则(mod )a c m ≡； 证明 由(mod )a b m ≡且(mod )b c m ≡，有 12,a b mq b c mq -=-=，()12a c m q q -=+，得(mod )a c m ≡．（2）若(mod )a b m ≡且(mod )c d m ≡，则(mod )a c b d m +≡+且(mod )ac bd m ≡． 证明 由(mod )a b m ≡且(mod )c d m ≡，有12,a b mq c d mq -=-=， ① 对①直接相加 ，有()()()12a c b d m q q +-+=+，得 (mod )a c b d m +≡+.对①分别乘以,c b 后相加，有()()()12ac bd ac bc bc bd m cq bq -=---=+，得 (mod )ac bd m ≡．（3）若(mod )a b m ≡，则对任意的正整数n 有(mod )nna b m =且(mod )an bn mn ≡. （4）若(mod )a b m ≡，且对非零整数k 有(,,)k a b m ，则mod a b m k k k ⎛⎫= ⎪⎝⎭． 证明 由(mod )a b m ≡、，有 a b mq =+， 又(,,)k a b m ，有,,a b mk k k 均为整数，且 a b mq k k k=+， 得mod a b m k k k ⎛⎫≡ ⎪⎝⎭． 定理10 设,a b 为整数，n 为正整数， （1）若a b ≠，则()()nna b a b--．()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++．（2）若a b ≠-，则()()2121n n a b ab --++．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+．（3）若a b ≠-，则()()22nn a b ab +-．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+-．定义7 设n 为正整数，k 为大于2的正整数, 12,,,m a a a 是小于k 的非负整数，且10a >．若12121m m m m n a k a k a k a ---=++++，则称数12m a a a 为n 的k 进制表示．定理11 给定整数2k ≥，对任意的正整数n ，都有唯一的k 进制表示．如12121101010m m m m n a a a a ---=++++，109,0i a a ≤≤>（10进制） 12121222m m m m n a a a a ---=++++．101,0i a a ≤≤>（２进制）定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的1212k k n p p p ααα=，其中12k p p p <<<为素数，12,,,k ααα为正整数． （分解唯一性）证明1 先证明，正整数n 可分解为素数的乘积12m n p p p =． ①如果大于1的正整数n 为素数，命题已成立．当正整数n 为合数时，n 的正约数中必有一个最小的，记为1p ，则1p 为素数，有11n p a =，11a n <<．如果1a 为素数，命题已成立．当1a 为合数时，1a 的最小正约数2p 为必为素数，有11122n p a p p a ==，211a a n <<<．这个过程继续进行下去，由于n 为有限数，而每进行一步i a 就要变小一次，于是，经过有限次后，比如m 次，n 就变为素数的乘积12m n p p p =．下面证明分解式是唯一的．假设n 还有另一个分解式 12t n q q q =， ② 则有 1212m t p p p q q q =． ③因为等式的右边能被1q 整除，所以左边也能被1q 整除，于是1q 整除12,,,m p p p 中的某一个i p ，但i p 为素数，所以i p 与1q 相等，不妨设i p 为1p ，有11p q =．把等式③两边约去11p q =，得 2323m t p p p q q q =．再重复上述步骤，又可得22p q =，33p q =，…，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m t <），则有121m m t q q q ++=． ④但12,,,m m t q q q ++均为素数，素数都大于1，有121m m t q q q ++>，这表明等式④不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的．将分解式按i p 的递增排列，并将相同的i p 合并成指数形式，即得1212k k n p p p ααα=．其中12k p p p <<<为素数，12,,,k ααα为正整数．证明2 用第二数学归纳法证明12m n p p p =，12m p p p ≤≤≤．（1）当2n =，因为2为素数，命题成立．（2）假设命题对一切大于1而小于n 的正整数已成立． 这时，若n 为素数，命题成立；若n 不为素数，必存在,a b ，使 n ab =，1,1a n b n <<<<， 由归纳假设，小于n 的,a b 可分解为素数的乘积得 //////1212s s s t n p p p q q q ++=，适当调整/i p 的顺序，可得命题对于正整数n 成立．由数学归纳法，命题对一切大于1的正整数n 成立．下面证明分解式是唯一的．假设n 的分解式不唯一，则至少有两个分解式12m n p p p =，12m p p p ≤≤≤， 12t n q q q =，12t q q q ≤≤≤，得 1212m t p p p q q q =．有 112|t p q q q 且112|m q p p p ，这就存在,i j q p ，使1|i p q 且1|j q p ，但11,,,i j p q q p 均为为素数，所以11,i j p q q p ==，又 111i j p q q p p =≥=≥， 所以 11p q =．把等式两边约去11p q =，得2323m t p p p q q q =．再重复上述步骤，又可得22p q =，33p q =，…，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m t <），则有121m m t q q q ++=．但12,,,m m t q q q ++均为素数，素数都大于1，有121m m t q q q ++>，这表明上述等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的．将分解式按i p 的递增排列，并将相同的i p 合并成指数形式，即得1212k k n p p p ααα=．其中12k p p p <<<为素数，12,,,k ααα为正整数．定理13 若正整数n 的素数分解式为 1212k k n p p p ααα=则n 的正约数的个数为()()()()12111k d n a a a =+++，n 的一切正约数之和为()121111212111111k k k p p p S n p p p ααα+++---=⋅⋅⋅---． 证明 对于正整数1212k k n p p p ααα=，它的任意一个正约数可以表示为1212k k m p p p βββ=，0i i βα≤≤ ， ①由于i β有0,1,2,,i α共1i α+种取值，据乘法原理得n 的约数的个数为()()()()12111k d n a a a =+++．考虑乘积 ()()()12010101111222k kk k p p p p p p pp p ααα+++++++++，展开式的每一项都是n 的某一个约数（参见①），反之，n 的每一个约数都是展开式的某一项，于是，n 的一切约数之和为121111212111111k k k p p p p p p ααα+++---=⋅⋅⋅---． 注 构造法．定义8 （高斯函数）对任意实数x ，[]x 是不超过x 的最大整数．亦称[]x 为x 的整数部分，[][]1x x x ≤<+． 定理14 在正整数!n 的素因子分解式中，素数p 作为因子出现的次数是23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦．证明 由于p 为素数，故在!n 中p 的次方数是1,2,,n 各数中p 的次方数的总和（注意，若p 不为素数，这句话不成立）．在1,2,,n 中，有n p ⎡⎤⎢⎥⎣⎦个p 的倍数；在n p ⎡⎤⎢⎥⎣⎦个p 的倍数的因式中，有2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数；在2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数的因式中，有3n p ⎡⎤⎢⎥⎣⎦个3p 的倍数；…，如此下去，在正整数!n 的素因子分解式中，素数p 作为因子出现的次数就为23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦．注 省略号其实是有限项之和．画线示意50!中2的指数．定理15 （费玛小定理）如果素数p 不能整除整数a ，则()11p p a --．证明1 考察下面的1p -个等式： 11a pq r =+，10r p ≤<，222a pq r =+，20r p ≤<……()111p p p a pq r ---=+，10p r p -≤<由于素数p 不能整除整数a ，所以，p 不能整除每个等式的左边，得121,,,p r r r -均不为0，只能取1,2,,1p -．下面证明121,,,p r r r -各不相等．若不然，存在,,11t s t s p ≤<≤-，使 相减 ()()s t s t a p q q -=-．应有素数p 整除()s t a -，但素数p 不能整除a ，所以素数p 整除()s t -，然而由11t s p ≤<≤-可得 02s t p p <-≤-<， 要素数p 整除()s t -是不可能的，得121,,,p r r r -各不相等．有()()1211211!p rr r p p -=-=-．再把上述1p -个等式相乘，有 ()11211!p p p aMp rr r ---=+，即 ()()11!1!p p aMp p --=+-，其中M 是一个整数．亦即 ()()11!1p p a Mp ---=．由于p 是素数，不能整除()1!p -，所以素数p 整除11p a--，得证证明2 改证等价命题：如果素数p 不能整除整数a ，则()mod p a a p ≡． 只需对1,2,,1a p =-证明成立，用数学归纳法．（1）1a =，命题显然成立．（2）假设命题对()11a k k p =≤<-成立，则当1a k =+时，由于()|1,2,,1i p p C i p =-，故有()11mod p k k p ≡+≡+．（用了归纳假设） 这表明，命题对1a k =+是成立． 由数学归纳法得()mod p a a p ≡．又素数p 不能整除整数a ，有(),1a p =，得()11p p a--．定义9 （欧拉函数）用()n ϕ表示不大于n 且与n 互素的正整数个数． 定理16 设正整数1212k k n p p p ααα=，则()12111111k n n p p p ϕ⎛⎫⎛⎫⎛⎫=--- ⎪ ⎪⎪⎝⎭⎝⎭⎝⎭．证明 用容斥原理．设{}1,2,,S n =，记i A 为S 中能被i p 整除的数所组成的集合（1,2,i k =），用iA 表示i A 中元素的个数，有i inA p =，1212,,i j k i jkn n A A A A A p p p p p ==．易知，{}1,2,,S n =中与n 互素的正整数个数为12k A A A ，由容斥原理得注 示意3n =的容斥原理． 推论 对素数p 有()()11,p p ppp αααϕϕ-=-=-．定理17 整系数不定方程ax by c +=（0ab ≠）存在整数解的充分必要条件是(),a b c ． 证明 记(),d a b =．（1）必要性（方程有解必须满足的条件）．若方程存在整数解，记为00,,x x y y =⎧⎨=⎩，则00ax by c +=，由|,|d a d b ， 有00|d ax by +，得证(),|a b c ．（2）充分性（条件能使方程有解）．若|d c ，可设c de =由于形如ax by +的数中有最小正数00ax by +满足00ax by +(),a b =．两边乘以e ，得这表明方程有解00,.x ex y ey =⎧⎨=⎩定理18 若0ab ≠,(),1a b =，且00,,x x y y =⎧⎨=⎩是整系数不定方程ax by c +=的一个整数解，则方程的一切整数解可以表示为00,,x x bt y y at =-⎧⎨=+⎩()t Z ∈． ①证明 直接代入知①是方程的整数解，下面证明任意一个整数解都有①的形式. 由()00,x y 是方程的一个解，有00ax by c +=，又方程的任意一个解(),x y 满足ax by c +=， ② 相减 ()()000a x x b y y -+-=． ③ 但(),1a b =，故有 ()0|a y y -， 有00,x x y y t t Z b a--==∈- 得方程的任意一个整数解可以表示为00,,x x bt y y at =-⎧⎨=+⎩()t Z ∈．定义10 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）．类似地可以定义空间整点．第二讲 数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等．重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容．一、奇数与偶数整数按照能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数．偶数可以表示为2n ，奇数可以表示为21n -或21n +．一般地，整数被正整数m 去除，按照余数可以分为m 类，称为模m 的剩余类(){}mod i C x x i m =≡，从每类中各取出一个元素i i a C ∈，可得模m 的完全剩余系（剩余类派出的一个代表团），0,1,2,,1m -称为模m 的非负最小完全剩余系.通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用．关于奇数和偶数，有下面的简单性质：（1）奇数≠偶数．（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9． （3）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；．（4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数．（5）除2外所有的正偶数均为合数；（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半． （7）偶数乘以任何整数的积为偶数．（8）两数和与两数差有相同的奇偶性，()mod 2a b a b +≡-． （9）乘积为奇数的充分必要条件是各个因数为奇数． （10）n 个偶数的积是2n 的倍数．（11）()11k -=的充分必要条件是k 为偶数，()11k-=-的充分必要条件是k 为奇数． （12）()()()()()()22220mod 4,211mod 4,211mod8n n n ≡-≡-≡． （13）任何整数都可以表示为()221mn k =-．……例1 （1906，匈牙利）假设12,,,n a a a 是1,2,,n 的某种排列，证明：如果n 是奇数，则乘积是偶数．解法1 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，奇数个奇数的和还是奇数奇数=()()()1212n a a a n -+-++-()()12120n a a a n =+++-+++=，这与“奇数≠偶数”矛盾． 所以()()()1212n a a a n ---是偶数．评析 这个解法说明()()()1212n a a a n ---不为偶数是不行的，但没有指出为偶数的真正原因．体现了整体处理的优点，但掩盖了“乘积”为偶数的实质．解法 2 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，i a 与i 的奇偶性相反，{}1,2,,n 中奇数与偶数一样多，n 为偶数．但已知条件n 为奇数，矛盾． 所以()()()1212n a a a n ---是偶数．评析 这个解法揭示了()()()1212n a a a n ---为偶数的原因是“n 为奇数”．那么为什么“n 为奇数”时“乘积”就为偶数呢？解法3 121,2,,,,,,n n a a a 中有1n +个奇数，放到n 个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得()()()1212n a a a n ---为偶数．评析 这个解法揭示了()()()1212n a a a n ---为偶数的原因是“当n 为奇数时，1,2,,n 中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”．类似题：例1-1（1986，英国）设127,,,a a a 是整数，127,,,b b b 是它们的一个排列，证明()()()112277a b a b a b ---是偶数．（127,,,a a a 中奇数与偶数个数不等）例1-2 π的前24位数字为 3.14159265358979323846264π=，记1224,,,a a a 为该24个数字的任一排列，求证()()()12342324a a a a a a ---必为偶数．（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等） 例2 能否从1,2,,15中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为1,2,,14？解 考虑14个差的和S ，一方面1214105S =+++=为奇数．另一方面，每两个数,a b 的差与其和有相同的奇偶性 (mod2)a b a b -≡+，因此，14个差的和S 的奇偶性与14个相应数之和的和/S 的奇偶性相同，由于图中的每一个数a 与2个或4个圈中的数相加，对/S 的贡献为2a 或4a ，从而/S 为偶数，这与S 为奇数矛盾，所以不能按要求给图中的圆圈填数．评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在反证法中，计算两次又可用来构成矛盾．例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？解 （1）4堆是不能保证的．如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）．（2）5堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数．例4 有n 个数121,,,,n n x x x x -，它们中的每一个要么是1，要么是1-．若1223110n n n x x x x x x x x -+++++=，求证4|n ．证明 由{}1,1i x ∈-，有{}11,1i i x x +∈-，再由1223110n n n x x x x x x x x -+++++=，知n 个1i i x x +中有一半是1，有一半是1-，n 必为偶数，设2n k =．现把n 个1i i x x +相乘，有2222122311121(1)(1)1k kn n n n n x x x x x x x x x x x x ---+===，可见，k 为偶数，设2k m =，有4n m =，得证4|n ．例5 n 个整数121,,,,n n a a a a -，其积为n ，其和为0，试证4|n ．证明 先证n 为偶数，若不然，由121n n a a a a n -=知，121,,,,n n a a a a -全为奇数，其和必为奇数，与其和为0（偶数），故n 必为偶数．（121,,,,n n a a a a -中至少有1个偶数）再证n 为4的倍数，若不然，由n 为偶数知，121,,,,n n a a a a -恰有一个为偶数，其余1n -个数全为奇数，奇数个奇数之和必为奇数，加上一个偶数，总和为奇数，与121,,,,n n a a a a -之和为0矛盾，所以，n 为4的倍数，4|n ．（121,,,,n n a a a a -中至少有2个偶数）评析 要证4|n ，只须证121,,,,n n a a a a -中至少有2个偶数，分两步，第一步证至少有1个偶数，第二步证至少有2个偶数．例6 在数轴上给定两点1，在区间内任取n 个点，在此2n +个点中，每相邻两点连一线段，可得1n +条互不重叠的线段，证明在此1n +条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．证明 将2n +个点按从小到大的顺序记为122,,,n A A A +…，并在每一点赋予数值i a ，使 与此同时，每条线段1i i A A +也可数字化为1i i a a +（乘法） 记11i i a a +=-的线段有k 条，一方面 另一方面 12233412()()()()n n a a a a a a a a ++…21231212()1n n n a a a a a a a -++===-…，得()11k-=-，故k 为奇数． 评析 用了数字化、奇偶分析的技巧． 二、约数与倍数最大公约数与最小公倍数的求法． （1）短除法．（2）分解质因数法．设1212,0,1,2,,k k i a p p p i k αααα=≥=， 1212,0,1,2,,k k i b p p p i k ββββ=≥=．记 {}{}min ,,max ,i i i i i i γαβδαβ==， 则 ()1212,k k a b p p p γγγ=， []1212,k k a b p p p δδδ=．（3）辗转相除法()()()()()121,,,,,0n n n n a b b r r r r r r r -======．例7 （1）求()8381,1015，[]8381,1015； （2）()144,180,108，[]144,180,108． 解（1）方法1 分解质因数法．由 得 ()8381,101529=，[]28381,1015571729293335=⨯⨯⨯=．方法2 辗转相除法．或23214221313823226110158381232232783812029232261q q q q r r r r ========或 ()()()()()8381,1015261,1015261,23229,23229,029=====． []()83811015838110158381,10158381352933358381,101529⨯⨯===⨯=．（2）方法1 短除法．由得 ()22144,180,1082336=⨯=，[]43144,180,1082352160=⨯⨯=．方法2 分解质因数法．由42222314423,180235,10823,=⨯=⨯⨯=⨯，得 ()22144,180,1082336=⨯=，[]43144,180,1082352160=⨯⨯=．例8 正整数n 分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n 的最小值为 ． 解 依题意，对最小的n ，则1n +是2,3,4,5,6,7,8,9,10的公倍数3212357n +=⨯⨯⨯，得2519n =．例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？解 相当于求不定方程15276x y +=的整数解． 由()15,273=知，存在整数,u v ，使15273u v +=，可得一个解2,1u v ==-，从而方程 ()1542726⨯+⨯-=．即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升．例10 对每一个2n ≥，求证存在n 个互不相同的正整数12,,,n a a a ，使i j i j a a a a -+，对任意的{},1,2,,,i j n i j ∈≠成立．证明 用数学归纳法．当2n =时，取121,2a a ==，命题显然成立． 假设n k =时，命题成立，即存在12,,,k a a a ，使 i j i j a a a a -+，对任意的{},1,2,,,i j k i j ∈≠成立．现取b 为12,,,k a a a 及它们每两个数之差的最小公倍数，则1k +个数满足 ()()()()()(),,t t ij i j a b b a b b a b a b a b a b ⎧+-++⎪⎨+-++++⎪⎩即命题对1n k =+时成立．由数学归纳法知命题对2n ≥成立．例11 ()111959,IMO -证明对任意正整数n ，分数214143n n ++不可约．证明1 （反证法）假若214143n n ++可约，则存在1d >， ①使 ()214,143n n d ++=， 从而存在(),,,1p q p q =，使 消去n ，()()3322⨯-⨯，得()132d q p =-， ④ 的 1d =． ⑤由（1）、（5）矛盾，得1d =． 解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法．（2）式④是实质性的进展，表明 ()()131432214n n =+-+， 可见 ()214,1431n n ++=． 由此获得2个解法．证明2 设()214,143n n d ++=．存在(),,,1p q p q =，使 消去n ，②×3-①×2，得()132d q p =- ③ 得 1d =．证明3 由()()131432214n n =+-+ 得 ()214,1431n n ++=．证明4 ()214,143n n ++ ()71,143n n =++ ④ ()71,1n =+ ⑤1=．解题分析：第④ 相当于 ①-②；第⑤ 相当于②-2（①-②）=②×3-①×2；所以③式与⑤式的效果是一样的．例12 不存在这样的多项式()1110mm m m f n a n a na n a --=++++，使得对任意的正整数n ，()f n 都是素数．证明 假设存在这样的多项式,对任意的正整数n ，()f n 都是素数，则取正整数n b =，有素数p 使 ()1110mm m m f b a b a ba b a p --=++++=，进而对任意的整数,k 有()1110m m m m a b a b a b a Mp --=+++++（二项式定理展开）()1P M =+，其中M 为整数，这表明()f b kp +为合数．这一矛盾说明，不存在这样的多项式,对任意的正整数n ，()f n 都是素数． 三、平方数若a 是整数，则2a 就叫做a 的完全平方数，简称平方数． 1．平方数的简单性质（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．（3）()()()()2220mod 4,211mod 4n n ≡-≡． （４）()()2211mod 8n -≡．（6）凡是不能被3整除的数，平方后被3除余1．（7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个．（9）直角三角形的三边均为整数时，我们把满足222a b c +=的整数(),,a b c 叫做勾股数．勾股数的公式为其中,m n 为正整数，(),1m n =且,m n 一奇一偶．这个公式可给出全部素勾股数．2．平方数的证明方法 （1）反证法． （2）恒等变形法．（3）分解法．设a 为平方数，且a bc =，(),1b c =，则,b c 均为平方数． （4）约数法．证明该数有奇数个约数． 3．非平方数的判别方法（1）若()221n x n <<+，则x 不是平方数．（2）约数有偶数个的数不是平方数．（3）个位数为2，3，7，8的数不是平方数． （4）同余法：满足下式的数n 都不是平方数．()2mod3n ≡， ()23mod4n ≡或， ()23mod5n ≡或，()23567mod8n ≡或或或或， ()2378mod10n ≡或或或．（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整除的电灯的。

数学竞赛中的数论知识点总结数学竞赛中，数论是竞赛题目中经常出现的一个重要知识点。

在数论中，各种定理和技巧层出不穷，很多时候需要针对特殊类型的问题有针对性地进行研究。

本文将对数论中的一些基本知识点进行总结，以便竞赛选手更好地备战数学竞赛。

一、同余同余是数论中常见的一个概念。

a与b模n同余，当且仅当它们的差能被n整除，即a-b是n的倍数。

可以表示为$a \equiv b\pmod{n}$。

同时，同余关系具有传递性、反身性和对称性。

同余关系在数论中有很多应用，特别是在求证和构造问题中。

二、模反元素求模反元素是数论中的一个重要技巧。

在模n的情况下，如果a乘以x再模n可以得到1，那么x就是a模n的反元素（或倒数）。

求模反元素的一般方法是通过使用扩展欧几里得算法，在求最大公约数的同时求出x和y的值，其中x就是a模n的反元素。

三、欧拉函数欧拉函数是数论中一个重要的概念，通常记为$\varphi (n)$。

欧拉函数的意义是小于n的正整数中，与n互质的数的个数。

求欧拉函数的方法有很多种，其中比较常用的有：将n分解为质因数的积，然后根据欧拉函数的性质，对于每个不同的质因数，将它的欧拉函数值相乘即可。

四、费马小定理费马小定理是数论中常用的一个定理，它表明如果p是一个质数，那么对于任意正整数a，$a^{p-1} \equiv 1 \pmod{p}$。

这个定理在构造和求证问题中有很多应用，特别是在判定质数的问题中。

五、中国剩余定理中国剩余定理是一种将模数分解成相对质数乘积的方法。

可以表示为：$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2\pmod{n_2} \end{cases}$ 其中，$n_1$和$n_2$是两个互质的正整数，a1和a2是任意整数。

该定理的思路是先根据n1和n2分别求出它们的模反元素，然后利用同余方程组的解法，得出一个通解，最后在将通解化简成最小正整数解即可。

高一年级竞赛数学数论专题讲义：1整除高一竞赛数论专题1.整除设,,0.a b Z a ∈≠如果存在,q Z ∈使得,b aq =那么就说b 可被a 整除(或a 整除b ),记做|.a b 且称b 是a 的倍数,a 是b 的约数(也可称为除数、因数).b 不能被a 整除就记做a b ?. 整除关系的基本性质(1)|,||.a b b c a c ?(2)|,|a b a c ?对任意的,,x y Z ∈有|.a bx cy +设12,a a 是两个不全为零的整数,如果1|d a 且2|,d a 那么d 就称为1a 和2a 的公约数,我们把1a 和2a 的公约数中的最大的称为1a 和2a 的最大公约数,记做12(,).a a 若12(,)1,a a =则称1a 和2a 是既约的,或是互素的.设12,a a 是两个均不为零的整数,如果1|,a l 且2|,a l 那么l 就称为1a 和2a 的公倍数,我们把1a 和2a 的公倍数中的最小的称为1a 和2a 的最小公倍数,记做12[,].a a1.设12,a a 是两个不全为零的整数,证明对任意整数q ,都有12121(,)(,).a a a a qa =+2.设(,)1,a b =证明(1)若|,|a c b c 则|.ab c(2)若|a bc 则|.a c3.(Bezout 定理)设,a b 是不全为零的整数,证明(,)1a b =的充要条件是存在整数,x y 使得 1.ax by +=4.证明对任意整数n ,65222n n n n +--能被120整除.5.设m 是一个大于2正整数,若存在正整数n 使得21|21m n -+.求m 的所有可能取值.6.证明：正整数M 是完全平方数的充要条件是对于任意正整数n ,22(1),(2),,M M M M +-+-2()M n M +-中至少有一项可以被n 整除.7.已知整数,x y 满足1,1,x y ≠-≠-且使得441111x y y x --+++是整数,求证4441x y -能被1x +整除.8.证明：对于任何自然数n 和k ,数3(,)2410k k f n k n n =++都不能分解成若干个连续的自然数之积.9.对于所有素数p 和所有正整数()n n p ≥,证明：p n n C p ??-能被p 整除.10.(1)求所有的素数数列12n p p p <<<,使得11(1)n k kp =+∏是一个整数. (2)是否存在n 个大于1的不同正整数*12,,,,,n a a a n N ∈使得211(1)n k ka =+∏为整数?.11.设,m n 是正整数, 证明(,)(21,21)21.m n m n --=-12.任给2n ≥,证明：存在n 个互不相同的正整数,其中任意两个的和整除这n 个数的积.高一竞赛数论专题1.整除解答设,,0.a b Z a ∈≠如果存在,q Z ∈使得,b aq =那么就说b 可被a 整除(或a 整除b ),记做|.a b 且称b 是a 的倍数,a 是b 的约数(也可称为除数、因数).b 不能被a 整除就记做a b ?. 整除关系的基本性质(1)|,||.a b b c a c ?(2)|,|a b a c ?对任意的,,x y Z ∈有|.a bx cy +设12,a a 是两个不全为零的整数,如果1|d a 且2|,d a 那么d 就称为1a 和2a 的公约数,我们把1a 和2a 的公约数中的最大的称为1a 和2a 的最大公约数,记做12(,).a a 若12(,)1,a a =则称1a 和2a 是既约的,或是互素的.设12,a a 是两个均不为零的整数,如果1|,a l 且2|,a l 那么l 就称为1a 和2a 的公倍数,我们把1a 和2a 的公倍数中的最小的称为1a 和2a 的最小公倍数,记做12[,].a a。