资源描述：
《数论基础知识》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、全文：数论的基本知识本文将简单地介绍有关整数集合Z二｛・・・,-2,-1,0,1,2,…｝和自然数集合N=｛0,l,2,・•・｝的最基本的数论概念。可除性与约数一个整数能被另一个整数整除的概念是数论中的一个中心概念，记号d
2、a(读作“d除a”)意味着对某个整数k,有a二kdo0可被每个整数整除。如果a>0JJ.d
3、a,则
4、d
5、W
6、a
7、。如果d
8、a,则我们也可以说a是d的倍数。如果a不能被d整除，则写作dFa。如果d
9、a并且dMO,则我们说d是a的约数。注意，d
10、a当且仅当(-d)
11、a,因此定义约数为非负整数不会失去一般性，只要明白a的任
12、何约数的和应负数同样能整除a0一个整数a的约数最小为1,最大为*1。例如，24的约数有1,2,3,4,6,8,12和24。每个整数a都可以被其平凡约数1和a整除。a的非平凡约数也称为a的因子。例如，20的因子有2,4,5和10。素数与合数对于某个整数a>l,如果它仅有平凡约数1和a,则我们称a为素数(或质数)。素数具有许多特殊性质，在数论屮举足轻重。按顺序，下列为一个小素数序列：2,3,5,6,11,13,17,19,23,29,31,37,41,43,47,53,59,…不是素数的整数a>l称为合数。例如，因为有3
13、39,所以39是合
14、数。整数1被称为基数，它既不是质数也不是合数。类似地，整数0和所有负整数既不是素数也不是合数。定理1素数有无穷个。证明：假设素数只有有限的n个，从小到大依次排列为pl,p2,...,pn,则x二(pl・p2・...・pn)+l显然是不能被pl,p2,...,pn中的任何一个索数整除的，因此x也是一个索数，这和只有n个素数矛盾，所以素数是无限多的。这个证明的最早来白亚里士多徳，非常漂亮，是反证法的经典应用，这个证明被欧拉称为“直接來自上帝的证明”，历代的数学家也対其评价很高。除法定理，余数和同模己知一个整数n,所有整数都可以分划为是n的倍
15、数的整数与不是n的倍数的整数。对于不是n的倍数的那些整数，我们又可以根据它们除以n所得的余数来进行分类，数论的大部分理论都是基于上述分划的。下列定理是进行这种分划的基础。定理2(除法定理)对任意整数a和任意正整数n,存在唯一的整数q和r,满足Wn,并JJ.a=qn+r0这个定理是整数的基木定理之一，这里就不给岀具体证明了。值q=?a/n?称为除法的商(?x?表示地板符号floor,即小于等于x的最大整数)。值r=amodn称为除法的余数。我们有当且仅当amodn二0,并且有下式成立：(1)或(2)当我们定义了一个整数除以期一个整数的余数
16、的概念后，就可以很方便地给出表示同余的特殊记法。如果(amodn)=(bmodn),就写作a=b(modn),并说a和b对模n是相等的。换句话说，当a和b除以n有著相同的余数时，有a三b(modn)0等价地有，a=b(modn)当且仅当n
17、(b-a)o如果a和b对模n不相等,则写作aTb(modn)。例如，61=6(mod11),同样，-13三22=2(mod5)。根据整数模n所得的余数可以把整数分成n个等价类。模n等价类包含的整数a为：例如，⑶7二{・・・,-11,-4,3,10,17,・・・},该集合还有其他记法[-4]7和[10]
18、7。aG[b]n。就等同于a三b(modn)0所有这样的等价类的集合为：(3)我们经常见到定义(4)如果用0农示[0]n,用1表示[l]no等等，每一类均用其最小的非负元素来表示，则上述两个定义(3)和(4)是等价的。但是，我们必须记住相应的等价类。例如，提到Zn的元素-1就是指[n-l]n,因为T=n-1(modn)。公约数与最大公约数如果d是a的约数并且也是b的约数，则d是a与b的公约数。例如，24与30的公约数为1,2,3和6。注意，1是任意两个整数的公约数。公约数的一条重耍性质为:更一般地，对任意整数X和y,我们有(6)同样，如
19、果a
20、b,则或者
21、a
22、W
23、b
24、,或者b二0,这说明：(7)两个不同时为0的整数a与b的最大公约数表示成gcd(a,b)«例如，gcd(24,30)二6,god(5,7)=1,gcd(0,9)=9o如果a与b不同时为0,则gcd(a,b)是一个在1与min(
25、a
26、,
27、b
28、)之间的整数。我们定义gcd(0,0)=0,这个定义对于使gcd函数的一般性质(如下面的式(11))普遍正确是必不可少的。下列性质就是gcd函数的棊木性质：(8)(9)(10)(11)(12)定理3如果a和b是不都为0的任意整数，则gcd(a,b)是a与b的线性组合集合｛
29、ax+by:x,yeZ｝中的最小正元素。证明：设s是a与b的线性组合集中的最小正元索，并对某个x,yez,冇s二ax+by,设q=?a/s?,则式(2)说明因此,amods也是a与b的一种线性组合。但由于a
