数学竞赛中的数论问题

数学竞赛中的数论问题 罗增儒

引言

数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支．

什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，?是这样一个集合N?：

（1）有一个最小的数1．

（2）每一个数a的后面都有且只有一个后继数a；除1之外，每一个数的都是且只是一个数的后继数．

这个结构很像数学归纳法，事实上，有这样的归纳公理：

（3）对N?的子集M，若1?M，且当a?M时，有后继数a?M，则M?N?． 就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度．比如，哥德巴赫猜想：

1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和．后者是前者的推论，也可独立证明（已解决）．“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1．

欧拉认为这是对的，但证不出来．

1900年希尔伯特将其归入23个问题中的第8个问题． 1966年陈景润证得：一个素数+素数?素数（1+2），至今仍无人超越． ●陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠．??”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥．

●数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了．任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（U．Dudley《数论基础》前言）．下面，是一个有趣的故事．

当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有n?1个正整数，这些正整数小于或等于2n，那么你一定有一对整数是互素的，你知道这是什么原因吗？

不到12岁的波萨只用了1分半钟，就给出了问题的解答．他将1～2n分成（1，2），（3，4），?，（2n?1,2n）共n个抽屉，手头的n?1个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素．

通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”．

●重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大

// 1

支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）．高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题．数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目．

数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程．

在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x]，费马小定理，格点及其性质，无穷递降法，欧拉定理?，孙子定理?．

根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型： （1）奇数与偶数（奇偶分析法、01法）； （2）约数与倍数、素数与合数； （3）平方数； （4）整除； （5）同余； （6）不定方程；

（7）数论函数、?x?高斯函数、??n?欧拉函数；

（8）进位制（十进制、二进制）．

下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解．

2

第一讲 数论题的基本内容

中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理． 首先约定，本文中的字母均表示整数．

定义1 （带余除法）给定整数a,b,b?0,如果有整数q,r0?r?b满足 a?qb?r，

则q和r分别称为a除以b的商和余数．特别的，r?0时，则称a被b整除，记作ba，或者说a是b的倍数，而b是a的约数．（q,r的存在性由定理1证明）

定义2 （最大公约数）设整数a1,a2,?,an中至少有一个不等于零，这n个数的最大公约数是能整除其中每一个整数的最大正整数，记作?a1,a2,?,an?．

?a1,a2,?,an?中的ai没有顺序，最大公约数也称最大公因数． 简单性质：?a1,a2,?,an??a1,a2,?,an．

一个功能：可以把对整数的研究转化为对非负整数的研究．

定义3 （最小公倍数）非零整数a1,a2,?,an的最小公倍数是能被其中每一个

????ai?1?i?n?所整除的最小正整数，记作?a1,a2,?,an?．

简单性质：如果k是正整数a,b的公倍数，则存在正整数m使k?m?a,b?

证明 若不然，有k?m?a,b??r（0?r??a,b?），由k,?a,b?都是a,b的公倍数得r也是a,b的公倍数，但0?r??a,b?，与?a,b?的最小性矛盾．故k?m?a,b?．

定义4 如果整数a,b 满足?a,b??1，则称a与b是互素的（也称互质）．

定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）．其余大于1的正整数称为合数；数1既不是素数也不是合数．

定理1 若a,b是两个整数，b?0，则存在两个实数q,r，使a?qb?r?0?r?b?，并且q,r是唯一性．

证明1 先证存在性．作序列

?,?3b.?2b,?b,0,b,2b,3b,?

则a必在上述序列的某两项之间，从而存在一个整数q，使

qb?a??q?1?b，

3

即 0?a?qb?b， 取 r?a?qb， 0?r?b， 得 a?qb?r，

即存在两个实数q,r，使a?qb?r?0?r?b?． 再证唯一性．假设不唯一，则同时存在q1,r1与q1,r2，使 a?q1b?r1?0?r1?b?， a?q2b?r2?0?r2?b?， 相减 ?q1?q2?b?r2?r1， q1?q2b?r2?r1?b， 0?q1?q2?1，

但q1?q2为整数，故q1?q2?0，得q1?q2，从而r1?r2．

注：如果取消0?r?b，当r?0或r?b，不保证唯一． 经典方法：紧扣定义，构造法证存在性，反证法证唯一性． 证明2 只证存在性，用高斯记号，由 0?ab???a??b???1， 有 0?a?b??a??b???b，

记r?a?b??a??，故存在q???a??a??b??b??,r?a?b??b??,0?r?b使

a?qb?r?0?r?b?．

证明3 只证存在性，作集合

M??a?bx|x?Z,a?bx?0?

这是一个有下界的非空整数集，其中必有最小的，设x?q时，有最小值r?r?0? a?qb?r．

再证r?b，若不然，r?b，记r?b?r1，有

4

a?qb?r?qb??b?r1??b?q?1??r1

r1?a?b?q?1??M

即M有r1比r更小，这与r为最小值矛盾． 故存在两个实数q,r，使a?qb?r?0?r?b?．

定理2 设a,b,c是三个不全为0的整数，满足a?qb?c，其中q也为整数，则

?a,b???b,c?．

证明 设A?｛a,b的公约数｝， B?｛b,c的公约数｝．

任取d?A???d|a?d|c?a?bq???d?B?A?B， d|bd|b???d|b?d|b???d?A?B?A， 任取d?B??d|cd|a?bq?c??得 A?B．

有A中元素的最大值?B中元素的最大值，即

?a,b???b,c?．

注：这是辗转相除法求最大公约数的理论基础．

经典方法：要证明A?B，只需证A?B且B?A． 定理3 对任意的正整数a,b，有 ?a,b???a,b??ab．

证明 因为ab是a,b的公倍数，所以a,b的最小公倍数也是ab的约数，存在q使 ab?q?a,b?，

有

a,b??a,b??a?q且为整数，

bb故q是a的约数．同理q是b的约数，即q是a,b的公约数．下面证明，q是a,b的最大公约数．若不然，q??a,b?．有

ab?q?a,b???a,b??a,b?． ①

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学竞赛中的数论问题在线全文阅读。