上海中学竞赛课程数学3.docx

第一讲数论基础

知识精讲

本讲的目的是通过介绍整数的概念与性质,建立最大公约数理论,导出算术基本定理.期望能给学生数论知识架构上的一个清晰脉络,做好逻辑体系形成的基础性工作.

皮亚诺(Peano)关于自然数的数条公理展示出的算术系统不是中学生必须了解的,但其中的一条公设应该知道,即归纳公理.

归纳公理设S是N*的一个子集,满足下面的两个条件

(i)1∈S

(ii)如果n∈S,那么

则S=

它是我们常用的数学归纳法的基础,两者实质上是一回事,这也是不去纠结数学归纳法是定理还是原(公)理的原因.

数学归纳法设P(n)是关于正整数n的一个命题

(i)当n=1时,命题P(1)

(ii)由命题P(n)成立可推出

那么,对任意n∈N

第二数学归纳法设P(n)是关于正整数n的一个命题

(i)当n=1时,命题P(1)

(ii)由命题P(1),P(2),?,P

那么,对任意n∈N

最小数原理若T是N*的一个非空子集,则存在t0∈T,使得对任意t∈T,都有t0?t,即t

上述原理是数论中经常要用到的一个原理,这里从归纳公理出发可依次方便地(并非没有挑战性)证明后续原理,它们作为数学的基础之一也是数论的基础.

数?,-3,-2,-1,0,1,2,3,?称为有理整数(rationalinteger),或简称为整数,其全体构成的集合为整数集,记为Z

数0,1,2,3,?称为非负整数(non-negativeinteger),其全体构成的集合记为N.

数1,2,3,?称为正整数(positiveinteger),其全体构成的集合记为N*.正整数是初等数论研究的主要对象,基于整数集对加法,减法和乘法是封闭的,数论中主要讨论与除法相关的问题,进门容易出门难,知识不多挑战大

整除的定义设a,b∈Z,b≠0.若存在整数q,使得a=bq,则称a能被b整除,或称b能整除a,记作b∣a.

若a能被b整除,则称a为b的倍数,b为a的约数.如果c是a的约数,也是b的约数,那么称c为a,b

整除的性质下面给出整除的一些简单性质,证明留给读者.

(i)a|b?-a|

(ii)a|b,b|c?a

(iii)a|b,a|c?对任意x,y∈Z,都有

（iv）若a,b∈N*,a∣b且b∣a,则a

由最小数原理可推出下面的:

最大数原理正整数集的任意一个有上界的非空子集必有最大元.

依此结合整除的性质可知,整数a,b(不全为零)的公约数中有最大元,称之为a,b的最大公约数

裴蜀(Bezout)定理又称为裴蜀等式,最大公约数定理.设a,b是两个不全为零的整数,则存在x

ax

为证此定理成立,我们需要了解:带余除法定理和辗转相除的方法.

带余除法设a,b∈Z,b≠0

a

证明存在性.当b∣a时,取q=ab,r

T

由于b?a,可知T中数(如果存在)都为正整数,而T中存在正整数(例如,取k=-b(|a|+1)),因此,T是N*的非空子集,必有最小元,设其为t0(对应的k为k0).我们说:t0|b|(注意,t0=a-bk0,知a=bk0+t0或者a=bk0-t0,

唯一性.若还存在q和r满足

a

不妨设r?r,将(2)与(3)

r

由于0?r-r|b|,上式两边取绝对值,可知q-q=0(否则

[注]一套理论建立之初,经常需要处理一些不平凡的简单结论,有足够的耐心才能获得清晰的思路.

辗转相除法(Euclid算法)设a,b∈Z,b≠0,b?

u

证明对u0,u1=(a,b)用前面的定理,结合b?a,可知第一式成立.若u2?u

u

每一次,uj+1都比uj至少小1,而小于u1的正整数只有有限个,上述过程必然终止,再结合1是任何整数的约数,可知存在某个k,使得uk+11,但uk+1∣u

现在来证明裴蜀定理.

由(4)知uk+1∣uk,知uk+1∣uk-1(因为uk-1=qk-1u

另一方面,d∣a且d∣b,知d∣u2(因为u2=

上述讨论表明:d=

接下来,从(4)的第k式向上看,uk+1是uk,uk-1的“线性组合”,uk是uk-1,uk-2的“线性组合”,故uk+1也是uk-1,u

综上可知,(1)成立,裴蜀定理获证.

为导出算术基本定理,我们需要将正整数分类:可约的与不可约的(这样来称呼,可以将数论的一些知识简单地推广到一元多项式中去),如果一个正整数可以表示为两个更小的正整数之积,那么称它为可约的,可约的正整数叫做合数.其余的正整数都是不可约的,在不可约的正整数中去掉那个特殊的数1后,剩下的叫做素数.

素数集是正整数集中最重要的子集,每一个(大于1的)正整数都可以用一些素数来刻画其性质,其基础是下面的:

算术基本定理每一个大于1的正整数都可以表示为若干个素数(可以重复)的乘积的形式,这种表示在不考虑素因数的排列次序时是唯一的.

证明先证可以表出:注意到,一个大于1的正整数n,要么它是素数(