1、1数学竞赛中的数论问题罗增儒引言数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数 1，2，3，是这样一个集合 ：N（1）有一个最小的数 1 （2）每一个数 的后面都有且只有一个后继数 ；除 1 之外，每一个数的都是且只a/a是一个数的后继数这个结构很像数学归纳法，事实上，有这样的归纳公理：（3）对 的子集 ，若 ，且当 时，有后继数 ，则 NM1M/aMN就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧
2、还没有成熟到解决它的程度比如，哥德巴赫猜想：1742 年 6 月 7 日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由 4 开始，都可以表示为两个素数和的形式，任何奇数，由 7 开始，都可以表示为三个素数的和后者是前者的推论，也可独立证明（已解决） “表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称 1+1欧拉认为这是对的，但证不出来1900 年希尔伯特将其归入 23 个问题中的第 8 个问题1966 年陈景润证得：一个素数+素数 素数（1+2） ，至今仍无人超越陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数
3、学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（UDudley数论基础前言） 下面，是一个有趣的故事当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有 个正
4、整数，这些正整数小于或等1n于 ，那么你一定有一对整数是互素的，你知道这是什么原因吗？2n不到 12 岁的波萨只用了 1 分半钟，就给出了问题的解答他将 1 分成（1，2） ，n（3，4） ， （ ）共 个抽屉，手头的 个正整数一定有两个属于同一抽屉，,2n这两个数是相邻的正整数，必定互素通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理” 重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四2大支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）高中竞赛加试四道题正好是四大模块各一题，分别是
5、几何题、代数题、数论题、组合题，一试中也会有数论题数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被 2、3、4、5、8、9、11 等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程 在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数 ，费马小定理，格点及其性质，无穷递降法，x欧拉
6、定理 ，孙子定理 根据已出现的试题统计，中学数学竞赛中的数论问题的主要有 8 个重点类型：（1）奇数与偶数（奇偶分析法、01 法） ；（2）约数与倍数、素数与合数；（3）平方数；（4）整除；（5）同余；（6）不定方程；（7）数论函数、 高斯函数、 欧拉函数；xn（8）进位制（十进制、二进制） 下面，我们首先介绍数论题的基本内容（10 个定义、18 条定理） ，然后，对数学竞赛中的数论问题作分类讲解第一讲 数论题的基本内容3中学数学竞赛中的数论问题涉及的数论内容主要有 10 个定义、18 条定理首先约定，本文中的字母均表示整数定义 1 （带余除法）给定整数 如果有整数 满足,0,ab,0qrb，
7、aqbr则 和 分别称为 除以 的商和余数特别的， 时，则称 被 整除，记作 ，qr raa或者说 是 的倍数，而 是 的约数 （ 的存在性由定理 1 证明）a,q定义 2 （最大公约数）设整数 中至少有一个不等于零，这 个数的最大12na n公约数是能整除其中每一个整数的最大正整数，记作 12,na中的 没有顺序，最大公约数也称最大公因数12,na ia简单性质： 1212,nna 一个功能：可以把对整数的研究转化为对非负整数的研究定义 3 （最小公倍数）非零整数 的最小公倍数是能被其中每一个12,n所整除的最小正整数，记作 1iana简单性质：如果 是正整数 的公倍数，则存在正整数 使k,
8、bm,kab证明 若不然，有 （ ） ，由 都是 的公倍数得mr0,b,也是 的公倍数，但 ，与 的最小性矛盾故 r,ab0,a ,k定义 4 如果整数 满足 ，则称 与 是互素的（也称互质） ,b1a定义 5 大于 1 且除 1 及其自身外没有别的正整数因子的正整数，称为素数（也称质数） 其余大于 1 的正整数称为合数；数 1 既不是素数也不是合数定理 1 若 是两个整数， ，则存在两个实数 ，使 ，,a0,qr0abr并且 是唯一性,qr证明 1 先证存在性作序列 ,3.2,3bb 则 必在上述序列的某两项之间，从而存在一个整数 ，使a q，1qa即 ，0b4取 ， ，raqb0r得 ，即
9、存在两个实数 ，使 ,r0aqbr再证唯一性假设不唯一，则同时存在 与 ，使1,2,qr，110aqbr，22b相减 ，11r，2q，10但 为整数，故 ，得 ，从而 1220q12q12r注：如果取消 ，当 或 ，不保证唯一rbrb经典方法：紧扣定义，构造法证存在性，反证法证唯一性证明 2 只证存在性，用高斯记号，由，01ab有 ，记 ，故存在 使arb,0aaqrbrb0rb证明 3 只证存在性，作集合|,0MaxZax这是一个有下界的非空整数集，其中必有最小的，设 时，有最小值xqr0qbr再证 ，若不然， ，记 ，有r1rb1arqr51rabqM即 有 比 更小，这与 为最小值矛盾M
10、r故存在两个实数 ，使 ,0rb定理 2 设 是三个不全为 0 的整数，满足 ，其中 也为整数，则abcaqc,abc证明 设 的公约数 ，A, 的公约数 Bbc任取 ，|dabqdBA任取 ，|bBdcaqc得 A有 中元素的最大值 中元素的最大值，即,abc注：这是辗转相除法求最大公约数的理论基础经典方法：要证明 ，只需证 且 ABBA定理 3 对任意的正整数 ，有,ab,证明 因为 是 的公倍数，所以 的最小公倍数也是 的约数，存在 使b,abq，,aq有 且 为整数，ba故 是 的约数同理 是 的约数，即 是 的公约数下面证明， 是 的最大公qaqq,abq,ab约数若不然， 有,a
11、,b6设 ，可见 是 的倍数，同样 ， 是 的倍,abkka,abkkb数，即 是 的公倍数，则存在正整数 使 ，有m,，,abab得 ,q与矛盾，所以， ，得证 ab,ab注 也可以由 ，得 ，与 矛盾,1,kqmabab,ab,qab两步 可以交换吗？,abqk定理 4 是两个不同时为 0 的整数，若 是形如 （ 是任意整0axbyaxby,数）的数中的最小正数，则（1） | ；0axby（2） ,证明 （1）由带余除法有， ，0axbyqr0axby得 ，0rxy知 也是形如 的非负数，但 是形如 的数中的最小正数，故 ，rxyabxy0r即| 0ab（2）由（1）有| ，0xy10aA
12、| ，abb得 是 的公约数另一方面， 的每一个公约数都可以整除 ，所以0xy, , 0axby是 的最大公约数， 0axy7推论 若 ，则存在整数 ，使 （很有用）,1ab,st1abt定理 5 互素的简单性质： （1） ,（2） 1n（3） ,（4）若 是一个素数， 是任意一个整数，且 不能被 整除，则 paap,1ap证明 因为 ，所以，素数 的约数只有两种可能：,|p但 不能被 整除， ，得 ,1,a,推论 若 是一个素数， 是任意一个整数，则 或 pa,1ap（5）若 ，则存在整数 ，使 （定理 4 推论）,b,stbt（6）若 ，则 1,ac1c证明 由 知存在整数 ，使 ,sta
13、t有 ，csbt得 ,1a（7）若 ，则 ， ， ,a,1ab,1ab证明 ，,b，,1a由（6） ,（8）若 ，则 ，其中 为正整数b,mnab,n证明 据（6） ，由 可得 1,1同样，由 可得 ,mmn定理 6 设 是大于 1 的整数，则 的除 1 之外的最小的正约数 必是素数，且当aaq是合数时， aq8证明 用反证法，假设 不是素数，则存在正整数数 ， ，使 ，但q1q11|q，故有 ，这与 是 的除 1 之外的最小正约数矛盾，故 是素数|qa1|a当 是合数时，设 ，则 也是 的一个正约数，由 的最小性得 ，从a1a而 ，开方得 21q定理 7 素数有无穷多个，2 是唯一的偶素数证
14、明 假设素数只有有限多个，记为 ，作一个新数12,np12npA若 为素数，则与素数只有 个 矛盾12,n若 为合数，则必有 ，使 ，从而 ，又与 矛盾ip |ip|1iip综上所述，素数不能只有有限多个，所以素数有无穷多个2 是素数，而大于 2 的偶数都是合数，所以 2 是唯一的偶素数注：这个证明中，包含着数学归纳法的早期因素：若假设有 个素数，便有 个素n1n数 （构造法、反证法）秒定理 8（整除的性质）整数 通常指非零整数,abc（1） ， ；当 时， ， a|0|0a（2）若 ， ，则 ;若 ， ，则 ;若 ，且bb0ab，则 ,证明 由 ， ，有 ，得 a0aqq逆反命题成立“若 ，
15、 ，则 ”;b0由 且 得 ，又 ，得 bbab（3）若 ，且 ，则 acd|,|eac|ed（4）若 ， ，则 证明 （定义法）由 ， ，有cb，12,qa得 ，c9即 ca（5）若 ，则 b（6）若 ， ，则对任意整数 ，有 c,mncanb证明 （定义法）由 ， ，有ca，12,qb得 ，1mnqc即 ca（7）若 ，且 ，则 ,bca证明 由 知存在整数 ，使 ，有1,st1bt，acstc因为 ， ，所以 整除等式的左边，进而整除等式的右边，即 ba ac注意 不能由 且 得出 如 ，但 且 c|c649|6|9（8）若 ，且 ，则 ,1a,b证明 由 知存在整数 ，使 ，有bst1
16、at，cst又由 有 代入得,a12,aqc，2bst所以 c注意 不能由 且 得出 如不能由 且 得出 acab6301|60|3（9）若 为素数，且 ，则 或 c证明 若不然，则 且 ，由 为素数得 ，由互素的性质| ,1abc（6）得 ，再由 为素数得 ，与 矛盾,1abca|bc注意 没有 为素数，不能由 推出 或 如 ，但 且 649|6|10定义 6 对于整数 ，且 ，若 ，则称 关于模 同余，记作,abc0()cab,c；若 ，则称 关于模 不同余，记作 (mod)abc|, (mod)定理 9（同余的性质）设 为整数，cdm,（1）若 且 ，则 ；()(o)b(od)ac证明 由 且 ，有oac，12,mq，c得 (od)a（2）若 且 ，则 且bm(od)c(mod)acb()c证明 由 且 ，有oda()c， 12,bmq对直接相加 ，有，12acdq得 .(o)b对分别乘以 后相加，有,c，12adcbdmcqb得 (mo)cb（3）若 ，则对任意的正整数 有 且 .n(od)na(mod)anbn（4）若 ，且对非零整数 有 ，则 (od)abk(,)bmkk证明 由 、 ，有m，abq
