数论基础知识new

《数论基础知识new》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数论基础知识.txt丶︶￣喜欢的歌，静静的听，喜欢的人，远远的看我笑了当初你不挺傲的吗现在您这是又玩哪出呢？全文:数论的基本知识本文将简单地介绍有关整数集合Z={…,-2,-1,0,1,2,…}和自然数集合N={0,1,2,…}的最基本的数论概念。可除性与约数一个整数能被另一个整数整除的概念是数论中的一个中心概念，记号d

2、a（读作“d除a”）意味着对某个整数k，有a=kd。0可被每个整数整除。如果a>0且d

3、a，则

4、d

5、≤

6、a

7、。如果d

8、a，则我们也可以说a是d的倍数。如果a不能被d整除，则写作dFa。如果d

9、a并且d≥0，则我们说d是

10、a的约数。注意，d

11、a当且仅当(-d)

12、a，因此定义约数为非负整数不会失去一般性，只要明白a的任何约数的相应负数同样能整除a。一个整数a的约数最小为1，最大为

13、a

14、。例如，24的约数有1，2，3，4，6，8，12和24。每个整数a都可以被其平凡约数1和a整除。a的非平凡约数也称为a的因子。例如，20的因子有2，4，5和10。素数与合数对于某个整数a>1，如果它仅有平凡约数1和a，则我们称a为素数(或质数)。素数具有许多特殊性质，在数论中举足轻重。按顺序，下列为一个小素数序列:2，3，5，6，11，13，17，19，23，29，31，37

15、，41，43，47，53，59，…不是素数的整数a>1称为合数。例如，因为有3

16、39，所以39是合数。整数1被称为基数，它既不是质数也不是合数。类似地，整数0和所有负整数既不是素数也不是合数。定理1素数有无穷个。证明：假设素数只有有限的n个，从小到大依次排列为p1,p2,...,pn，则x=(p1·p2·...·pn)+1显然是不能被p1,p2,...,pn中的任何一个素数整除的，因此x也是一个素数，这和只有n个素数矛盾，所以素数是无限多的。这个证明的最早来自亚里士多德，非常漂亮，是反证法的经典应用，这个证明被欧拉称为“直接来自上帝的证

17、明”，历代的数学家也对其评价很高。除法定理，余数和同模已知一个整数n，所有整数都可以分划为是n的倍数的整数与不是n的倍数的整数。对于不是n的倍数的那些整数，我们又可以根据它们除以n所得的余数来进行分类，数论的大部分理论都是基于上述分划的。下列定理是进行这种分划的基础。定理2(除法定理)对任意整数a和任意正整数n，存在唯一的整数q和r，满足0

18、我们有n

19、a当且仅当amodn=O，并且有下式成立：(1)或(2)当我们定义了一个整数除以另一个整数的余数的概念后，就可以很方便地给出表示同余的特殊记法。如果(amodn)=(bmodn)，就写作a≡b(modn)，并说a和b对模n是相等的。换句话说，当a和b除以n有着相同的余数时，有a≡b(modn)。等价地有，a≡b(modn)当且仅当n

20、(b-a)。如果a和b对模n不相等，则写作aTb(modn)。例如，61≡6(mod11)，同样，-13≡22≡2(mod5)。根据整数模n所得的余数可以把整数分成n个等价类。模n等价类包含的整数

21、a为：例如，[3]7={…,-11,-4,3,10,17,…}，该集合还有其他记法[-4]7和[10]7。a∈[b]n。就等同于a≡b(modn)。所有这样的等价类的集合为:(3)我们经常见到定义(4)如果用0表示[0]n，用1表示[1]n。等等，每一类均用其最小的非负元素来表示，则上述两个定义(3)和(4)是等价的。但是，我们必须记住相应的等价类。例如，提到Zn的元素-1就是指[n-1]n，因为-1=n-1(modn)。公约数与最大公约数如果d是a的约数并且也是b的约数，则d是a与b的公约数。例如，24与30的公约数为1,2,3和6。

22、注意，1是任意两个整数的公约数。公约数的一条重要性质为:(5)更一般地，对任意整数x和y，我们有(6)同样，如果a

23、b，则或者

24、a

25、≤

26、b

27、，或者b=O，这说明：(7)两个不同时为0的整数a与b的最大公约数表示成gcd(a,b)。例如，gcd(24,30)=6，gcd(5,7)=1，gcd(0,9)=9。如果a与b不同时为0，则gcd(a,b)是一个在1与min(

28、a

29、,

30、b

31、)之间的整数。我们定义gcd(O,0)=0，这个定义对于使gcd函数的一般性质(如下面的式(11))普遍正确是必不可少的。下列性质就是gcd函数的基本性质：(8)

32、(9)(10)(11)(12)定理3如果a和b是不都为0的任意整数，则gcd(a,b)是a与b的线性组合集合{ax+by:x,y∈Z}中的最小正元素。证明：设s是a与b的线性组合集中的最小正元素，并且对某个