数学竞赛中的数论问题

《数学竞赛中的数论问题》由会员分享，可在线阅读，更多相关《数学竞赛中的数论问题（47页珍藏版）》请在金锄头文库上搜索。

1、数学竞赛中的数论问题 罗增儒引言数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，是这样一个集合：（1）有一个最小的数1 （2）每一个数的后面都有且只有一个后继数；除1之外，每一个数的都是且只是一个数的后继数这个结构很像数学归纳法，事实上，有这样的归纳公理：（3）对的子集，若，且当时，有后继数，则就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度比如，哥德巴赫猜想：174

2、2年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和后者是前者的推论，也可独立证明（已解决）“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1欧拉认为这是对的，但证不出来1900年希尔伯特将其归入23个问题中的第8个问题1966年陈景润证得：一个素数+素数素数（1+2），至今仍无人超越陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠”陈景润就是由此而受到了启示和激励，展

3、开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（UDudley数论基础前言）下面，是一个有趣的故事当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有个正整数，这些正整数小于或等于，那么你一定有一对整数是互素的，你知道这是什么原因吗？不到12岁的

4、波萨只用了1分半钟，就给出了问题的解答他将1分成（1，2），（3，4），（）共个抽屉，手头的个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的

5、、新鲜而有趣的题目数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程 在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数，费马小定理，格点及其性质，无穷递降法，欧拉定理，孙子定理根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型：（1）奇数与偶数（奇偶分析法、01法）；（2）约数与倍数、素数与

6、合数；（3）平方数；（4）整除；（5）同余；（6）不定方程；（7）数论函数、高斯函数、欧拉函数；（8）进位制（十进制、二进制）下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解第一讲 数论题的基本内容中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理首先约定，本文中的字母均表示整数定义1 （带余除法）给定整数如果有整数满足 ，则和分别称为除以的商和余数特别的，时，则称被整除，记作，或者说是的倍数，而是的约数（的存在性由定理1证明）定义2 （最大公约数）设整数中至少有一个不等于零，这个数的最大公约数是能整除其中每一个整数的最大正整

7、数，记作 中的没有顺序，最大公约数也称最大公因数简单性质：一个功能：可以把对整数的研究转化为对非负整数的研究定义3 （最小公倍数）非零整数的最小公倍数是能被其中每一个所整除的最小正整数，记作简单性质：如果是正整数的公倍数，则存在正整数使证明若不然，有（），由都是的公倍数得也是的公倍数，但，与的最小性矛盾故定义4 如果整数 满足，则称与是互素的（也称互质）定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）其余大于1的正整数称为合数；数1既不是素数也不是合数定理1 若是两个整数，则存在两个实数，使，并且是唯一性证明1 先证存在性作序列则必在上述序列的某两项之间，从而存在

8、一个整数，使 ，即 ，取 ， ，得 ，即存在两个实数，使 再证唯一性假设不唯一，则同时存在与，使 ， ，相减 ， ， ，但为整数，故，得，从而注：如果取消，当或，不保证唯一经典方法：紧扣定义，构造法证存在性，反证法证唯一性证明2 只证存在性，用高斯记号，由 ，有 ，记，故存在使证明3 只证存在性，作集合 这是一个有下界的非空整数集，其中必有最小的，设时，有最小值 再证，若不然，记，有 即有比更小，这与为最小值矛盾故存在两个实数，使定理2 设是三个不全为0的整数，满足，其中也为整数，则证明 设的公约数， 的公约数任取，任取，得 有中元素的最大值中元素的最大值，即注：这是辗转相除法求最大公约数的理

9、论基础经典方法：要证明，只需证且定理3 对任意的正整数，有 证明 因为是的公倍数，所以的最小公倍数也是的约数，存在使 ，有 且为整数，故是的约数同理是的约数，即是的公约数下面证明，是的最大公约数若不然，有 设，可见是的倍数，同样，是的倍数，即是的公倍数，则存在正整数使，有，得 与矛盾，所以，得证注 也可以由，得，与矛盾两步可以交换吗？定理4 是两个不同时为0的整数，若是形如（是任意整数）的数中的最小正数，则（1）|；（2）证明 （1）由带余除法有 ，得 ，知也是形如的非负数，但是形如的数中的最小正数，故，即| （2）由（1）有|，|，得是的公约数另一方面，的每一个公约数都可以整除，所以是的最大

10、公约数，推论若，则存在整数，使（很有用）定理5 互素的简单性质： （1）（2）（3）（4）若是一个素数，是任意一个整数，且不能被整除，则证明 因为，所以，素数的约数只有两种可能：但不能被整除，得推论 若是一个素数，是任意一个整数，则或（5）若，则存在整数，使（定理4推论）（6）若，则证明 由知存在整数，使有 ，得 （7）若，则， 证明 ， ，由（6）（8）若，则，其中为正整数证明 据（6），由可得 同样，由可得定理6 设是大于1的整数，则的除1之外的最小的正约数必是素数，且当是合数时，证明 用反证法，假设不是素数，则存在正整数数，使，但，故有，这与是的除1之外的最小正约数矛盾，故是素数当是合数

11、时，设，则也是的一个正约数，由的最小性得，从而，开方得定理7 素数有无穷多个，2是唯一的偶素数证明 假设素数只有有限多个，记为，作一个新数 若为素数，则与素数只有 个矛盾若为合数，则必有，使，从而，又与矛盾综上所述，素数不能只有有限多个，所以素数有无穷多个2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数注：这个证明中，包含着数学归纳法的早期因素：若假设有个素数，便有个素数（构造法、反证法）秒定理8（整除的性质）整数通常指非零整数（1），；当时， （2）若，则;若，则;若，且，则证明 由，有，得逆反命题成立“若，则”;由且得，又，得（3）若，且，则（4）若，则证明 （定义法）由，有 ，得

12、，即 （5）若，则（6）若，则对任意整数，有证明 （定义法）由，有 ，得 ，即 （7）若，且，则证明 由知存在整数，使，有， 因为，所以整除等式的左边，进而整除等式的右边，即注意 不能由且得出如，但且（8）若，且，则证明 由知存在整数，使，有， 又由有代入得，所以 注意 不能由且得出如不能由且得出（9）若为素数，且，则或证明 若不然，则且，由为素数得，由互素的性质（6）得，再由为素数得，与矛盾注意 没有为素数，不能由推出或如，但且定义6 对于整数，且，若，则称关于模同余，记作；若，则称关于模不同余，记作 定理9（同余的性质）设为整数，（1）若且，则；证明 由且，有 ，得（2）若且，则且证明 由且，有 ， 对直接相加 ，有，得 .对分别乘以后相加，有，得 （3）若，则对任意的正整数有且.（4）若，且对非零整数有，则证明 由、，有 ，又，有均为整数，且，得 定理10 设为整数，为正整数，（1）若，则（2）若，则（3）若，则定义7 设为正整数，为大于2的正整数, 是小于的非负整数，且若 ，则称数为的进制表示定理11 给定整数，对任意的正整数，都有唯一的进制表示如，（10进制）（进制）定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的 ，其中为素数，为正整数 （分解唯一性）证明1 先证明，正整数可分解为素数的乘积