2021年2021年数学竞赛中的数论问题.docx

《2021年2021年数学竞赛中的数论问题.docx》由会员分享，可在线阅读，更多相关《2021年2021年数学竞赛中的数论问题.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品word 可编辑资料 - - - - - - - - - - - - -数学竞赛中的数论问题罗增儒引言数论的熟悉： 数论为关于数的学问，主要讨论整数，重点对象为正整数，对中同学可以说，数论为讨论正整数的一个数学分支什么为正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1， 2， 3，为这样一个集合N ：（ 1）有一个最小的数1（ 2）每一个数a 的后面都有且只有一个后继数a / ；除 1 之外，每一个数的都为且只为一个数的后继数这个结构很像数学归纳法，事实上，有这样的归纳公理：（ 3）对 N 的子集 M ，如 1M ，且当 aM 时，有后继数a/M

2、 ，就 MN就为这么一个简洁的数集，里面却有无穷无尽的秘密，有的秘密甚至使得人们怀疑：人类的聪慧仍没有成熟到解决它的程度比如，哥德巴赫猜想：1742 年 6 月 7 日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数， 由 4 开头， 都可以表示为两个素数和的形式，任何奇数， 由 7 开头，都可以表示为三个素数的和后者为前者的推论，也可独立证明（已解决）“表示为两个素数和的形式”就为闻名的哥德巴赫猜想，简称1+1欧拉认为这为对的，但证不出来1900 年希尔伯特将其归入23 个问题中的第8 个问题1966 年陈景润证得：一个素数+素数素数（ 1+2），至今仍无人超越陈景润的数学老师沈

3、元很重视利用名人.名言.名事去勉励同学， 他曾多次在开讲时，说过这样的话 : “自然科学的皇后为数学，数学的皇冠为数论，哥德巴赫猜想就为皇冠上的明珠” 陈景润就为由此而受到了启示和勉励，绽开了艰苦卓绝的终生奋斗和辉煌辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥数论题涉及的学问不为许多，但用不多的学问来解决问题往往就需要较强的才能和精明多的技巧，有人说：用以发觉数学人才，在初等数学中再也没有比数论教材更好的课程了任何同学如能把当今一本数论教材中的练习做出，就应当受到勉励，劝他（她）将来去从事数学方面的工作（U Dudley 数论基础前言） 下面，为一个好玩的故事当代最高产的数学家厄尔多斯听说

4、一个叫波萨（匈牙利， 1948）的小男孩很聪慧，就问了他一个问题加以考察（1959 ）：假如你手头上有n1 个正整数， 这些正整数小于或等于2 n ，那么你肯定有一对整数为互素的，你知道这为什么缘由吗？不到 12 岁的波萨只用了1 分半钟， 就给出了问题的解答他将 1 2n 分成（ 1，2），（ 3，4），（ 2n1、2 n ）共 n 个抽屉，手头的n1 个正整数肯定有两个属于同一抽屉，这两个数为相邻的正整数，必定互素通过这个问题，厄尔多斯认定波萨为个难得的英才，就细心加以培育，不到两年，14岁的波萨就发表了图论中“波萨定理”重视数学才能的数学竞赛，已经广泛采纳数论题目，为数学竞赛四大支柱之一

5、，四大1第 1 页，共 6 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -支柱为：代数，几何，初等数论，组合初步（俗称代数题.几何题.算术题和智力题）高中竞赛加试四道题正好为四大模块各一题，分别为几何题.代数题.数论题.组合题，一试中也会有数论题 数论受到数学竞赛的青睐可能仍有一个技术上的缘由，就为它能便利地供应从学校到高校各个层面的.新奇而好玩的题目数论题的主要类型：在中学竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被 2.3.4.5.8.9.11 等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和

6、偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的运算；简洁的一次不定方程在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数 x ，费马小定理，格点及其性质，无穷递降法，欧拉定理，孙子定理依据已显现的试题统计，中学数学竞赛中的数论问题的主要有8 个重点类型：（ 1）奇数与偶数（奇偶分析法.01 法）；（ 2）约数与倍数.素数与合数；（ 3）平方数；（ 4）整除；（ 5）同余；（ 6）不定方程；（ 7）数论函数.x 高斯函数.n 欧拉函数；（ 8）进位制（十进制.二进制）下面，我们第一介绍数论题的基本内

7、容（10 个定义. 18 条定理），然后，对数学竞赛中的数论问题作分类讲解2第 2 页，共 6 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -第一讲数论题的基本内容中学数学竞赛中的数论问题涉及的数论内容主要有10 个定义. 18 条定理第一商定，本文中的字母均表示整数定义 1 （带余除法）给定整数a、b、b0、 假如有整数q、 r0rb满意aqbr ，就 q 和 r 分别称为 a 除以 b 的商和余数特殊的，r0 时，就称 a 被 b 整除，记作 b a，或者说 a 为 b 的倍数，而b 为 a 的约数（ q、 r 的存在

8、性由定理1 证明）定义2（最大公约数）设整数a1 、 a2 、 an 中至少有一个不等于零，这n 个数的最大公约数为能整除其中每一个整数的最大正整数，记作a1、 a2 、 ana1、a2 、 an中的 ai 没有次序，最大公约数也称最大公因数简洁性质：a1、 a2 、 ana1 、 a2、 an一个功能：可以把对整数的讨论转化为对非负整数的讨论定义3（最小公倍数）非零整数a1 、 a2 、 an的最小公倍数为能被其中每一个ai1in 所整除的最小正整数，记作a1、 a2 、 an简洁性质： 假如 k 为正整数a、 b 的公倍数，就存在正整数m 使 km a、b证明如不然， 有 km a、 br

9、 （ 0ra、 b ），由 k、a、b 都为a、 b 的公倍数得r也为 a、 b 的公倍数，但0ra、 b ，与a、 b 的最小性冲突故km a、 b 定义 4假如整数a、 b满意a、b1，就称 a 与 b 为互素的（也称互质） 定义 5大于 1 且除 1 及其自身外没有别的正整数因子的正整数，称为素数（也称质数）其余大于1 的正整数称为合数；数1 既不为素数也不为合数定理 1 如 a 、b 为两个整数，b并且 q、 r 为唯独性证明 1先证存在性作序列0 ，就存在两个实数q 、 r ，使aqbr0rb，、3b.2b、b、0、 b、2 b、3b、就 a 必在上述序列的某两项之间，从而存在一个整

10、数q ，使qbaq1 b ，3第 3 页，共 6 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -即0aqbb ，取得raaqbqb ，r ，0rb ，即存在两个实数q 、 r ，使aqbr0rb 再证唯独性假设不唯独，就同时存在q1 、r1 与 q1、 r2 ，使aq1br10r1b ，aq2br20r2b ，相减q1q2br2r1 ，q1q2 br2r1b ，0q1q21，但 q1q2 为整数，故q1q20 ，得 q1q2 ，从而 r1r2 注：假如取消0rb ，当 r0 或 rb ，不保证唯独经典方法 ：紧扣定义，构造

11、法证存在性，反证法证唯独性 证明 2只证存在性，用高斯记号，由0aa1 ， bb有0abab ， b记 raba，故存在 qa、raba、0rb 使bbbaqbr0rb证明 3只证存在性，作集合Mabx | xZ 、 abx0这为一个有下界的非空整数集，其中必有最小的，设xq 时，有最小值rr0aqbr 再证 rb ，如不然，rb ，记rbr1 ，有4第 4 页，共 6 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -aqbrqbbr1bq1r1r1abq1M即 M 有 r1 比 r 更小，这与r 为最小值冲突故存在两个实数

12、q 、 r ，使aqbr0rb 定理2设a、b、c 为三个不全为0 的整数，满意aqbc ，其中 q 也为整数，就a、 bb、c证明设 A a 、b 的公约数， B b、 c 的公约数dBAB ，dABA ，d | ad | bd | cd | babqd | b d | cd | b d | abqc任取 dA任取 dB得AB 有 A 中元素的最大值B 中元素的最大值，即a、bb、 c注： 这为辗转相除法求最大公约数的理论基础经典方法： 要证明 AB ，只需证AB 且 BA 定理 3对任意的正整数a、b ，有a、 ba、bab 证明由于 ab 为a、 b 的公倍数，所以a、 b 的最小公倍数

13、也为ab 的约数，存在q 使abq a、b ，有aqa、 b且ba、b b为整数，故 q 为 a 的约数同理q 为 b 的约数，即q 为 a 、b 的公约数下面证明，q 为 a、 b 的最大公约数如不然，qa、b有abq a、 ba、 ba、b 5第 5 页，共 6 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -设 kabab，可见 k 为 a 的倍数，同样kabba， k 为 b 的倍a、 ba、ba、ba、b数，即 k 为 a 、b 的公倍数，就存在正整数m 使 km a、b ， 有abm a、ba、b，a、b得abq

14、 a、ba、ba、 b与冲突，所以，qa、b，得证a、ba、bab 注也可以由 1m，得 qa、b，与qa、 b冲突abka、bqa、babqa、 b两步 abq a、b 、 aba、b k 可以交换吗？定理 4a 、 b 为两个不同时为0 的整数，如 ax0by0 为形如 axby（x、 y 为任意整数）的数中的最小正数，就（ 1） ax0by0 | axby ；（ 2） ax0by0a、 b 证明（ 1）由带余除法有axbyax0by0qr ，0rax0by0 ，得raxqx0xbyqy0ax0by0 ，知 r 也为形如 axby 的非负数，但ax0by0 为形如 axby 的数中的最小正数，故r0 ，即ax0by0 | axby （ 2）由（ 1）有ax0by0 | a 1b 0a ，ax0by0 | a 0b 1b ，得 ax0by0 为a、 b 的公约数另一方面，a 、 b 的每一个公约数都可以整除ax0by0 ，所以ax0by0 为a、 b 的最大公约数，ax0by0a、b6第 6 页，共 6 页 - - - - - - - - - -