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

精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -数学竞赛中的数论问题罗增儒引言数论的熟悉： 数论是关于数的学问，主要讨论整数，重点对象是正整数，对中同学可以说，数论是讨论正整数的一个数学分支什么是正整数了？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1， 2， 3，, 是这样一个集合N ：可编辑资料 - - - 欢迎下载精品名师归纳总结（ 1）有一个最小的数1（ 2）每一个数a 的后面都有且只有一个后继数a / 。除 1 之外，每一个数的都是且只是可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结一个数的后继数这个结构很像数学归纳法，事实上，有这样的归纳公理：（ 3）对 N 的子集 M ，如 1M ，且当 aM 时，有后继数a /M ，就 MN可编辑资料 - - - 欢迎下载精品名师归纳总结就是这么一个简洁的数集，里面却有无穷无尽的秘密，有的秘密甚至使得人们怀疑：人类的聪慧仍没有成熟到解决它的程度比如，哥德巴赫猜想：1742 年 6 月 7 日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数， 由 4 开头， 都可以表示为两个素数和的形式，任何奇数， 由 7 开头，都可以表示为三个素数的和后者是前者的推论，也可独立证明（已解决）“表示为两个素数和的形式”就是闻名的哥德巴赫猜想，简称1+1欧拉认为这是对的，但证不出来1900 年希尔伯特将其归入23 个问题中的第8 个问题1966 年陈景润证得：一个素数+素数素数（ 1+2），至今仍无人超越陈景润的数学老师沈元很重视利用名人、名言、名事去勉励同学， 他曾多次在开讲时，说过这样的话 : “自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想就是皇冠上的明珠 , ”陈景润就是由此而受到了启示和勉励，绽开了艰苦卓绝的终生奋斗和辉煌辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥数论题涉及的学问不是许多，但用不多的学问来解决问题往往就需要较强的才能和精明多的技巧，有人说：用以发觉数学人才，在初等数学中再也没有比数论教材更好的课程了任何同学如能把当今一本数论教材中的练习做出，就应当受到勉励，劝他（她）将来去从事数学方面的工作（U Dudley 数论基础前言） 下面，是一个好玩的故事当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利， 1948）的小男孩很聪慧，就问可编辑资料 - - - 欢迎下载精品名师归纳总结了他一个问题加以考察（1959 ）：假如你手头上有n1 个正整数， 这些正整数小于或等于2 n ，可编辑资料 - - - 欢迎下载精品名师归纳总结那么你肯定有一对整数是互素的，你知道这是什么缘由吗？不到 12 岁的波萨只用了1 分半钟， 就给出了问题的解答他将 1 2n 分成（ 1，2），（ 3，可编辑资料 - - - 欢迎下载精品名师归纳总结4），, ， （ 2n1,2 n ）共 n 个抽屉，手头的n1 个正整数肯定有两个属于同一抽屉，这两可编辑资料 - - - 欢迎下载精品名师归纳总结个数是相邻的正整数，必定互素通过这个问题，厄尔多斯认定波萨是个难得的英才，就细心加以培育，不到两年，14岁的波萨就发表了图论中“波萨定理”重视数学才能的数学竞赛，已经广泛采纳数论题目，是数学竞赛四大支柱之一，四大可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题 数论受到数学竞赛的青睐可能仍有一个技术上的缘由，就是它能便利的供应从学校到高校各个层面的、新奇而好玩的题目数论题的主要类型：在中学竞赛大纲中，数论的内容列有：十进制整数及表示方法。整除性，被 2、3、4、5、8、9、11 等数整除的判定。素数和合数，最大公约数与最小公倍数。奇数和偶数，奇偶性分析。带余除法和利用余数分类。完全平方数。因数分解的表示法，约数个数的运算。简洁的一次不定方程在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数 x ，费马小定理，格点及其性质，无穷递降法，欧拉定理，孙子定理依据已显现的试题统计，中学数学竞赛中的数论问题的主要有8 个重点类型：（ 1）奇数与偶数（奇偶分析法、01 法）。（ 2）约数与倍数、素数与合数。（ 3）平方数。（ 4）整除。（ 5）同余。（ 6）不定方程。（ 7）数论函数、x 高斯函数、n 欧拉函数。（ 8）进位制（十进制、二进制）下面，我们第一介绍数论题的基本内容（10 个定义、 18 条定理），然后，对数学竞赛中的数论问题作分类讲解可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料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 的存在性由定理1 证明）可编辑资料 - - - 欢迎下载精品名师归纳总结定义2（最大公约数）设整数a1 , a2 , an 中至少有一个不等于零，这n 个数的最大可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结公约数是能整除其中每一个整数的最大正整数，记作a1, a2 , an可编辑资料 - - - 欢迎下载精品名师归纳总结a1,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 （ 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 必在上述序列的某两项之间，从而存在一个整数q ，使qbaq1 b ，可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料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 ，不保证唯独经典方法 ：紧扣定义，构造法证存在性，反证法证唯独性 证明 2只证存在性，用高斯记号，由0aa1 ， bba有0abb ，b可编辑资料 - - - 欢迎下载精品名师归纳总结记 raba，故存在 qa,raba,0rb 使可编辑资料 - - - 欢迎下载精品名师归纳总结bbbaqbr0rb证明 3只证存在性，作集合Mabx | xZ , abx0这是一个有下界的非空整数集，其中必有最小的，设xq 时，有最小值rr0aqbr 可编辑资料 - - - 欢迎下载精品名师归纳总结再证 rb ，如不然，rb ，记rbr1 ，有可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -aqbrqbbr1bq1r1r1abq1M即 M 有 r1 比 r 更小，这与r 为最小值冲突可编辑资料 - - - 欢迎下载精品名师归纳总结故存在两个实数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 的最小公倍数也是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 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料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 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,b可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结推论如a, b1，就存在整数s,t ，使asbt1 （很有用）可编辑资料 - - - 欢迎下载精品名师归纳总结定理 5互素的简洁性质：（ 1） 1,a1可编辑资料 - - - 欢迎下载精品名师归纳总结（ 2）n, n11 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结（ 3）2n1,2 n11可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结（ 4）如 p 是一个素数，a 是任意一个整数，且a 不能被p 整除，就a, p1可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结证明由于a, p| p ，所以， 素数 p 的约数只有两种可能：a, p1, a,pp 但可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结a 不能被p 整除，a, pp ，得a, p1 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结推论如 p 是一个素数，a 是任意一个整数，就a, p1 或a, pp 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结（ 5）如a, b1，就存在整数s, t ，使asbt1 （定理 4 推论）可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结（ 6）如a,b1, a, c1 ，就a, bc1可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结证明由a, b1知存在整数s,t ，使asbt1 可编辑资料 - - - 欢迎下载精品名师归纳总结有a csbctc ，得a,bca, c1可编辑资料 - - - 欢迎下载精品名师归纳总结（ 7）如a, b1，就ab, a1，ab,b1，ab, ab1 可编辑资料 - - - 欢迎下载精品名师归纳总结证明ab, ab, ab, a1 ，ab,ba,b1 ，可编辑资料 - - - 欢迎下载精品名师归纳总结由（ 6）ab, ab1可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结（ 8）如a, b1，就am ,b n1 ，其中m,n 为正整数可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结证明据（ 6），由a, b1可得am , b1 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结同样，由a m ,b1 可得a m ,b n1 可编辑资料 - - - 欢迎下载精品名师归纳总结定理 6设 a 是大于 1 的整数， 就 a 的除 1 之外的最小的正约数q 必是素数， 且当 a 是合数时， qa 可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结证明用反证法， 假设 q 不是素数， 就存在正整数数q1 ，1q1q ，使 q1 | q ，但q | a ，可编辑资料 - - - 欢迎下载精品名师归纳总结故有 q1 | a ，这与 q 是 a 的除 1 之外的最小正约数冲突，故q 是素数可编辑资料 - - - 欢迎下载精品名师归纳总结当 a 是合数时，设aa1q ，就a1 也是 a 的一个正约数，由q 的最小性得qa1 ，从而可编辑资料 - - - 欢迎下载精品名师归纳总结2qa1qa ，开方得 qa 定理 7素数有无穷多个，2 是唯独的偶素数可编辑资料 - - - 欢迎下载精品名师归纳总结证明假设素数只有有限多个，记为p1,p2 , pn ，作一个新数可编辑资料 - - - 欢迎下载精品名师归纳总结pp1p2pn11如 p 为素数，就与素数只有n 个 p1 , p2 , pn 冲突可编辑资料 - - - 欢迎下载精品名师归纳总结如 p 为合数，就必有pip1 , p2 , pn，使 pi| p ，从而pi |1 ，又与 pi1冲突可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结综上所述，素数不能只有有限多个，所以素数有无穷多个2 是素数，而大于2 的偶数都是合数，所以2 是唯独的偶素数注：这个证明中，包含着数学归纳法的早期因素：如假设有n 个素数，便有n数（构造法、反证法）秒1 个素可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结定理 8（整除的性质）整数a,b, c 通常指非零整数可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结（ 1） 1 a ，1| a 。当 a0 时，a | a ，a | 0 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结（ 2）如 b a ， a0 ，就 ba ; 如 b a ， ba ，就 a0 ; 如 ab0 ，且 b a,a b，可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结就 ab 证明由 b a ， a0 ，有 abq ，得 ab qb 可编辑资料 - - - 欢迎下载精品名师归纳总结逆反命题成立“如b a ， ba ，就 a0 ” ;由 ba 且 ba 得 ab ，又 ab0 ，得 ab 可编辑资料 - - - 欢迎下载精品名师归纳总结（ 3）如 abcd ，且e | a, e | b, e | c ，就e | d 可编辑资料 - - - 欢迎下载精品名师归纳总结（ 4）如 c b ， b a ，就 c a 证明（定义法）由c b ， b a ，有bq1c,aq2b ，得aq1q2c ，可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 46 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -即c a （ 5）如 c a ，就 bc ab 可编辑资料 - - - 欢迎下载精品名师归纳总结（ 6）如 c a ， c b ，就对任意整数m, n ，有 c manb 可编辑资料 - - - 欢迎下载精品名师归纳总结证明（定义法）由c a ， c b ，有aq1c,bq2c ，得manbmq1nq2c ，即c manb 可编辑资料 - - - 欢迎下载精品名师归纳总结（ 7）如a, b1，且 a bc ，就 a c 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结证明由a, b1知存在整数s,t ，使asbt1 ，有可编辑资料 - - - 欢迎下载精品名师归纳总结a csbc tc ，由于 a a ， a bc ，所以 a 整除等式的左边，进而整除等式的右边，即a c 留意不能由 a bc 且 a | b 得出 a c 如 6 49 ，但 6 | 4 且 6 | 9 可编辑资料 - - - 欢迎下载精品名师归纳总结（ 8）如a, b1，且a c ,b c ，就 ab c 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结证明由a, b1知存在整数s,t ，使asbt1 ，有可编辑资料 - - - 欢迎下载精品名师归纳总结acsbctc ，又由 a c ,b c 有 caq1 ,cbq2 代入得ab q2 sab q1tc ，所以 ab c 留意不能由 a c 且 b c 得出 ab c 如不能由6 30 且 10 | 30 得出 60 | 30