数学竞赛中的数论问题

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

引言

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

什么是正整数呢?人们借助于“集合”和“后继”关系给正整数(当时也即自然数)作过本质的描述,正整数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, ?a1,a2,,an?.

,an?中的ai没有顺序,最大公约数也称最大公因数.

,an???a1,a2,,an?.

简单性质:?a1,a2,一个功能:可以把对整数的研究转化为对非负整数的研究. 定义3 (最小公倍数)非零整数a1,a2,,an的最小公倍数是能被其中每一个

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

简单性质:如果k是正整数a,b的公倍数,则存在正整数m使k?m证明 若不然,有k?m?a,b??r(0?r??a,b?),由k,?a,b?

?a,b?都是a,b的公倍数得r?a,b?.

也是a,b的公倍数,但0?r??a,b?,与?a,b?的最小性矛盾.故k?m定义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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4