初等数论1 - 整除理论

《初等数论1 - 整除理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整除理论1、素数(1)、素因子(2)、素数分布(3)、素数搜寻(4)、素性判定2、GCD和LCM定义若整数a0，1，并且只有约数1和a，则称a是素数（或质数）；否则称a为合数。定理任何大于1的整数a都至少有一个素约数。推论任何大于1的合数a必有一个不超过a1/2的素约数。定理(算术基本定理)任何大于1的整数n可以唯一地表示成(标准分解式)其中p1,p2,,pk是素数，p1

2、一个充分大的偶数都可表为一个素数及一个不超过两个素数乘积之和”素因子素数分布1)、任意两个相邻的正整数n和n＋l(n＞3)中必有一个不是素数。相邻两整数均为素数只有2和3。2)、n和n＋2均为素数的有很多,这样一对素数称为孪生素数。在100以内有七对孪生素数:(3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。《自然》(2013.5.14)：新罕布什尔大学（Lecturer）（UniversityofNewHampshire，UNH）张益唐（《

3、数学年刊》（AnnalsofMathematics））——存在无穷多对素数，其差小于7000万。素数分布1)、任意两个相邻的正整数n和n＋l(n＞3)中必有一个不是素数。相邻两整数均为素数只有2和3。2)、n和n＋2均为素数的有很多,这样一对素数称为孪生素数。在100以内有七对孪生素数:(3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。3)、p为素数，2p-1称为Mersenne数；素数2p-1称为Mersenne素数。p=2,3,5,7时，

4、2p-1都是素数；p=11时，2p-1=2047=23×89不是素数。已发现最大梅森素数是p＝43,112,609的情形，一个12,978,189位数。若an-1(a>1)是素数，则a=2，并且n是素数。(3+k)ab-1必非素数。4)、形如2^(2n)+1(n=0,1,2,)的数称为Fermat数。Fermat曾猜测是素数：F0,F1,F2,F3,F4是素数，F5=641*6700417是合数。5)、形如4n3的素数有无限多个。6)、越往后越稀疏：在正整数序列中,有任意长的区间中不含有素数

5、。对于大于等于2的整数n，连续n-1个整数n!＋2,n!＋3,…,n!＋n都不是素数。素数分布7)、素数大小粗糙的估计pnp1p2pn-11，n1。pn22n。(n)(log2n)/2。8)、素数定理：素数搜寻寻找素数的方法：Eratosthenes筛法。素性判定确定型算法试除法尝试从2到√N的整数是否整除N。威廉斯方法、艾德利曼、鲁梅利法、马宁德拉.阿格拉瓦法(log(n)的多项式级算法)……随机算法费马测试利用费马小定理来测试。若存在a，(a,n)=1，使得an11modn

6、成立，则称n是关于基数a的伪素数（Fermat伪素数，Carmichael数）。米勒-拉宾法、……GCD和LCM定义整数a1,a2,,ak的公共约数称为a1,a2,,ak的公约数。不全为零的整数a1,a2,,ak的公约数中最大一个叫做a1,a2,,ak的最大公约数（或最大公因数），记为(a1,a2,,ak)。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。如果(a1,a2,,ak)=1，则称a1,a2,,ak是互素的。如果(ai,aj)=1，1i,j

7、k，ij，则称a1,a2,,ak是两两互素的。a1,a2,,ak两两互素可以推出(a1,a2,,ak)=1，反之则不然。定义整数a1,a2,,ak的公共倍数称为a1,a2,,ak的公倍数。整数a1,a2,,ak的正公倍数中最小的一个叫做a1,a2,,ak的最小公倍数，记为[a1,a2,,ak]。GCD和LCMn的标准分解式：n的正因数：n的正倍数：带余数除法设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得a=bqr，0r<

8、b

9、。定理若a=bqr，则(a,b)

10、=(b,r)。实际上给出一个求最大公因子的方法。推论设a1,a2,,an为不全为零的整数，以y0表示集合A={y：y=a1x1anxn，xiZ，1in}中的最小正数，则对于任何yA，y0y；特别地，y0ai，1in。证明：设y0=a1x1anxn，对任意的y=a1x1anxnA，存在q,r0Z，使得y=qy0r0，0r0