《初等数论》由会员分享，可在线阅读，更多相关《初等数论（8页珍藏版）》请在金锄头文库上搜索。
1、初等数论 初等数论从表面意义来讲，就是作为一门研究数的相关性质的数学学科。准确地按照潘承洞、潘承彪两位数论大师的说法：初等数论是研究整数最基本的性质，是一门十分重要的数学基础课。它不仅是中、高等师范院校数学专业，大学数学各专业的必修课，而且也是计算机科学等相关专业所需的课程。纵观数论发展过程，我国出现了许许多多的数论大师，如：华罗庚的早期研究方向、陈景润、潘承洞等。第一部分：整除初接触初等数论，经过初等数论课本知整除理论是初等数论的基础。整除理论首先涉及整除。现向上延伸则想到整除的对象，即自然数、整数。从小学、中学再到大学，我们从接触最初的1、2、3再到后来的有理数、无理数、实数再到复数，可谓
2、种类繁多。但数论中的整除运算仅仅局限于自然数及其整数等相关范围内。首先大学数学中绝大多数数学定义中的自然数不包括0 ，这似乎与中学有一点差别，当然整数的定义改变就相对少得多。另外，自然数、整数的相关基本性质需懂得及灵活利用，如分配律、交换律、反对称性等。在初等代数中曾系统地介绍了自然数的起源问题：自然数源于经验，自然数的本质属性是由归纳原理刻画的，它是自然数公理化定义的核心。自然数集合严格的抽象定义是由Peano定理给出的，他刻画了自然数的本质属性，并导出有关自然数的有关性质。Peano定理：设N是一个非空集合，满足以下条件：（）对每一个nN，一定有唯一的一个N中的元素与之对应，这个元素记作n
3、+,称为是n的后继元素（或后继）；（）有元素eN，他不是N中任意元素的后继；（）N中的任意一个元素至多是一个元素的后继，即从a+=b+ 一定可以推出a=b;()(归纳原理)设S是N的一个子集合，eS, 如果nS则必有n+ S,那么，S=N.这样的集合N称为自然数集合，它的元素叫做自然数。其中的归纳原理是我们常用的数学归纳法的基础。数学归纳法在中学已属重点内容，此处就不作介绍。主要描述一下推广状态下的第二种数学归纳法：（第二种数学归纳法）设P(n)是关于自然数n的一种性质或命题。如果（1） 当n=1时，P(1)不成立；（2） 设n1,若对所有的自然数mn,P(m)成立，则必可推出P(n)成立。那
4、么,P(n)对所有的自然数都成立。数学归纳法是一种非常常用的数学方法，其重要性不必多说。另外，由归纳法原理还可推出两个在数学中，特别是初等数论中常用的自然数的性质，即最小自然数原理和最大自然数原理。并且最小自然数原理是我们常用的第二数学归纳法的基础。此外，在初等数论中还经常用到的一个工具，那就是鸽巢原理，也就是同等意义下的在组合数学中的抽屉原理。介绍完自然数和整数及其性质定理等数论基础后，下面来关注初等数论的一写重要方面，即整除、带余数除法、辗转相除法、素数、约数、最大公约数理论、算术基本定理等等。整除既然是初等数论的基础内容，看似简单的整除，若要领略各中精髓以及其中之奥妙，仍需下一番苦功夫。
5、单从整除的定义就有各种解释方法：1） 设a,bZ,a0,如果存在qZ,使得b=aq,那么就说b可被a整除，记作ab.2） Z上定义一种关系R，令R=(a,b)a0.bZ，且在使ax=b有解，称为Z上的整除关系。（任意的R，存在a,bZ，使得=（a,b）R,一般写成aRb,称为a与b有整除关系，也称a是b的约数，也称b是a的倍数。）aRb令为ab,这就回到了第一种定义，其实这两种定义方式看似一样，其数学内涵却大有不同：第一种定义方法是从最原始的观点出发，也可说从“整除”的字面意思来定义，也是中学最常用的一种定义方式，因此只能算作一种简单明了的数学思维，并不能真正体现数学的高等数论。尽管初等数论是
6、一种初等思想去解决一些高等难题。第二种定义方法则焦点于高等代数中的环、域定义。环、域定义让我们的数学定义方式更加广泛，这是初等数学中所没有的，因此有的时候初等数学解决不了的问题就可以用此种定义去解决，这给了我们更广泛的思维空间。对整除的各方面性质可以归纳如下：1） 序关系 (N,bRa 对称关系 aRb,bRc=aRc 传递性注意：整除不是等价关系3） 整除具有线性可加性 abi (1in) abixi xiZ4） 整除可约性 ab mamb(m0)5） 整除与符号无关 abab -aba-b6） ab(b0)=ab上面这些性质可以灵活的加以利用，其魅力就可显现出来：已知a,bZ.a2+b20
7、,存在x,yZ使得ax+by=1.若abq,则可证aqA ,b同例1存在ax+by=1 如果 an,bn 则abn整除的这些性质应用可谓变幻无穷。特别是在后面的素数、合数的相关性质方面及其证明中。下面就来介绍一下关于素数的一些性质，当然介绍素数的同时还涉及到关于合数的问题。点到部分再一一介绍。从目前所学的内容来看关于素数的性质占了很大的比重，应该说是素数和整除的性质占了很大的部分，故彰显其重要性。素数的概念与中学学的相差不大，只存在名称的扩充问题。显然约（因、除）数，非显然约（因、除）数，真约（因、除）数的辨别问题。当然须指出的是以后所介绍的素数一般指正的。知道素数的概念后就应该思考一下关于素
8、数的基本求法。在课本随后的介绍中讲到了Eratosthenes筛法（在本书的第八章：素数分布的初等结果中有详细的讲解）来自书中的推论6即为该筛法的相关理论背景：推论6：设整数a2.() 若a是合数，则必有不可约数pa,pa1/2() 若a=p1p2ps的表示式，则必有不可约数p|a,pa1/s其主要原理就来自于这个推论6。当然此种意义下的Eratosthenes筛法是最简单的了。对于它的推广应用还很多，比如说：如何找出1，2，,N中至多两个素数的乘积的数？这就是推广意义下的应用，只是在推论6的理论下a的二分之一的情况改为三分之一的情况，这也可以看出推论6也可以推广的。故我们知道该筛法有很多种应
9、用情况，比如说至少两个素数的乘积的情况，至多三个的情况，至少三个的情况等等。我们可以明显地观察出上面的这些解法是在有限的情况下来讨论的，故我们需要研究一下再不知道具体情况下的素数的一些情况。在不明确范围的情况下有很多种状况：如：设n1，2n+1是素数的必要条件是n=2k；2n-1是素数的必要条件是n为素数；其证明也很简单：若n2，则n=am,2不等于大于1的m2n+1=(2a)m+1=(2a+1)(2a)m-1-(2a)m-2+1)便可得到若n是合数，则n=am.a1,m12n-1=(2a)m-1=(2a-1)(2a)m-1+(2a)m-2+1)便可得到其中数学中的一个著名定理是：不可约数（素
10、数）有无穷多个。除了课本中给出的证明方法以外，在习题中也有一些证明方式来进行证明：如：1）设n0,Fn=2的2N次加上1（它称为Fermat数）再设mn,且d|Fn,则dFn由此推出素数有无穷多个，且可得到Fn+1=Fn F0 +2 ;2) 设F1 =2， An+1=A2n AN +1,再设nm,若d|An,d1,则 d 不整除于Am,由此推出素数有无穷多个，且可得到An+1=An A1 +1.(设m1,m|(m-1)!+1，可得到m是素数。)有了素数及整除的定义后，首先要考虑的就是公约数、最大公约数、公倍数、最小公倍数。乍一看，这似乎就是中学内容。不错，根据初等数论的低落脚点，这属于中学知识
11、的衍生而已。除了其定义是通过整除来定义以外，其他的性质也有适当的延伸。其中较重要的一个就是：如果存在整数x1,x2,x2,xk,使得a1x1+a2x2+a3x3+akxk=1,则a1,a2,ak是既约的，即使互素的。-（1）这一定理在后面部分有着十分重大的作用。如在实现建立最大公约数理论的第二个途径处：设a1,ak是不全为零的整数，有1）（a1,a2,ak）=mins=a1x1+a2x2+akxk;xjZ(1jk),s0,即a1,ak 的最大公约数等于a1,ak的所有整系数线性组合组成的集合S中的最小正整数。2）一定存在一组整数x1,0, ,xk,0 使得(a1, ,ak )=a1 x1,0
12、+ + ak xk,0 -（2）要论及上面这个定理得应用，下面可以举一个简单的例子：若（a,b）=1则任一整数n必可表示为n=ax+by,x,y是整数。由(a,b)=1及上定理（2）知存在x0,y0, 使得ax0+by0=1,因而取x=nx0,y=ny0, 即满足要求。此题属于定理（1）（2）得综合运用，仍可想到的是在定理（2）有一种特殊情况，若其中的每一个元素均两两互素，那么情况（2）也就变成情况（1）了，因此情况（2）可以看作此种情况（1）的推广，情况（1）就看作情况（2）得特殊情况而已。在构造一系列既约数方面应用得较多的方法就是下面这个方法：（a1/(a1,ak),ak/(a1,ak)）
13、=1关于最大公约数理论和最小公倍数理论的进一步性质推广，重在利用带余数除法在最大公约数理论部分讨论。整数集合最重要的特性就在于其中可以实现带余数除法（也称带余除法或除法算法），它是初等数论中的证明中最重要、最基本、最直接的工具。具体应用带余数除法时常取以下更灵活的形式：设a,b是两个给定的整数，a0,再设d 是一给定的整数，那么，一定存在唯一的一对整数q1与r1，满足 b=q1a+r1,dr10,任一整数被a除后所得的最小非负余数是且仅是0,1,a-1这a个数中的一个。这个推论最直接的用法就是整数分类以及进位制表示法，间接影响到辗转相除法。首先来看整除分类：j mod m称为j关于除数m所在的
14、剩余类，则有0 mod a1 mod a(a-1) mod a=Z,其中0ij（a-1）是集合j mod a 和 j mod a 不相交。此时是利用全体整数按被a除后所得的最小非负余数分类，分成了两两不相交的a个类，这对诠释整除的含义有更积极的意义。仔细观察，我们就会发现此种划分法与第三章中的“同余”有相似之处，最明显之处就是定义：a同余于模m，如果设m0,若m|a-b,即a-b=km，与 j mod m的定义j 关于除数m的所在剩余类，或许根本就是一个知识点。确切的说j mod m 这个知识点属于同余的一个分支而已，即同余类（剩余类）。进位制的表示法可以看作是初等数论与计算机科学的一个交叉利用。在计算机理论科学中，经常会遇到十进制、二进制、八进制、十六进制、甚至三十二进制之类的知识点。而初等数论中的此处讲解得更为广泛、更为深刻。辗转相除法单独运用的情况一般较少，常用于综合分析，特别是与最大公约数理论的联合利用。最大公约数理论与最小公倍数理论及其推广逐渐涉及到实际生活中的问题，例如四色问题的翻版。至此，建立了整数集合Z中的最大公约数理论，特别是讨论了如何从各种不同的途径来建立这一理论，这是尤为重要的。因为这主要不是为了利用不同的技
