文档介绍：第五章数论
数论曾经被认为是“最纯粹的数学”.但是随着计算机和复杂的密码技术的出现,---包括因式分解和模算数,,以便于理解一个称之为RSA(命名源自于它的三位发明家Rivest,Shamir和Adleman),,我们本章将要学****的数论知识除了解决被选来的例子以外,还有其他方面的广泛应用.
如果取自然数N的相反数,连同N和0一起,就得到了整数集合:…,-2,-1,0,1,2,3,….注意如果把两个自然数相加或相乘,就会得到另外一个自然数,,、乘法和减法是封闭的,.
如果a,b∈N且存在一个k∈N,使得a×k=b,|×4=12,所以3整除12,记为3|12,如果自然数k不存在,称为b不能够被a整除,记作a|b,例如3||b,也称a是b的因子(因式),,为了语言的简练,当提到a是一个数的时候,通常指a为自然数.
在所有小于等于10的自然数中,列出所有整数10的自然数,10|10吗?
如果a≠0,那么a|0,因为0=0×a,这样的话,就扩展了整除的定义,,整除的定义可以修订为:如果a∈N且b∈N∪﹛0﹜,若存在k∈N∪﹛0﹜,使得a×k=b,称为a整除b.
除法定理
除法定理是数论的基本性理论,在小学时我们就以某种形式接触到了除法
定理,,虽然并非每个自然数都能被其他自然数整除,但是通过余数形式,:320除以12,商为26,=12×26+:
除法定理 a和b是两个自然数,那么存在唯一的自然数q和r,且0≤r<b,使得a=b×q+r.
我们不在这里证明这个定理,但注意这个定理的关键问题:余数r在0和b之间,可以为0,并且数q和r是唯一的,也就是说,没有其他的自然数q和r满足这个定理.
举例来说,如果a=39,b=4,那么q=9,r=3,因为39=4×9+=5,b=13,那么q=0,r=5,因为5=10+,r代表余数.
最大公约数
通常,对一个数进行因式分解是一项很费时间的工作,,用公元前四世纪欧几里德提出的算法,我们就能非常容易而且快速的求出两个数的最大公约数.
给定两个自然数a和b,:对于任意一对自然数来讲,,例如,12和18就有公约数1,2,,称为d是a和b的最大公约数,记为d=gcd(a,b).例如gcd(42,18)=6,而gcd(24,15)=(a,b)=1,(4,15)=1.
求gcd(20,45)和gcd(21,16)的值.
考虑一个特例,当a≠0时,gcd(a,0)的值,因为每个非零数都是0的因子,所以gcd(a,0)=a.
为什么每对自然数肯定有一个最大公约数呢?已经知道1是任意一对自然数的公约数,那么每对自然数的所有公约数组成的集合肯定不是空集,,该集合必有一个最大值.
为了求a和b最大公约数,我们可以简单地从两个数中较小的那个数开始,并且每次对较小的数减1,然后判断结果是不是a和b的公约数,重复这个步骤,,或者它们的最大公约数很小,,.
:在这个例子里,根据算法,反复对一系列数求商和余数,(285,255):
285=25×51+30
255=30×8+15