初等數(shù)論整除理論

初等數(shù)論整除理論第1頁，課件共19頁，創(chuàng)作于2023年2月1、素數(shù)

(1)、素因子

(2)、素數(shù)分布

(3)、素數(shù)搜尋

(4)、素性判定2、GCD和LCM第2頁，課件共19頁，創(chuàng)作于2023年2月定義若整數(shù)a

0，1，并且只有約數(shù)1和a，則稱a是素數(shù)（或質(zhì)數(shù)）；

否則稱a為合數(shù)。定理任何大于1的整數(shù)a都至少有一個素約數(shù)。推論任何大于1的合數(shù)a必有一個不超過a1/2的素約數(shù)。定理(算術(shù)基本定理)任何大于1的整數(shù)n可以唯一地表示成(標(biāo)準(zhǔn)分解式)

其中p1,

p2,,pk是素數(shù)，p1<p2<<pk，1,2,,k是正整數(shù)。哥德巴赫猜想：“每個大于2的偶數(shù)均可表成為兩個素數(shù)之和”陳景潤：“每一個充分大的偶數(shù)都可表為一個素數(shù)及一個不超過兩個素數(shù)乘積之和”素因子第3頁，課件共19頁，創(chuàng)作于2023年2月素數(shù)分布1)、任意兩個相鄰的正整數(shù)n和n＋l(n＞3)中必有一個不是素數(shù)。

相鄰兩整數(shù)均為素數(shù)只有2和3。2)、n和n＋2均為素數(shù)的有很多,這樣一對素數(shù)稱為孿生素數(shù)。在100以內(nèi)有七對孿生素數(shù):(3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。

《自然》(2013.5.14)：新罕布什爾大學(xué)（Lecturer）（UniversityofNewHampshire，UNH）張益唐（《數(shù)學(xué)年刊》（AnnalsofMathematics））——存在無窮多對素數(shù)，其差小于7000萬。第4頁，課件共19頁，創(chuàng)作于2023年2月素數(shù)分布1)、任意兩個相鄰的正整數(shù)n和n＋l(n＞3)中必有一個不是素數(shù)。

相鄰兩整數(shù)均為素數(shù)只有2和3。2)、n和n＋2均為素數(shù)的有很多,這樣一對素數(shù)稱為孿生素數(shù)。在100以內(nèi)有七對孿生素數(shù):(3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。

3)、p為素數(shù)，2p-1稱為Mersenne數(shù)；素數(shù)2p-1稱為Mersenne素數(shù)。

p=2,3,5,7時，2p-1都是素數(shù)；p=11時，

2p-1

=2047=23×89不是素數(shù)。已發(fā)現(xiàn)最大梅森素數(shù)是p＝43,112,609的情形，一個12,978,189位數(shù)。

若an-1(a>1)是素數(shù)，則a=2，并且n是素數(shù)。(3+k)ab-1必非素數(shù)。4)、形如2^(2n)+1(n=0,1,2,)的數(shù)稱為Fermat數(shù)。

Fermat曾猜測是素數(shù)：F0,F1,F2,F3,F4是素數(shù)，F(xiàn)5=641*6700417是合數(shù)。

5)、形如4n

3的素數(shù)有無限多個。6)、越往后越稀疏：在正整數(shù)序列中,有任意長的區(qū)間中不含有素數(shù)。

對于大于等于2的整數(shù)n，連續(xù)n-1個整數(shù)n!＋2,n!＋3,…,n!＋n都不是素數(shù)。

第5頁，課件共19頁，創(chuàng)作于2023年2月素數(shù)分布7)、素數(shù)大小粗糙的估計

pn

p1p2pn-1

1，n1。

pn

22n。

(n)(log2n)/2。8)、素數(shù)定理：第6頁，課件共19頁，創(chuàng)作于2023年2月素數(shù)搜尋尋找素數(shù)的方法：Eratosthenes篩法。第7頁，課件共19頁，創(chuàng)作于2023年2月素性判定確定型算法

試除法嘗試從2到√N的整數(shù)是否整除N。威廉斯方法、艾德利曼、魯梅利法、馬寧德拉.阿格拉瓦法(log(n)的多項式級算法)……隨機算法

費馬測試利用費馬小定理來測試。

若存在a，(a,n)=1，使得a

n

1

1modn成立，則稱n是關(guān)于基數(shù)a的偽素數(shù)（Fermat偽素數(shù)，Carmichael數(shù)）。米勒-拉賓法、……第8頁，課件共19頁，創(chuàng)作于2023年2月GCD和LCM定義整數(shù)a1,a2,,ak的公共約數(shù)稱為a1,a2,,ak的公約數(shù)。不全為零的整數(shù)a1,a2,,ak的公約數(shù)中最大一個叫做a1,a2,,ak的最大公約數(shù)（或最大公因數(shù)），記為(a1,a2,,ak)。由于每個非零整數(shù)的約數(shù)的個數(shù)是有限的，所以最大公約數(shù)是存在的，并且是正整數(shù)。如果(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，反之則不然。定義整數(shù)a1,a2,,ak的公共倍數(shù)稱為a1,a2,,ak的公倍數(shù)。整數(shù)a1,a2,,ak的正公倍數(shù)中最小的一個叫做a1,a2,,ak的最小公倍數(shù)，記為[a1,a2,,ak]。第9頁，課件共19頁，創(chuàng)作于2023年2月GCD和LCMn的標(biāo)準(zhǔn)分解式：n的正因數(shù)：

n的正倍數(shù)：第10頁，課件共19頁，創(chuàng)作于2023年2月帶余數(shù)除法

設(shè)a與b是兩個整數(shù)，b

0，則存在唯一的兩個整數(shù)q和r，使得

a=bq

r，0

r<|b|。定理若a=bqr，則(a,b)

=

(b,r)。實際上給出一個求最大公因子的方法。推論設(shè)a1,a2,,an為不全為零的整數(shù)，以y0表示集合

A={y：y=a1x1

anxn，xiZ，1

i

n}中的最小正數(shù)，則對于任何yA，y0y；特別地，y0ai，1

i

n。證明：設(shè)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還小的正數(shù)，這與y0的定義矛盾。所以r0=0，即y0y。顯然aiA（1

i

n），所以y0整除每個ai（1

i

n）。GCD和LCM第11頁，課件共19頁，創(chuàng)作于2023年2月定理

設(shè)a1,a2,,ak

Z，記A={y：y=，xiZ，

i

k}。如果y0是集合A中最小的正數(shù)，則y0=(a1,a2,,ak)。推論設(shè)d是a1,a2,,ak的一個公約數(shù)，則d(a1,a2,,ak)。

最大公約數(shù)不但是公約數(shù)中的最大的，而且是所有公約數(shù)的倍數(shù)。定理記d=(a1,a2,,ak)，則(a1/d,a2/d,,ak/d)=1。特別地,(a/(a,b),b/(a,b)=1。定理

(a1,a2,,ak)=1的充要條件是存在整數(shù)x1,x2,,xk，使得

a1x1

a2x2

akxk=1。定理對于任意的整數(shù)a，b，c，下面的結(jié)論成立：

(ⅰ)由bac及(a,b)=1可以推出bc；

(ⅱ)由bc，ac及(a,b)=1可以推出abc。推論若p是素數(shù)，則下述結(jié)論成立：

(ⅰ)pab

pa或pb；

(ⅱ)pa2

pa。GCD和LCM第12頁，課件共19頁，創(chuàng)作于2023年2月推論若(a,b)=1，則(a,bc)=(a,c)。（備注1）推論若(a,bi)=1，1

i

n，則(a,b1b2bn)=1。定理對于任意的n個整數(shù)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第13頁，課件共19頁，創(chuàng)作于2023年2月定理下面的等式成立：(ⅰ)[a,1]=|a|，[a,a]=|a|；(ⅱ)[a,b]=[b,a]；(ⅲ)[a1,a2,,ak]=[|a1|,

|a2|,|ak|]；(ⅳ)若ab，則[a,b]=|b|。推論由[a,b]=ab/(a,b)有：兩個整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除。

定理對于任意的n個整數(shù)a1,a2,,an，記

[a1,a2]=m2，

[m2,a3]=m3，

，

[mn2,an1]=mn1，

[mn1,an]=mn，則

[a1,a2,,an]=mn。推論若m是a1,a2,,an的公倍數(shù)，則[a1,a2,,an]|m。GCD和LCM第14頁，課件共19頁，創(chuàng)作于2023年2月定理整數(shù)a1,a2,,an兩兩互素，即(ai,aj)=1，1

i,j

n，i

j的充要條件是

[a1,a2,,an]=a1

a2

an。

如果m1,m2,,mk是兩兩互素的整數(shù)，那么要證明m=m1m2mk整除某個整數(shù)Q，只需證明對于每個i，1

i

k，都有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次除法，顯然遠遠少于m1×m2××mk

=m。

GCD和LCM第15頁，課件共19頁，創(chuàng)作于2023年2月輾轉(zhuǎn)相除法/Euclid算法

設(shè)a與b是兩個整數(shù)，b

0，依次做帶余數(shù)除法：

a=bq1

r1， 0<r1<|b|，

b=r1q2

r2， 0<r2<r1

，

rk1=rkqk+1

rk+1， 0<rk+1<rk

， (1)

rn2=rn1qn

rn，

0<rn<rn-1

，

rn1=rnqn+1

。由于b是固定的，而且|b|>r1>r2>

，所以式(1)中只包含有限個等式。

GCD和LCM第16頁，課件共19頁，創(chuàng)作于2023年2月輾轉(zhuǎn)相除法/Euclid算法

引理用下面的方式定義Fibonacci數(shù)列{Fn}：

F1=F2=1，F(xiàn)n=Fn1

Fn

2，n

3，那么對于任意的整數(shù)n3，有

Fn>

n2， (2)其中

=(1+51/2)/2。定理(Lame)設(shè)a,bN，a>b，使用在式(1)中的記號，則n<5log10b。

定理使用式(1)中的記號，記

P0=1，P1=q1，Pk=qkPk1

Pk2，k2，

Q0=0，Q1=1，Qk=qkQk