初等数论1 - 整除理论.ppt

1、整数除法理论，1。质数(1)、质因数(2)、质数分布(3)、质数搜索(4)、质数确定(2)、GCD和LCM，定义了如果整数为0、1且只有约1和A，则A称为质数(或质数)；否则，a称为复合数。定理任何大于1的整数都至少有一个素数除数。可以推断，任何大于1的复合数A必须有一个不超过1/2的素数除数。定理(算术基本定理)任何大于1的整数都可以唯一地表示为(标准分解公式)，其中p1、p2、pk是素数，p1、p2、pk、1、2、K是正整数。哥德巴赫猜想：“每一个大于2的偶数都可以表示为两个素数之和”陈景润：“每一个足够大的偶数都可以表示为一个素数和不超过两个素数的乘积之和”，素数因子，素数分布，1)任意

2、两个相邻的正整数n和nl (n3)中的一个不能是素数。两个相邻的整数是质数，只有2和3。2)，N和n2都是质数，所以一对质数称为孪生质数。在100以内，有七对孪生素数： (3，5)，(5，7)，(11，13)，(29，31)，(41，43)，(59，61)和(71，73)。自然(2013年5月14日):新罕布什尔大学的张(数学年鉴)中有无限对素数，相差不到7000万。1)任意两个相邻的正整数n和n1(n3)之一不是质数。两个相邻的整数是质数，只有2和3。2)，N和n2都是质数，所以一对质数称为孪生质数。在100以内，有七对孪生素数： (3，5)，(5，7)，(11，13)，(29，31)，(4

3、1，43)，(59，61)和(71，73)。3) P是质数，2p-1称为梅森数；素数2p-1被称为梅森素数。当p=2，3，5和7时，2p-1是质数。当p=11时，2p-1=2047=2389不是质数。已经发现，梅森素数的最大值是43，112，609，即12，978，189位数。如果-1(a1)是质数，那么a=2，n是质数。(3 k)ab-1不能是质数。4)形式为2(2n) 1 (n=0，1，2)的数称为费马数。费马曾猜测这是一个质数：F0、F1、F2、F3和F4是质数，F5=641*6700417是一个复合数。5)4n 3形式的素数有无穷多个。6)随着时间的流逝而稀疏：在正整数序列中，在任何长

4、的区间中都没有质数。对于大于或等于2的整数n，n-1个连续整数n！2，n！3，n！n不是质数。素数分布，7)，素数大小的粗略估计。pn 22n .(n) (log2n)/2 .8)素数定理：寻找素数，找到素数的方法：厄拉多塞筛方法。威廉姆斯方法、埃德尔曼方法、鲁梅利方法和马宁德拉阿格拉瓦方法(对数(n)的多项式级算法)用费马小定理进行了检验。如果有一个，(a，n)=1，那么n 1 1模n成立，那么n是关于基数a的伪素数(费马伪素数，卡迈克尔数)。米勒-拉宾方法，GCD和LCM将整数A1，A2，AK的公约数定义为A1，A2，AK的公约数。不全为零的整数a1、a2和AK的最大公约数被称为a1、a2

5、和AK的最大公约数(或最大公因数)，并被表示为(a1、a2和AK)。因为每个非零整数的除数是有限的，所以最大公约数存在并且是正整数。如果(a1，a2，ak)=1，那么a1，a2，ak称为互质。如果(ai，aj)=1，1 i，j 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和LCM，n的标准分解公式：n的正因子：n的正整数：除以余数如果a和b是两个整数，那么就有两个唯一的整

6、数q和r，这样a=bq r，0 r |b|。定理如果a=bq r，那么(a，b)=(b，r)。实际上，给出了一种寻找最大公因数的方法。可以推断a1、a2、an是不全为零的整数，并且y0表示集合A=y:y=a1x1 anxn、xiZ、1 i n中的最小正数，那么对于任何yA，y0；证明了如果y0=a1x1 anxn，对于任何y=a1x1 anxnA，存在q，r0Z，这使得y=qy0 r0，0 r0 y0。因此r0=y qy0=a1(x1 qx1) an(xn qxn)A.如果r0为0，因为0 r0 y0，r0是小于a中y0的正数，这与y0的定义相矛盾。因此，r0=0，即y0y。很明显aiA(1

7、i n)，所以y0把每个ai(1 i n)分开。GCD和LCM，设a1，a2，ak Z，并记住a=y: y=，xiZ，I k。如果y0是集合a中的最小正数，y0=(a1，a2，ak)。可以推断，d是a1，a2，AK的公约数，然后是d (a1，a2，AK)。最大公约数不仅是公约数中最大的，而且是所有公约数的倍数。根据这个定理，d=(a1，a2，ak)，那么(a1/d，a2/d，AK/d)=1。特别是，(a/(a，b)，b/(a，b)=1。定理(a1，a2，ak)=1的充要条件是整数x1，x2，xk的存在，因此a1x1 a2x2 akxk=1。对于任何整数A，B，C，下列结论成立：()BC可以从b

8、ac和(A，b)=1推导出来；()Abc可以从bc、ac和(a，b)=1中推导出来。可以推断，如果P是一个质数，下列结论成立：()pab pa或PB；(pa2 pa).GCD和LCM，则推断如果(a，b)=1，则(a，bc)=(a，c)。(注1)推断如果(a，bi)=1，1in，则(a，b1b2bn)=1。任何n个整数的定理a1，a2，an，记住(注2) (a1，a2)=d2，(d2，a3)=d3，(dn-2，an-1)=dn-1，(dn-1，an)=dn，然后dn=(a1，a2，an)，GCD和LCM，下列等式成立：()a，1=|a|，a，a=| a |(a，b=b，a );()a1，a2，

9、ak=|a1|，|a2|，| ak |()如果ab，则a，b=|b|。推论是a，b=ab/(a，b):两个整数的任何公倍数都可以被它们的最小公倍数整除。任意n个整数a1，a2，an的定理，设a1，a2=m2，m2，a3=m3，mn2，an1=mn1，mn1，an=mn，然后a1，a2，an=mn。结论是，如果m是a1，a2和an的公倍数，那么a1，a2和an | m，GCD和LCM，定理整数a1，a2，an是成对素数，即(ai，aj)=1，1 i，j n，i j，当且仅当a1，a2，an=a1 a2 an。如果m1，m2，mk是成对的素数，那么为了证明m=m1m2mk整除一个整数q，我们只需要

10、证明每个I，1k都有miQ，这在实际计算中非常有用。对于多项式f(x)，要验证命题“mf(n)，nZ”是否有效，可以验证“mf(r)，r=0，1，m 1”是否有效。这需要m个部门。然而，如果分别验证“mif(ri)，ri=0，1，mi 1，1 i k”，则总共需要m1 m2 mk除法，这显然远小于M1M2MK=m，GCD和LCM，旋转和相位除法/Euclid算法假设a和b是两个整数，b 0，然后用余数除它们：a=bq1 r1，0 r1 r2，因此公式(1)仅包含有限数量的方程。GCD和LCM，旋转和相位除法/欧几里德算法的引理以如下方式定义斐波那契序列Fn:Fn:F1=F2=1，Fn=Fn 1

11、 Fn 2，n 3，那么对于任何整数n 3，都有Fn n n 2，(2)其中=(1 51/2)/2。定理(拉梅):让a，bN，a b，并使用公式(1)中的符号，然后n 5log10b。在定理中，使用公式(1)中的符号，P0=1，P1=q1，Pk=qkPk 1 Pk 2，k 2，Q0=0，Q1=1，Qk=qkQk 1 Qk 2，k 2，然后AkK BpK=(1)k 1Rk，k=1，2和n。(3)整数x，y可以通过使用旋转和相位的除法来获得，因此ax by=(a，b)。(4)为此目的所需的分区数为0(log10b)。GCD和LCM、旋转和相位分割/欧几里德算法。然而，如果只需要计算(a，b ),而不需要使等式(4)成立的整数x和y，则所需的除法次数甚至会更少。让A和B是正整数。基于以下四个基本事实，(a，b)只能通过2的除法和减法来计算。()如果ab，则(a，b)=a