有关数论函数的一些问题

七大数学难题题目七大数学难题是21世纪数学界的重要挑战，由美国克雷数学研究所（Clay Mathematics Institute）于2000年提出。

一、这七个难题分别是：1. P vs NP问题2. 霍奇猜想（Hodge conjecture）3. 庞加莱猜想（Poincaré conjecture）4. 黎曼猜想（Riemann hypothesis）5. 杨-米尔斯存在性和质量间隙6. 纳维尔-斯托克斯方程的存在性和光滑性7. BSD猜想（Birch and Swinnerton-Dyer conjecture）二、下面将详细介绍这七大数学难题的题目和背景。

1. P vs NP问题P vs NP问题是计算机科学和数学中最著名的问题之一，由计算机科学家Stephen Cook在1971年提出。

P类问题是指那些可以用多项式时间算法解决的问题，而NP类问题是指那些可以在多项式时间内验证一个解的问题。

目前已知P类问题包含在NP类问题中，但尚不清楚NP类问题是否可以完全包含在P类问题中。

如果能够证明P=NP，那么将意味着所有NP类问题都可以通过某种多项式时间算法解决，这将对计算机科学和数学产生深远的影响。

2. 霍奇猜想霍奇猜想是代数几何中的一个基本问题，由英国数学家WilliamHodge在1940年提出。

该猜想认为，对于任何光滑的复代数簇，其Hodge-Deligne组中的某些元素可以通过有限次的迭代消除。

这个问题与拓扑学、代数几何和数论等多个数学分支有关，解决它将对这些领域产生重要影响。

3. 庞加莱猜想庞加莱猜想是拓扑学中的一个基本问题，由法国数学家Henri Poincaré在1904年提出。

该猜想认为，任何三维流形都可以通过连续变换分解为一些简单的部分，如二维球面和三维球面。

这个问题涉及到流形的结构和拓扑性质，解决它将对拓扑学的发展产生重要影响。

4. 黎曼猜想黎曼猜想是数论中的一个基本问题，由德国数学家Gustav Riemann在1859年提出。

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

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题，占10.8% 。

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

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

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

在USACO比赛中，数论相关题目一直是考察的热点之一。

数论作为数学的一个重要分支，涉及整数的性质和关系，常常能够运用到算法设计和问题求解中。

本文将从简单到复杂，由浅入深地探讨USACO比赛中的数论相关题目，帮助你更深入地理解这一主题。

1. 简单级别：在USACO比赛的入门级题目中，通常会涉及一些基本的数论知识，比如素数、最大公约数、最小公倍数等。

给定两个整数，要求求它们的最大公约数或最小公倍数；或者判断一个数是否为素数等。

这些题目往往需要运用到基本的数论算法，比如欧几里得算法求最大公约数、筛法求素数等。

2. 中等级别：在中等级别的USACO比赛题目中，数论相关的内容会更加复杂和深刻。

可能涉及到模运算、同余方程、欧拉函数、费马小定理等知识点。

题目可能会要求实现一些高级的数论算法，比如快速幂算法、扩展欧几里得算法等。

这些题目往往需要更深入的数论知识和算法功底，能够更好地理解和运用复杂的数论知识。

3. 高级级别：在USACO比赛的高级题目中，数论相关的内容往往会与其他算法知识结合，考察的角度也更加灵活多样。

题目可能会涉及到数论与图论、动态规划、贪心算法等内容的结合，难度较大。

此时，除了对数论知识的深刻理解外，还需要具备较强的问题建模能力和算法设计能力。

总结回顾：通过以上的分析，我们可以看到，USACO比赛中的数论相关题目，涵盖了不同难度级别的内容，从简单的基本算法到复杂的高级问题解决方案，都需要对数论知识有较为全面、深刻的理解。

在备战USACO比赛时，我们要加强对数论知识的学习和掌握，尤其要注重基础知识的打牢和算法能力的提升。

个人观点和理解：我个人认为，数论是一门非常有趣和有挑战性的数学分支，在USACO 比赛中能够有机会运用数论知识解决实际问题，对于提高自己的数学建模能力和算法设计能力都是非常有益的。

我会在备战USACO比赛的过程中，加强对数论相关知识的学习和实践，努力提高自己的数论解题能力。

通过以上分析和讨论，我们对USACO比赛中的数论相关题目有了更全面、深刻的理解。

数论基础答案【篇一：现代密码学(谷利泽)课后题答案】>第一章判断题选择题1、1949年，（ a ）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础，从此密码学成了一门科学。

a、shannonb、diffiec、hellmand、shamir2、一个密码系统至少由明文、密文、加密算法、解密算法和密钥5部分组成，而其安全性是由（ d）决定的。

a、加密算法b、解密算法c、加解密算法d、密钥3、计算和估计出破译密码系统的计算量下限，利用已有的最好方法破译它的所需要的代价超出了破译者的破译能力（如时间、空间、资金等资源），那么该密码系统的安全性是（ b ）。

a无条件安全b计算安全c可证明安全d实际安全4、根据密码分析者所掌握的分析资料的不通，密码分析一般可分为4类：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，其中破译难度最大的是（ d ）。

a、唯密文攻击b、已知明文攻击c、选择明文攻击d、选择密文攻击填空题：5、1976年，w.diffie和m.hellman在密码学的新方向一文中提出了公开密钥密码的思想，从而开创了现代密码学的新领域。

6、密码学的发展过程中，两个质的飞跃分别指1949年香农发表的保密系统的通信理论和公钥密码思想。

7、密码学是研究信息寄信息系统安全的科学，密码学又分为密码编码学和密码分析学。

8、一个保密系统一般是明文、密文、密钥、加密算法、解密算法5部分组成的。

9、密码体制是指实现加密和解密功能的密码方案，从使用密钥策略上，可分为对称和非对称。

10、对称密码体制又称为秘密密钥密码体制，它包括分组密码和序列密码。

第二章选择题：1、字母频率分析法对（b ）算法最有效。

a、置换密码b、单表代换密码c、多表代换密码d、序列密码2、（d）算法抵抗频率分析攻击能力最强，而对已知明文攻击最弱。

a仿射密码b维吉利亚密码c轮转密码d希尔密码3、重合指数法对（c）算法的破解最有效。

欧拉定理及其在数论中的应用欧拉定理（Euler's theorem），也称为费马-欧拉定理（Fermat-Euler theorem）是数论中非常重要的定理之一。

该定理描述了整数的幂与模运算之间的关系，具体地说，它说明了如果正整数a与正整数n互质，那么a的欧拉函数值与n的模运算结果余数的幂是相等的。

欧拉函数φ(n)指的是小于或等于n且与n互质的正整数的个数。

欧拉定理的数学表达式如下：如果a与n互质，那么a^φ(n)与1对模n同余。

其中，^表示乘方运算，φ(n)表示欧拉函数的值。

欧拉定理具有广泛的应用，特别在密码学和安全领域中发挥重要作用。

例如，在RSA（一种非对称加密算法）中，欧拉定理用于实现密钥的生成和加密过程。

此外，它还在数学证明和计算机科学中有诸多应用。

让我们进一步深入探讨欧拉定理在数论中的应用。

首先，欧拉定理提供了一种有效的方法来计算整数的模逆元素。

模逆元素是指在模意义下乘法的逆元素。

根据欧拉定理，如果a与n互质，那么a的欧拉函数值与n的模运算结果余数的幂是相等的。

因此，我们可以使用欧拉定理来计算整数a模n的逆元素。

具体地说，如果a与n互质，那么a^φ(n)与1对模n同余；所以, a^(φ(n)-1)与a的乘法逆元素对模n同余。

这种方法在RSA算法以及其他需要计算模逆元素的情况下非常有用。

其次，欧拉定理在素数测试中也有重要的应用。

根据费马定理（Fermat's theorem），如果p是一个素数，那么对于任意整数a，a^(p-1)与1对模p同余。

然而，对于合数n，a^(n-1)与1对模n同余的性质不一定成立。

欧拉定理的推广版本，即欧拉-费马定理（Euler-Fermat theorem），描述了当a和n互质时，a的欧拉函数值与n的模运算结果余数的幂是相等的。

这一定理可以有效用于检验一个数是否为素数，从而在素数测试中起到重要的作用。

此外，欧拉定理在分解整数的质因数和求解同余方程中也有广泛应用。

数学竞赛中的数论问题定理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 的组合数，当然为整数。

函数逼近论函数逼近论是函数论的一个重要组成部分，涉及的基本问题是函数的近似表示问题。

在数学的理论研究和实际应用中经常遇到下类问题：在选定的一类函数中寻找某个函数g，使它是已知函数ƒ在一定意义下的近似表示，并求出用g近似表示ƒ而产生的误差。

这就是函数逼近问题。

在函数逼近问题中，用来逼近已知函数ƒ的函数类可以有不同的选择；即使函数类选定了，在该类函数中用作ƒ的近似表示的函数g的确定方式仍然是各式各样的；g对ƒ的近似程度（误差）也可以有各种不同的含义。

所以函数逼近问题的提法具有多样的形式，其内容十分丰富。

从18世纪到19世纪初期，在L.欧拉、P.-S.拉普拉斯、J.-B.-J.傅里叶、J.-V.彭赛列等数学家的研究工作中已涉及一些个别的具体函数的最佳逼近问题。

这些问题是从诸如绘图学、测地学、机械设计等方面的实际需要中提出的。

在当时没有可能形成深刻的概念和统一的方法。

切比雪夫提出了最佳逼近概念,研究了逼近函数类是n次多项式时最佳逼近元的性质，建立了能够据以判断多项式为最佳逼近元的特征定理。

他和他的学生们研究了与零的偏差最小的多项式的问题，得到了许多重要结果。

已知[α,b]区间上的连续函数ƒ(x)，(n≥0)，叫做ƒ(x)的n阶最佳一致逼近值，简称为最佳逼近值，简记为En(ƒ)。

能使极小值实现的多项叫做ƒ(x)的n阶最佳逼近多项式。

切比雪夫证明了，在区间[-1,1]上函数xn+1的n阶最佳逼近多项式必满足关系式。

多项式就是著名的切比雪夫多项式。

切比雪夫还证明了ƒ(x)在[α,b]上的n 阶最佳逼近多项式的充分必要条件是：在[α，b]上存在着n+2个点：α≤x1<x2<…xn+2≤b，在这些点上依照i=1,2,…,n+2的次序交错变号，像这样的点组{x1,x2,…,xn+2} 便是著名的切比雪夫交错组。

1885年德国数学家K.（T.W.）外尔斯特拉斯在研究用多项式来一致逼近连续函数的问题时证明了一条定理，这条定理在原则上肯定了任何连续函数都可以用多项式以任何预先指定的精确度在函数的定义区间上一致地近似表示，但是没有指出应该如何选择多项式才能逼近得最好。

数论存在性问题选讲数学竞赛中出现的数论存在性问题比较多, 也比较难；求解这些问题的方法灵活多样，往往需要敏锐的观察力、丰富的想象力和必要的技巧. 这里选取了一些问题，尽量展示解决数论存在性问题的各种思想方法.数论存在性问题的解决的方法的关键是综合运用有关数论知识，并结合反证法,归纳法,抽屉原理,计数方法和构造法等. 一. 利用整除理论1. 对于正整数n , ()r n 表示n 分别被1,2,,n 除所得的余数之和. 证明存在无限多个n使得()(1)r n r n =-.解: 由带余除法知, n 被k 除所得的余数等于{}nn k n k k k⎢⎥=-⎢⎥⎣⎦. 所以, 有1()()nk n r n n k k =⎢⎥=-⎢⎥⎣⎦∑.于是, 条件()(1)r n r n =-等价于1111()(1)nn k k n n n k n k k k -==-⎢⎥⎢⎥-=--⎢⎥⎢⎥⎣⎦⎣⎦∑∑. 或111121 (*)nn k k n n n k k k k -==-⎢⎥⎢⎥-=-⎢⎥⎢⎥⎣⎦⎣⎦∑∑ 若k 不整除n , 则1n n k k -⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦⎣⎦, 从而1n n k k k k -⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦⎣⎦;若k 整除n , 则11n n k k -⎢⎥⎢⎥=+⎢⎥⎢⎥⎣⎦⎣⎦, 从而1n n k k k k k -⎢⎥⎢⎥=+⎢⎥⎢⎥⎣⎦⎣⎦. 由此可得(*)等价于|21k nn k -=∑. 易知, 2 ()mn m N =∈满足上式. 事实上, 有1221211222m m n +-=-=++++.因此, 当n 是2的非负整数幂时, ()(1)r n r n =-. 2. (USAMO, 1991) 对于任意整数1n ≥, 证明: 2222, 2, 2,自某项起各项模n 同余.证: 令002a =, 1*2 ()k ak a k N -=∈. 显然, 当i j ≤时, |i j a a . 由抽屉原理知01,,,na a a 这1n +个数中必有两个模n 同余, 所以, 存在0i j n ≤<≤, 使得(mod )i j a a n ≡, 即|j i n a a -.下证从第j 项起各项模n 同余: 即当s j ≥时, 1|s s n a a +-. 只要证: 当s j ≥时有1|j i s s a a a a +--. 即11111111111*122221212222121s s s s s s s j j i j i i i a a a a a a a s s s a a a a a a a j i i a a a N a a a -------------+------==⋅=⋅∈---- 只要*111s s j i a a N a a ----∈-; 同理, 只要 *1222s s j i a aN a a -----∈-, ... ,只要 *1101s i s i s i s i j i j i a a a a N a a a -+--+-----=∈--. 而11112(21)121s i s i s i j i a a a s i s i a j i a a a ---------+----=--, 所以, 只要11|j i s i s i a a a ------.因s j ≥, 所以11s i s i j i ->--≥--. 于是, 有1|j i s i a a ---和11|j i s i a a ----. 故有11|j i s i s i a a a ------.结论得证.3. (MOSP, 1997) 证明数列1, 11, 111,中包含一个无限子列, 其中任意两项是互素的.法一: 设n x 是该数列的第n 项, 则1101n n x x +-=, 从而1(, )1n n x x +=. 为了证明存在一个无限子列, 其中任意两项是互素, 只要证明无论这一子列已经包含了多少项, 总可以再添加一项. 为此, 注意到 *| ()n mn x x m N ∈. 令p 为已包含在子列中的所有项的下标之积, 则子列中的每一项都整除p x . 因此,可以再将1p x +添加到子列中. 结论成立.法二: 设n x 是该数列的第n 项, 则1019n n x -=. 因(,)101101(101,101)101(, )(,)9999m n m n m n m n x x -----===,所以, 当(,)1m n =时, (,)1m n x x =. 因此, 子列{|}p x p 为素数满足要求. 4. 证明存在无限多个正整数n , 使得|2 2 1|21nnn n +-+且. 证: 首先, 有 222|2 2 (21)|21+-+且.假设存在, 2n N n ∈≥, 使得|2 2 1|21nnn n +-+且.由1|21n n -+知, n 为偶数, 且存在奇数*k N ∈, 使得21(1)n n k +=-. 故121(1)21|2121nn n k -+-++=+.上式两边同乘以2, 可得2222|22n n+++.又由1|222(21)n n n -+=+知, 4|n /, 且存在奇数*t N ∈, 使得22nnt +=. 故22(221)21|2121nn n nt ++-=++=+.于是, 当|2 2 1|21n n n n +-+且时, 必有222222|2 2 21|21nnn n ++++++且 . 由此可知,存在无限多个正整数n , 使得|2 2 1|21n n n n +-+且.5. (德国, 2003) 证明: 对于任意6个连续正整数, 存在一个素数, 使得该素数能且只能整除这6个数之一.证: 设这6个连续正整数为, 1, 2, 3, 4, 5n n n n n n +++++.若5|n /, 则1, 2, 3, 4, 5n n n n n +++++中只有一个能被5整除, 结论成立. 若5|n , 则1, 2, 3, 4n n n n ++++不能被5整除, 且其中有两个(相邻奇数)不能被2整除, 这两个(相邻奇数)中至少有一个不能被3整除. 即1, 2, 3, 4n n n n ++++中有一个数不能被2, 3, 5整除. 因此, 该数有一个大于5的素因数p . 因5p >, p 不能同时整除, 1, 2, 3, 4, 5n n n n n n +++++中的两个数, 所以, 素数p 能且只能整除, 1,2,3, 4n n n n n n +++++中的一个数. 6. 设,,a b m 是正整数, (,)1a b =. 证明在等差数列{|0,1,2,}a kb k +=中必有无穷多个数与m 互素.证: 因((), )(, ), *a k m b m a kb m k N ++=+∈, 所以要证在等差数列{|0,1,2,}a kb k +=中必有无穷多个数与m 互素, 只要证: 存在{1,2,,}k m ∈, 使a kb +与m 互素.设c 为使(,)1c a =的m 的一个最大正因数, 并设(, )d a bc m =+. 下证: 1d =, 即(, )1a bc m +=.若1d >, 因(,)1a b =, (,)1a c =, 从而 (,)1a bc =. 又|d a bc +, 所以(,)1(,)d a d bc ==. 由此及|d m 和|c m 可得知|dc m . 再由(,)1d a =及(,)1c a =知, (,)1dc a =. 于是, dc 也是一个使(,)1dc a =的m 的正因数, 与c 的选择矛盾. 故1d =, 即(, )1a bc m +=.7. 证明存在一个映射:**f N N →, 使得对所有*n N ∈, 都有2(())f f n n =. 证: 首先, 定义一个映射:**g N N →, 使得对所有*n N ∈, 都有(())2g g n n =. 取定一个奇素数p , 用()p ord n 表示使|p n α的最大非负整数α. 若()p ord n 为偶数, 则令()2g n pn =; 否则, 令()n g n p=. 下证: (())2g g n n =.若()p ord n 为偶数, 则(())(2)()1p p p ord g n ord pn ord n ==+为奇数, 从而2(())(2)2png g n g pn n p===. 若()p ord n 为奇数, 则(())()()1p p p n ord g n ord ord n p ==-为偶数, 从而(())()22n ng g n g p n p p==⋅=.现定义(1)1f =, 对于正整数1n >, 当n 的素因数分解式为1krkk n p α==∏(0k α>)时, 定义()1()k rg kk f n pα==∏.最后, 有(())2211(())k krrg g kk k k f f n pp n αα=====∏∏. 8. (2008年联赛) 设()f x 是周期函数, T 和1是()f x 的周期且01T <<. 证明:(1)若T是有理数, 则存在素数p , 使1p是()f x 的周期;(2)若T 是无理数,则存在各项均为无理数的数列{}n a 满足110n n a a +>>>(1,2,n =),且每个n a (1,2,n =)都是()f x 的周期.证: (1) 若T 是有理数, 则存在正整数,m n , 使得nT m=且(,)1m n =, 从而有,a b Z ∈,使1ma nb +=. 于是,11bn a a b T m m=+=⋅+⋅是()f x 的周期. 又01T <<, 所以, 2m ≥有素因子. 设p 为m 的一个素因子, 且' ('*)m pm m N =∈, 则11'm p m=⋅是()f x 的周期.(2) 若T 是无理数, 令111[]a T T=-, 21111[]a a a =-, 32211[]a a a =-, ... , 111[]n n na a a +=-, .... 因01T <<且T 是无理数, 由归纳法易证: 01n a <<且n a 是无理数. 又1和T 是()f x 的周期, 由归纳法易证: n a 也是()f x 的周期. 而110[]1n n a a <-<, 所以, 11[]n n n a a a <+, 从而 111[]n n n na a a a +=-<. 因此, 数列{}n a 符合要求.二. 利用不定方程理论9. (Turkey, 1997) 证明对于每个素数7p ≥, 存在一个正整数n 和不被p 整除的整数1212,,,;,,,n n x x x y y y 使得2221122222232221(mod )(mod )(mod )n n x y x p x y x p x y x p ⎧+≡⎪+≡⎪⎨⎪⎪+≡⎩ 证: 1n p =-符合题目要求.首先, 考虑勾股方程组: 2221122222232221n n n x y x x y x x y x +⎧+=⎪+=⎪⎨⎪⎪+=⎩. 多次利用著名的勾股数222345+=可得下面等式:21212122222222232233211212212122(3)(34)(35),(35)(354)(35),(35)(354)(35),(35)(354)(35),(35)(54)(5).n n n n n n n n n n i i n i i n i i n n n --------+-------+⋅=⋅⋅+⋅⋅=⋅⋅+⋅⋅=⋅⋅+⋅⋅=⋅⋅+⋅=即取11135, 354, 1,2,,n i i n i i i i x y i n +----=⋅=⋅⋅=, 且15n n x +=. 为了完成我们的证明,只要注意到由费尔马小定理知,22221111532590(mod )n n p p n x x p --+-≡-≡-≡. (注: 存在无限多个这样的n , 如1p -的所有倍数.) 10. 证明方程33331999x y z t +++=存在无穷多组整数解.证: 注意到 333310100(1)1999+++-=. 我们构造下列形式的整数解: 10x k =-, 10y k =+, z m =, 1t m =--, ,k m Z ∈.代入原方程, 化简得 22(21)801m k +-=.这是一个Pell 方程, 且4, 1m k ==是它的一个解, 并且该Pell 方程有无穷多组解, 故原方程存在无穷多组整数解.11. 证明存在无穷多个正整数a , 使1, 31a a ++都是完全平方数. 证: 设221, 31a y a x +=+=, 则有 223 2 (*)x y -=-这是一个Pell 方程. 下证(*)有无穷多组解, 从而存在无穷多个正整数a , 使1, 31a a ++都是完全平方数.考虑另一个Pell 方程: 223 1 (**)x y -=, 它有无穷多组解, 其最小解为(2,1), 其全部正整数解(,)n n u v 可表示为:(2n n n u =, *n N ∈.对于(**)的一个解(,)n n u v , 令3n n n x u v =+, n n n y u v =+, 则有2232n n x y -=-, 从而(,)n n x y 是(*)的一组解. 因此, (*)也有无穷多组解.(实际上, (*)的全部正整数解(,)n n x y 满足: (2(1n n n x =, *n N ∈ )12. 证明: 存在无限多个正整数n , 使得21|!n n +证: 因Pell 方程2251x y -=-有最小正整数解(2,1), 所以, 它有无限多组正整数解(,)x y . 考虑使5y >的解, 由5y >知, 222451y y x ≤-=, 从而52y y x <<≤. 于是,52|!y y x ⋅⋅, 即22(1)|!x x +, 有21|!x x +. 结论得证.三. 利用同余理论13. (2011年联赛)证明: 对于任意整数4n ≥, 存在一个n 次多项式1110()n n n f x x a x a x a --=++++具有如下性质: (1)011,,,n a a a -均为正整数; (2)对于任意正整数m , 及任意(2)k k ≥个互不相同的正整数12,,,k r r r , 均有12()()()()k f m f r f r f r ≠.证: 令()(1)(2)()2f x x x x n =++++, 展开可知()f x 具有性质(1).下证()f x 具有性质(2).由于4n ≥, *m N ∀∈, ()2(mod 4)f m ≡, 所以, 对任意(2)k k ≥个互不相同的正整数12,,,k r r r , 有12()()()20(mod4)k k f r f r f r ≡≡. 故 12()()()()(mod4)k f m f r f r f r ≡/从而12()()()()k f m f r f r f r ≠. 即()f x 具有性质(2).14. (CMO, 1999) 设m 是给定的整数, 证明存在奇数,a b 和非负整数k , 使得1999199922m a b k =++⋅.证: (1)首先证明: 设*,r s N ∈, s 为奇数, 当t 取遍模2r的简系时, s t 也取遍模2r的简系.设,x y 与2r互素, 且(mod 2)rx y ≡/, 因121()()s s s s s x y x y x x y y ----=-+++且121s s s xx y y ---+++为奇数, 从而与2r 互素, 所以, (mod 2)s s rx y ≡/.故当t 取遍模2r的简系时, st 也取遍模2r的简系.(2)由(1)知, 对于奇数21m -, 必有奇数a 使得19199921(mod 2)m a -≡. 于是, 存在整数q ,使得191999212m a q -≡+⨯. 取奇数1b =, 有1999199922m a b q ≡++⨯. 若0q ≥, 则题中结论已得到证明. 若0q <, 则以199902a a h =-⨯, 1919991919991919019991999(2)(2)22a a h h a a q q q --⨯⨯-+=+=+ 代替a 和q , 仍有199919990022m a b q ≡++⨯. 而当h 足够大时, 可使00q ≥.于是, 结论得证.15. (第16届巴尔干MO) 设3p >为素数, 使3|2p -. 记23{1|,, 0,1}S y x x y N x y p =--∈≤≤-证明S 中至多有1p -个元素是p 的倍数.证: 先证一个引理: 设素数3p >且2(mod3)p ≡, 若33(mod )x y p ≡, 则(mod )x y p ≡.事实上, 若, x y 中有一个是p 的倍数, 则易知引理成立. 若|, |p x p y //, 因p 为素数, 有 (,)(,)1x p y p ==. 于是, 由费马小定理知, 111(mod )p p x y p --≡≡. 又33(mod )x y p ≡且3|2p -, 所以, 221(mod )p p x y p --≡≡, 从而1122(mod )p p p p x y y y x y p ----≡≡⋅≡⋅. 但2(,)1p p x -=, 所以, (mod )x y p ≡.下面证原题:由引理知, 当x 取遍模p 的完系时, 3x 也取遍模p 的完系. 于是, 对于某个固定的{0,1,2,,1}y p ∈-, 恰有一个{0,1,2,,1}x p ∈-, 使得231(mod )y x p -≡, 即23|1p y x --. 注意到y 共有p 种选择, 所以S 中至多有p 个元素是p 的倍数. 又231010S --=∈, 233210S --=∈, 所以S 中至多有1p -个元素是p 的倍数.16. (2006年国家集训队试题) 证明: 对任给正整数, m n , 总存在正整数k , 使得2km -至少有n 个不同的素因子.证: 固定m , 不妨设m 为奇数. 下面对n 用归纳法证明: 对任何正整数n , 存在正整数n k ,使得2n km -至少有n 个不同的素因子.当1n =时, 32mm -至少有一个素因子(其实只要取1k , 使得121k m ->即可).假设2n km -至少有n 个不同的素因子. 令2n kn A m =-, 因m 为奇数, 所以 (,2)1n A =.由欧拉定理知, 2()221(mod )n A n A ϕ≡. 于是, 2()222(mod )n n n k A k n A ϕ+≡, 从而 2()222(mod )n n n k A k n n m m A A ϕ+-≡-=. 令2()12n n k A n A m ϕ++=-, 则1n n A A +>且21(mod )n n n A A A +≡. 所以, 1|n n A A + 且11(mod )n n n A A A +≡, 从而1(, )1n n n A A A +=. 取1n nAA +的一个素因子p , 就有|n p A /. 因此, 1n A +至少比n A 多一个素因子p . 故1n A +至少有1n +个不同素因子.17. (IMO, 2004) 设12,,,n p p p 是大于3的n 个互异的素数, 证明: 1221np p p +至少有4n个不同因数.证: 首先证明一个引理.引理: 若正奇数,u v 满足(,)1u v =, 则(21,21)3u v ++=.因,u v 是正奇数, 所以, 3|21u +和3|21v +. 设(21,21)u v t ++=, 若3t >, 则21(mod )u t ≡-且21(mod )v t ≡-, 从而(2)1(mod )u t -≡, (2)1(mod )v t -≡.考虑同余方程: (2)1(mod )xt -≡, 由于,u v 是它的正整数解, 所以它必有最小正整数解r (即r 是2-模t 的阶). 因3t >, 所以2r >. 然而由r 的最小性知, |, |r u r v , 有|(,)1r u v =, 矛盾. 故3t =, 即(21,21)3u v ++=.其次, 因,u v 是正奇数, 有21|21uuv++, 21|21vuv++. 由引理知, 21(21,)13v u++=, 所以,(21)(21)|213u v uv+++. 下面对n 用归纳法证明原命题:当1n =时, 121p +至少有4个不同因数: 11211, 3, , 213p p ++. 假设12121n p p p -+至少有14n -个不同因数. 对于1221np p p +, 令121, n n u p p p v p -==,由归纳假设知, 21u+至少有14n -个不同因数. 因21(21,)13v u++=, 所以,1(21)(21)3u v m =++至少有124n -⨯个不同因数. 又因|21uv m +, 且,5u v ≥, 所以,2()uv u v ≥+, 从而2()22121uv u v m ++≥+>. 于是, 21uv +的因数个数不小于m 的因数个数的两倍(因为: 若|q m , 则|21uvq +且21|21uv uv q ++, 以及21uv m q+>). 故21uv +的因数个数不少于4n. 结论得证.18.(Russia, 2000)是否存在两两互素的整数, a b 和c 且,,1a b c >使得|21, |21, |21a b c b c a +++.解: 不存在. 用反证法, 关键是利用阶和最小素因数.假设存在两两互素的整数,,1a b c >使得|21, |21, |21a b c b c a +++， 则, a b 和c 都是奇数.首先假设, a b 和c 都是素数. 由题设中的循环条件可设a b <和a c <. 令k 为2对模a 的阶, 由费马小定理知, 121(mod )a a -≡. 又由|21c a +知, 221(mod )c a ≡. 所以, 由阶的性质得 |(2,1)k c a -. 因a 和c 是奇素数且a c <, 有(2,1)2c a -=. 于是, 2k =,从而3a =. 故|219ab +=, 矛盾.若, a b 和c 不全为素数, 我们试着一般化前面的方法. 用()n π表示正整数n 的最小素因子. 我们证明下面一个一般结论:引理: 若素数p 满足|(21)yp +且()p y π<, 则3p =.其证明方法类似于前面关于, a b 和c 都是素数情况的讨论. 令t 为2对模p 的阶, 则有|(2,1)2t y p -=. 从而有2t =及3p =. 故上面结论成立.现回到原题. 因, a b 和c 是两两互素的整数, 所以, (), ()a b ππ和()c π是互不相同的. 不妨设()()()a b c πππ<<, 在上面引理中取(,)((),)p y a c π=可得()3a π=. 记03a a =, 则03|a /. 否则, 9|a , 有9|21c+及221(mod9)c≡. 又仅当6|n 时才有21(mod9)n ≡,必有6|2c , 从而3|c , 与,a c 互素矛盾. 所以, 3不能整除0,,a b c .令0()q a bc π=, 则3()min{(),()}q q b c πππ<=≤. 若|q a , 由,a c 互素知|q c /, 从而()()q q c ππ=<; 又由|q a 知|21c q +, 在上面引理中取(,)(,)p y q c =可得3q =, 矛盾. 因此, |q a /. 类似可得|q c /. 故必有|q b . 进一步, 令r 为2模q 的阶, 则由费马小定理知, 1r q ≤-. 同时, 由|q b 知|21a q +, 从而221(mod )a q ≡. 于是, |2r a . 而2a 的小于q 的素因子只有2和3, 所以, |6r , 从而621(mod )q ≡, 可知7q =. 然而321(mod7)≡, 有00321(2)1(1)12(mod7)a a a +≡+≡+≡. 因此, 7|21a q =+/, 与|q b 及|21a b +矛盾.四. 利用同余数方程理论19. 设p 是素数, 且1(mod 4)p ≡, 证明存在整数,a b , 使22p a b =+. 证: 因素数1(mod 4)p ≡, 所以, 1-是模p 的平方剩余, 即存在整数u , 使210(mod )u p +≡于是存在正整数k , 使21u kp +≡. 即存在正整数k , 使22 (,)kp x y x y Z =+∈若1k =, 则结论成立; 若1k >, 令(mod ), (mod ), ,22k kx r k y s k r s ≡≡-<≤, 则有22220(mod )r s x y k +≡+≡. 所以存在正整数1k , 使得221r s k k +=, 从而222221()()r s x y k k p ++=. 又222222()()()()r s x y rx sy ry sx ++=++-且 220(mod )rx sy x y k +≡+≡和0(mod )ry sx xy yx k -≡-≡, 所以221()()rx sy ry sx k p k k+-+= 即1k p 也可表示为两个整数的平方和. 但222221()()222k k k k k r s =+≤+=, 有12k k k ≤<.因此, 只要1k >, 总存在正整数1k k <, 使得1k p 也可表示为两个整数的平方和. 故p 可表示为两个整数的平方和.(最后一步用到了递降的思想)20. 给定正整数2n ≥, 证明存在n 个不同正整数的集合S , 使得(1)S 中的数两两互素, (2)S 中任意(2)k k ≥个数之和为合数.证: 当2n =时, 结论显然成立. 假设已有n 个不同正整数,,,a a a 符合要求, 下面基于此构造第1n +个符合要求的正整数1n a +.由于素数有无限多个, 故可取21n-个互不相同且均与12n a a a 互素的素数(121)n i p i ≤≤-. 由12,,,n a a a 中任取(1)k k n ≤≤个作成的21n -个和记为(121)n j S j ≤≤-, 其中1k =时的和就是 (1)i a i n ≤≤.因12(, )1i n p a a a =, 所以存在整数i b , 使121(mod )n i i a a a b p ⨯≡. 由孙子定理知, 同余方程组:1111222221212121(mod )(mod ) (*)(mod )n n n n x b b S p x b b S p x b b S p ----≡--⎧⎪≡--⎪⎨⎪⎪≡--⎩ 有无限多个正整数解x , 取定一个解0 (121)n i x p i >≤≤-, 并将(*)中同余式两边同乘12n a a a 得到12010(mod ) (121) (**)n n i i a a a x S p i ⨯++≡≤≤- 令11201n n a a a a x +=+, 则112(, )1n n a a a a +=, 从而1(, ) 1 (1)n i a a i n +=≤≤; 由(**)知1|i n i p a S ++且1n i i a S p ++>, 所以, 1n i a S ++ (1)i n ≤≤是合数. 故121,,,,n n a a a a +符合要求.五. 利用阶乘数,进位制表示,高斯函数性质,韦达定理等21. (2009年联赛) 设,k l 是给定的两个正整数, 求证: 有无穷多个正整数m k ≥, 使km C 与l 互素.证: 令!m k n l k =⨯⨯+, *n N ∈, 则有11!!!(1)(1)(1)1(mod )1111km m m m k k k k C nl nl nl l k k k k --+=⋅=⋅+⋅+⋅+≡-- 所以, (, )1km C l =.22. 是否存在一个严格递增的正整数序列1{}k k a ∞=, 使得对于任何整数a , 序列1{}k k a a ∞=+只含有限多个素数.法一: 这样的序列是存在的. 事实上, 对于每个正整数k , 取3(!)k a k =. 若1a =±, 则由321(1)(1)x x xx ±=±+知, 3(!)1k a a k +=±是合数. 若||1a >, 则对于||k a ≥, 有|!a k , 这表明对于所有||k a ≥, 都有|a a a +.法二: 取(2)!k a k k =+. 对于所有整数k , ||k a ≥且2k a ≥-, 有22k a k ≤+≤. 因此,|k k a a a ++, 从而对于所有这样的k , k a a +是合数.23. (2007年联赛) 设集合{1,2,3,4,5}P =, 对任意k P ∈和正整数m ,记51(,)[i f m k m ==∑, 其中[]a 表示不大于a 的最大整数. 求证: 对任意正整数n , 存在k P ∈和正整数m , 使得(,)f m k n =.证: 由高斯函数的定义知, [m是不超过m , 即这样的正整数i m 的个数: m ≤于是,令{| *}{| *}i B b b m b N b b N =≤∈=≤∈, 1,2,3,i =,则有||[i B m =, 从而125(,)||||||f m k B B B =+++.又令{*}i C b N =∈, 1,2,3,i =, 显然, i B 与i C 中的元素是一一对应的, 所以, ||||i i B C =, 从而125(,)||||||f m k C C C =+++.由于当12,k k P ∈且12k k ≠时是无理数, 所以, 对任意12,k k P ∈以及正整数12,b b , 有12,12 b b b b k k =⇔== (*)因此, 当,i j P ∈且i j ≠时,i j C C =∅.故125(,)|||{, *}|f m k C C C i P b N ==≤∈∈.定义集合{*, }A b b N i P =∈∈, 由(*)知集合A 中无重复元素. 注意到A 是一个无穷集合, 现将A 中的元素按从小到大的顺序排成一个无穷数列(即递增数列){}n a , 即12{,,,,}n A a a a =, 其中 12n a a a <<<<.对任意正整数n , 由于此数列的第n 项a A ∈, 所以存在k P ∈和正整数m , 使得n a =. 而12125{,,,}{1|11, , *}n a a a b i b i m k i P b N C C C =++≤+∈∈=所以, 125||(,)n C C C f m k ==.24. (2008年中国女子数学奥林匹克) 对于正整数n , 令[2[2n f =+, 求证: 数列12, ,f f 中有无穷多个奇数和无穷多个偶数.证: 由于题设中含有2n, a 和b ., 所以, a 和b 都是非循环的. 而n f 是奇数还是偶数, 取决于a 和b 的小数点的第n 是否相同. 如果数列12, ,f f 中只有有限多个奇数, 则在某个n 以后, 所有的 ()k f k n ≥都是偶数.这说明在a 和b 的小数点后n 位开始, 每一位都相同, 从而a b -在二进制表示下是有限小数, 即是有理数. 这是不可能的. 如果数列12, ,f f 中只有有限多个偶数, 则在某个n 以后, 所有的 ()k f k n ≥都是奇数数. 这说明在a 和b 的小数点后n 位开始, 每一位都不相同, 从而a b +在二进制表示下是循环小数, 即是有理数. 这是不可能的. 因此, 数列12, ,f f 中既有无穷多个奇数又有无穷多个偶数.25. 证明由[n a =定义的数列{}n a 中有无穷多个项是2的整数幂.法一: 将用二进制表示:012301230123. 2222b bb b b b b b ---==⨯+⨯+⨯+⨯+,{0,1}i b ∈. , 所以有无穷多个正整数k , 使得1k b =.若1k b =, 则2k -: 01112. k k k k b b b b b --+=. 令[2k m -=,则121222k k k m b b ---+=+⨯+⨯+, 从而121[2]22k k k m -<=<-.得 2(222kkm <+<+. 这时有 [(2k m +=. 因这样的正整数k 有无穷多个, 所以, 这样的正整数1n m =+也有无穷多个, 即数列{[]}中有无穷多个项是2的整数幂. 法二: 我们要构造满足其性质的一类正整数n , 同时满足这种性质的正整数有无穷多个.2k k =, 使[2k=的正整数n k 从而1k n ≥+.构造集合{|]1, k }k B b b A ==+∈, *{1 k }k A k N =>∈, 则b B ∀∈,k A ∃∈,使1kb =+. 这时[1)]1)][22k k k k kb k k a ==+=-+==+由k A ∈知, 12k >-而1k <, 所以,1(12k <<-,即01k <<.故0k=. 于是, 2k b a =是2的整数幂.下面只要证集合B 是无限集.假设A 是有限集, 显然A ≠∅, 则A 有最大项1m ,即112m >-1m m >, 均有12m ≤-于是,111122m +≤-<,1111111121111111{2{2{22{22m m m m m m m m ++++++++==⨯+=⨯+⨯=⨯=⨯同理可得11322m m ++=⨯, 11432m m ++=⨯, ..., 1112m k m k+++=⨯,*k N ∈. 所以, 11112m k m k+++=⨯. 但事实上,因110m +>及11m +是固定的知,k充分大时可使112m k+⨯的值也充分大,与111m k ++<矛盾. 故A 为无限集.又对任意12,k k A ∈, 12k k <,2122k k ≥>,2111k k k ≥>. 所以,211k k ≥+, 从而2111k k +≠+. 由A 是无限集知, B 也是无限集. 即由有无限多个正整数n 使得[为2的整数幂.26. (USAMO,1996)确定并证明是否存在整数集的一个子集X , 使得对于任何整数n , 方程2a b n +=在X 中恰好有一个解(,)a b .法一: 这样的子集存在. 若问题限制在非负整数集合内, 则取其四进制表示中只含数码0和1的非负整数构成的集合满足要求. 为了也适合负整数, 考虑“-4”进制. 即将每个整数表示为(4)kii i c =-∑, 其中对于所有i , {0,1,2,3}i c ∈且0k c ≠, 并取{(4)|{0,1}, }kii i i X c c k N ==-∈∈∑为“-4”进制表示中只含数码0和1的整数构成的集合. 下面证明X 满足要求.首先, 每个整数的“-4”进制表示是唯一的. 令{}i c 和{}i d 是元素属于{0,1,2,3}的两个不同的有限序列, j 是使得j j c d ≠的最小整数, 则0(4)(4)(mod 4)k kiijiii i c d ==-≠-∑∑, 从而由{}i c 和{}i d 所表示的两个整数不相等. 其次, 设整数n 的“-4”进制表示为0(4)kiii n c ==-∑, 其中{0,1,2,3}ic ∈. 对于给定的{0,1,2,3}i c ∈, 易知方程2i i i a b c +=在{0,1}内恰有一个解(,)i i a b , 即在X 中有唯一一对整数0(4)k iii a a ==-∑和0(4)kiii b b ==-∑, 使得2n a b =+. 因此, X 满足要求.法二: 对于整数集的任一子集S , 令*{2|,}S a b a b S =+∈. 若12{,,,}m S a a a =使*2||||S S =, 即这些值2(1,)i j a a i j m +≤≤是互不相等的, 则称S 是一个好集合.首先, 我们证明: 对于给定的好集合S 和整数n , 总可以找到一个包含S 的好集合T , 使得*n T ∈. 事实上, 若*n S ∈, 则取T S =即可. 否则, {,2}T Sk n k =-, 其中k 为待定整数. 此时, *T 可分解为**T SQ R =, 其中{3,3(2),2(2),(2)2}Q k n k k n k n k k =-+--+{2,(2)2,2,2(2)|}R k a n k a a k a n k a S =+-+++-∈.任取一个整数k , 都有(2)2n n k k =-+属于*T 的子集Q . 除n 外, 新产生的元素均为k 的不同的非常数线性形式, 所以, 当k 充分大时, 它们互不相同且都不同于*S 中的元素.这就证明了*T 是一个好集合.其次, 从好集合0{0}X =出发, 由上可得一系列好集合12,,X X ,使得对于每个正整数j ,j X 是包含1j X -的好集合, 且*j X 含有序列1,1,2,2,3,3,---的第j 项. 于是,12X X X X =满足要求.27. (第43届IMO 预选题) 是否存在正整数m , 使方程1111m a b c abc a b c+++=++有无穷多组正整数解.解: 存在. 注意到取1a b c ===时, 有12m =. 令111112(,,)()f a b c a b c abc a b c abc a b c +++-=++++, 其中 22222222(,,)()()()9()(19)f a b c a b c b c a c a b a b c abc a b c a b c bc b c c b b c=++++++++-=++++-++++是一个关于,,a b c 的对称多项式. 假设(,,)x a b 是满足(,,)0f x a b =的一组解, 且x a b ≤≤. 由于(,,)0f x a b =是关于x 的二次方程, 所以, 1ab y x+=是其另一个解, 即1(,,)0ab f a b x +=, 且1ab y b x+=>. 设0121a a a ===, 定义1211(n N*)n n n n a a a a ++-+=∈. 下证:(1) 11|1n n n a a a -++; (2) 11|n n n a a a -++; (3) 11|1n n n a a a +-+.对n 用归纳法. 当1n =时, 以上三个结论都成立. 假设n k =时以上三个结论成立, 由(1)得11|1k k k a a a -++. 于是, 1(,)1k k a a -=, 且21111111|(1)k k k k k k k k k a a a a a a a a a -++-++-++=++. 由(2)得11|k k k a a a -++, 且2111|k k k k k a a a a a ++-++. 所以, 21111|k k k k k k a a a a a a -++-++, 即1111|(+1)k k k k k a a a a a ++-+⋅, 也即12|(+1)k k k a a a ++⋅. 于是, 当1n k =+时(1)成立.同理, 由于11(,)1k k a a -+=, 且111|(1)k k k k k a a a a a -+-++. 由(3)得11|1k k k a a a +-+, 且111|(1)k k k k k a a a a a +-+++. 所以, 1111|(1)k k k k k k a a a a a a -+-+++, 即1111|()k k k k k a a a a a ++-++, 也即12|()k k k a a a +++. 于是, 当1n k =+时(2)成立.由2k a +的定义及(1)知, 2k a +是整数且21|(+1)k k k a a a ++, 即当1n k =+时(3)也成立. 因此, 可得数列{}n a , 当2n ≥时它严格递增, 且12(,,)0n n n f a a a ++=, 从而12(,,)(,,)n n n a b c a a a ++=是原方程的一组解. 故存在正整数12m =, 使方程1111m a b c abc a b c+++=++有无穷多组正整数解. 28. (集训队试题) 设()S x 表示数列{[]}, *nx n N ∈, 证明方程321029250x x x -+-=有相异的两个实根, αβ, 使()()S S αβ中有无穷多个正整数.证: 记32()102925f x x x x =-+-, 则(1)5f =-, (2)1f =, (3)1f =-, (5)5f =-,(6)5f =. 于是, 方程()0f x =在区间(1,2), (2,3), (5,6)中各有一个根. 设这三个实根为,,αβγ, 则,,1αβγ>且1112925αβγ++=. 对于任意给定的正整数M , 用'(), '(), '()S S S αβγ分别表示(), (), ()S S S αβγ中小于等于M 的数的集合, 则|'()|[], |'()|[], |'()|[]MMMS S S αβγαβγ≥≥≥(见下面注).以{1,2,,}M 为全集, 由容斥原理知,|'()'()||'()'()||'()'()||'()||'()||'()||'()'()'()||'()||'()||'()|[][][](1)(1)(1)1114(1)3325S S S S S S S S S S S S MS S S MM M M M M MM MM M αβαγβγαβγαβγαβγαβγαβγαβγ++=+++-≥++-≥++->-+-+--=++--=- 所以, 当M →∞时, |'()'()|, |'()'()|, |'()'()|S S S S S S αβαγβγ中必有一项趋于无穷大. 因此, 方程必有两个实根(设为, αβ), 使()()S S αβ中有无穷多个正整数.注: 令[]Mk α=, 当1α>时有[(1)][]n n αα+>, 所以, [],[2],,[]k ααα是互不相同. 又({}){}MM Mk M M αααααα=-=-<, 所以, {[],[2],,[]}'()k S αααα⊆. 故|'()|[]MS k αα≥=.29. (IMO 预,1987) 证明对于每个正整数2k ≥, 存在一个无理数r , 使得对于每个正整数m , []1(mod )m r k ≡-.证: 若二次方程: 2()0f x x akx bk =-+=, 其中,a b 为整数, 且有无理根r 和s 使得(0,1)s ∈, 则由韦达定理, 0(mod )r s ak k +=≡, 0(mod )rs bk k =≡. 利用1111()()()m m m m m m r s r s r s rs r s ++--+=++-+及0, 1m =时, 2, m m r s ak +=, 可对m 用归纳法证明mmr s +为整数. 因(0,1)s ∈, 所以, []1m m m r r s +=+, 且因0(mod )rs k ≡, 有[]10(mod )m m m r r s k +=+≡.最后, 为了得到满足要求的二次方程, 考虑判别式224a k bk ∆=-. 取2, 1a b ==, 有222(22)44(21)k k k k -<∆=-<-可得其根r 和s 是无理数, 且12122k s <=<.。

利用二次函数对称性解决问题【西湖数论之我来讲题】第62
题
Ⅰ、归于函数模型：即利用一次函数的增减性和二次函数的对称性及增减性，确定某范围内函数的最大或最小值；
Ⅱ、归于几何模型，这类模型又分为两种情况：
（1）归于“两点之间的连线中，线段最短”。

凡属于求“变动的两线段之和的最小值”时，大都应用这一模型。

（2）归于“三角形两边之差小于第三边”凡属于求“变动的两线段之差的最大值”时，大都应用这一模型。

利用二次函数的对称性求最值问题是函数教学的一个难点问题，不仅要求学生掌握函数的基本要素，还要把几何图形和二次函数知识结合，综合运用图形的数形结合的能力。

在这个微课教学中，教师要让学生知道始点在哪里，终点在哪里，这两个点所在的图形有什么特征？从而确定这条对称轴。

解决这些问题关键是要掌握二次函数的对称性，明确图象上的任何一点关于对称轴对称的点也一定在此抛物线上。

再利用求“最值”的几何模型（1）：求“变动的两线段之和的最小值”时，大都应用“两点之间的所有连线中，线段最短”这一模型。

所以，二次函数是一件“外衣”，是一个工具。

希望学生能通过这样的一个教学对这一类题型触类旁通，解一题知一片。

数学与数论探索数论中的数学奥秘数学与数论探索数论中的数学奥秘数学是一门严谨而深奥的学科，而数论则是数学中的一门重要分支。

在数论中，隐藏着许多令人着迷的数学奥秘，本文将探索数论中的一些数学奥秘。

一、质数的奥秘质数一直以来都是被数学家们所关注的对象。

质数是指只能被1和自身整除的自然数，例如2、3、5、7等。

虽然质数的定义看起来很简单，但质数间的分布却并不规律。

这给数学家们带来了许多困惑和挑战。

最著名的数论问题之一是哥德巴赫猜想。

哥德巴赫猜想认为，任何一个大于2的偶数都可以表示为两个质数的和。

虽然这个问题已经被证明是正确的，但证明过程却非常复杂，需要运用到许多高深的数论知识。

二、费马大定理费马大定理是数论中最著名的问题之一，也是数学史上最难以证明的定理之一。

费马大定理的表述是：对于任何大于2的自然数n，方程x^n+y^n=z^n不存在整数解。

这个定理由法国数学家费马在17世纪提出，但直到近四百年后的1994年，英国数学家安德鲁·怀尔斯才给出了一种完整的证明方法。

费马大定理的证明涉及到了代数几何、模形式、椭圆曲线等许多高深的数学领域。

它的证明方法被称为“怀尔斯证明”，成为数论研究中的里程碑。

三、尼科彻斯定理尼科彻斯定理是数论中的一个重要定理，它刻画了一个自然数的因素个数与该数自身的大小关系。

尼科彻斯定理的表述是：对于任意一个大于1的正整数n，都可以表示为p_1^a_1 * p_2^a_2 * ... * p_k^a_k 的形式，其中p_1 < p_2 < ... < p_k为质数，a_1, a_2, ..., a_k为正整数。

尼科彻斯定理的证明相对来说比较简单，但这个定理本身却具有重要的数论意义。

通过尼科彻斯定理，我们可以更好地理解自然数的性质和结构。

四、哥德巴赫猜想的证明哥德巴赫猜想的证明是数论研究中的一大难题。

虽然这个猜想的正确性已经被证明，但是其证明过程却非常复杂，需要运用到许多高深的数论理论和技巧。

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

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．整点多边形问题如果一个多边形的所有顶点都是整点，则称这个多边形为整点多边形·平面直角坐标系中是否存在整点正n 边形？对于n=4，我们知道存在整点正方形，对于n=3，n ≥5呢？例1证明：不存在整点正三角形． 证 反证法，，设平面上3个整点A ，B ，C 组成一个正三角形·由于向上、下或左、右平移整数个单位，整点仍然变为整点，因此不妨设A 为原点，|AB| = r , B ，C 的坐标分别为（a ，b ），（x ，y ），其中a ，b ，x ， y ∈R 如图8-5．于是,2321)sin 23cos 21()3cos(b a r r x -=-=+=θθπθ .2321)cos 23sin 21()3sin(a b r r y +=+=+=θθπθ因为a ，b 均为整数，且至少有一个不为零，所以x ，y 不可能均为整数，矛盾.因此不存在整点正三角形．例2证明：不存在整点正五边形·证 设存在一个整点正五边形ABCDE ，边长为a ，如图8-6， 易知边长a 与对角线d 的比da满足⋅=-251d a 由两点间的距离公式知，任意两个整点的距离的平方是整数，所以a 2和d 2均为整数，从而22da 是有理数，但是,253)215(222-=-⋅=d a 上式右端是一个无理数，矛盾。

因此，整点正五边形是不存在的．下面我们给出本题的另一证法．设存在整点正五边形，在所有的整点正五边形中选出边长最短的一个，记作ABCDE ，连接所有的对角线-得五边形1111E D C B A I 如图8—7．易知五边形1111E D C B A I 是正五边形．又因为E ABA 1为平行四边形，A ，B ，E 是整点，令A ，B ，A 1，E 的坐标为),,(11y x ),,(),,(),,(443322y x y x y x 则,224231x x x x +=+ 所以⋅-+=1423x x x x 同理,1423y y y y -+= 所以A 1也是整点，同理，1111,,,E D C B均为整点·这样就得到了一个比ABCDE 边长更短的整点正五边形,11111E D C B A 矛盾·我们用完全类似的方法可以证明整点正n 边形不存在。

莫比乌斯的原理以及应用1. 什么是莫比乌斯的原理莫比乌斯的原理，也被称为莫比乌斯反演定理，是组合数学中一条重要的定理，由德国数学家奥古斯特·莫比乌斯在19世纪提出。

这个定理是一种在组合数学中计算莫比乌斯函数的方法，莫比乌斯函数是数论中的一个重要函数，用于描述数论中的互素性质。

2. 莫比乌斯函数的定义莫比乌斯函数μ(n)是一个数论函数，对于正整数n，定义如下：•当n为1时，μ(n) = 1；•当n为质数的幂时，μ(n) = -1；•当n包含大于1的平方因子时，μ(n) = 0。

3. 莫比乌斯的原理表述莫比乌斯的原理可以用如下方式表述：对于任意两个互逆的函数f(n)和g(n)，当一个等式关系成立时：∑_{d|n}f(d) = \sum_{d|n}g(d)则另一个等式关系也成立：∑_{d|n}μ(d)f(n/d) = g(n)其中，∑_{d|n}表示对n的所有正因子d求和。

4. 莫比乌斯的原理的应用莫比乌斯的原理在组合数学和数论中有广泛的应用，下面介绍几个主要的应用。

4.1 整数除法分块问题给定一个正整数n和另外n个整数a_1, a_2, …, a_n，求∑_{i=1}{n}∑_{j=1}{n} [a_i /a_j]的值，其中 [] 表示取整函数。

这个问题可以使用莫比乌斯的原理解决，具体步骤如下：1.定义f(n)为∑_{i=1}{n}∑_{j=1}{n} [a_i / a_j]；2.定义g(n)为n^2；3.利用莫比乌斯的原理，可以得到另一个等式：∑_{d|n}μ(d)f(n/d) =g(n)；4.再根据等式关系，可以得到f(n) = ∑_{d|n}μ(d)g(n/d)。

通过以上的推导，我们可以得到等式关系来解决整数除法分块问题。

4.2 莫比乌斯反演莫比乌斯反演是利用莫比乌斯函数求解组合数学问题的一种方法。

莫比乌斯反演可以用于求解一些关于集合的问题，例如计算集合交、集合并的个数等。

莫比乌斯反演的基本思想是通过莫比乌斯函数μ(n)和一个函数f(n)之间的等式关系来求解另一个函数g(n)。

余数函数知识点总结一、余数函数的概念1. 余数函数的定义余数函数是一个映射关系f:Z→Z，其中 Z 表示整数集，在余数函数中，f(x)表示整数x÷n的余数。

例如，当n=3时，余数函数f(x)=x%3，表示整数x÷3的余数。

这里的%表示取余运算，即x÷3的余数。

2. 余数函数的符号表示一般情况下，余数函数在数学中的符号表示为“mod”，用数学符号表示为：x mod n。

3. 余数函数的意义余数函数可以用来表示两个整数之间的关系，特别是对于循环、周期性和同余关系等数学问题有着重要的应用。

二、余数函数的性质1. 唯一性对于任意的整数x和正整数n，整数x对于模n的余数是唯一的，即对于模n，任意的整数x只能有唯一的余数。

这可以通过对除法的基本性质来证明。

2. 周期性对于模n来说，余数函数具有周期性，即对于任意的整数x，x对于模n的余数总是在0到n-1之间的一个整数。

这是因为当x增加或减少n的整数倍时，它们的余数是相同的。

3. 同余关系两个整数a和b对于模n的余数相同，就称它们在模n下是同余的，这可以表示为a≡b(mod n)。

同余关系具有一些特殊的性质，比如同余的整数具有相同的余数，同余的整数可以进行加、减、乘运算等。

4. 余数函数的性质余数函数具有一些特殊的性质，比如：（1）f(x)=0，当且仅当x被n整除（2）f(x)的取值范围在0到n-1之间（3）f(x)和f(x+n)的值是相同的三、余数函数的应用1. 除法运算余数函数常常用来表示除法运算的结果。

在计算机科学和密码学中，余数函数被广泛应用，比如在计算机的取模运算、数据加密和校验码等方面。

2. 周期性问题在数学中，许多周期性问题可以通过余数函数来进行分析和解决，比如循环小数的性质、周期函数的周期性等。

3. 同余关系问题同余关系是数论中的一个重要概念，通过余数函数可以方便地描述和分析同余关系的性质和应用。

四、相关概念1. 最大公约数最大公约数是指整数a和b的公约数中最大的一个数，通常表示为gcd(a, b)。

伽马函数的展开问题伽玛函数的展开问题引发了数学界的广泛讨论和研究。

本文将从简单到复杂的角度来探讨伽玛函数的展开问题，帮助读者全面、深入地理解这个主题。

1. 了解伽玛函数的概念伽玛函数是一种特殊的数学函数，通常用Γ(x)表示，定义为：Γ(x) = ∫[0, +∞] t^(x-1) * e^(-t) dt伽玛函数在数学和应用中发挥着重要的作用，如在概率论、组合数学、数论等领域都有广泛的应用。

然而，计算伽玛函数的积分并不容易，因此研究伽玛函数的展开问题成为了重要的课题。

2. 简单的伽玛函数展开伽玛函数的最简单展开形式是在x接近0时的泰勒展开式：Γ(x) ≈ 1/x - γ (当x接近0)其中γ是欧拉常数，约等于0.577。

这个展开式的推导可以通过分部积分和利用欧拉常数的性质得到，对于较小的x值，此近似式可以提供一个良好的近似结果。

3. 更复杂的伽玛函数展开除了简单的近似展开，伽玛函数还有更复杂的展开形式，如斯特林公式的展开和阿贝尔-普拉塔展开等。

- 斯特林公式的展开：斯特林公式是伽玛函数的另一种重要展开形式，表达为：n! ≈ (√(2πn))(n/e)^n这个公式的推导过程非常复杂，但可以在一定条件下提供一个较好的近似结果，特别是当n非常大时。

- 阿贝尔-普拉塔展开：阿贝尔-普拉塔展开是一种较为复杂的伽玛函数展开形式，可以将伽玛函数表示为级数的形式：Γ(x) = 1/x + γ - x/2 + ∑[n=1, +∞]((-1)^n * B_(2n) * x^(2n-1))/(2n*(2n-1))其中B_n是伯努利数。

这个展开式可以在特定条件下提供更精确的结果，但计算复杂度相应增加。

4. 个人观点和理解伽玛函数的展开问题是数学中一个非常有趣和有挑战性的问题。

通过展开伽玛函数，我们可以更好地理解它的性质和应用。

简单的近似展开式可以在某些情况下提供满足要求的结果，但对于更精确的计算和研究，复杂的展开形式更为重要。

数论函数【内容综述】本讲介绍数论中常见的一些函数的概念、性质及其应用，主要有除数函数——自然数n的正因数的个数函数；——自然数n的全部正因数的和函数；欧拉函数——设n是大于1的自然数，则欧拉函数是表示与n互素且不大于n的自然数的个数；（高斯函数或称方括号函数[X]在下讲介绍）为书写清楚，同学们应熟悉连加符号“”与连乘符号“”：；特别是“”表示对称式的和；“”表示对称式的积abc……；【要点讲解】§1．约数个数函数§2．约数和函数§3．欧拉函数φ(n)★★★§1．约数个数函数定义1 设，则的正约数的个数称为函数。

定理1 设，且是质数，则略证：由乘法原理，约数系由、、…、的不同取法而生成，它们的取法分别有种（含不取该约数的1种取法），故得证例1. 求24的正约数个数。

解：事实上，易求得约数分别是1，2，3，4，6，8，12，24；个数正是8个。

§2 约数和函数定义设，，则称的正约数和为函数。

定理2 自然数的正约数和函数（其中为的素数，）。

略证注意到（），展开后，其项数恰为的约数个数，又每项皆形如，可见每项皆自然数的约数且每个约数只出现一次，由此可见该积即，于是有例2. 求780的正约数和。

解：定理3 若、是互质的自然数，即(a，b)=1，则证明：设，，∵，故与各不相同（i=1，2，…，j=1，2，…，m）§3.欧拉函数定义设互素且不大于的自然数的个数(),称为欧拉函数。

如，易证是素数（∵每个小于的自然数都与它互素）；反之可见，若是合数，必有。

关于欧拉函数，有以下性质定理定理４设P是素数，且则证明∵P是素数，显然有与互素的充要条件是，即有：，反之若，且知在1和之间，有以下个数是p的倍数：，而其余的数都与互素，从而可知不超过且与互素的自然数个数。

当自然数的素因数分解式中，不只包含一个素因数时，有定理5 设大于1的自然数的素因数分解式为，其中则有证明：因为素因数的个数，故考虑采用数学归纳法（下设表有k个素因数的自然数）。

第五节 数论函数定义在整数集合上的函数，称为数论函数，或算术函数。

例如，函数y = x 2，y = sin x ，y = e x都可称为数论函数。

但是，通常在使用数论函数这个词时，仅指那些只在整数集合或正整数集合上有定义的函数，或者只与数论研究有特殊关系的函数，例如，在前面所遇到过的欧拉函数ϕ(n )，整数部分函数[x ]。

本节中还要介绍几个数论函数。

定义1 设f (n )是定义在整数集合A 上的函数，若f (mn ) = f (m )f (n ) (1)对所有的整数m , n ∈A ，(m , n ) = 1成立，则称f (n )是A 上的积性函数，或者，在不引起误会的情况下，简称为积性函数。

如果式(1)对于A 中的任何m ，n 都成立，则称f (n )是A 上的完全积性函数，简称为完全积性函数。

以下，我们总假定A 是由全体正整数所成的集合，即A = N 。

例1 函数ϕ(n )是积性函数，但不是完全积性函数。

事实上，由第三节定理4我们知道ϕ(n )是积性函数。

由2 = ϕ(4) ≠ ϕ(2)ϕ(2) = 1可知ϕ(n )不是完全积性函数。

例2 以d (n )表示正整数n 的正约数的个数，则d (n )是积性函数，但不是完全积性函数。

例3 函数μ(n ) =⎪⎩⎪⎨⎧=-=其他情形是互异的素数，当当0,,,)1(112121r r rp p p p p p n n ， 是积性函数，但不是完全积性函数。

事实上，容易看出μ(n )是积性函数。

由1 = μ(2)μ(2) ≠ μ(4) = 0可知μ(n )不是完全积性函数。

定理1 设函数f (n )是不恒等于零的数论函数，则f (n )是积性函数的充要条件是：f (1) = 1并且对任意的n ∈N ，n > 1，有)()()()(21212121k kk k p f p f p f p p p f αααααα =， (2)其中n =kk p p p ααα 2121是n 的标准分解式。