初等数论整除理论

初等数论整除理论第1页，课件共19页，创作于2023年2月1、素数

(1)、素因子

(2)、素数分布

(3)、素数搜寻

(4)、素性判定2、GCD和LCM第2页，课件共19页，创作于2023年2月定义若整数a

0，1，并且只有约数1和a，则称a是素数（或质数）；

否则称a为合数。定理任何大于1的整数a都至少有一个素约数。推论任何大于1的合数a必有一个不超过a1/2的素约数。定理(算术基本定理)任何大于1的整数n可以唯一地表示成(标准分解式)

其中p1,

p2,,pk是素数，p1<p2<<pk，1,2,,k是正整数。哥德巴赫猜想：“每个大于2的偶数均可表成为两个素数之和”陈景润：“每一个充分大的偶数都可表为一个素数及一个不超过两个素数乘积之和”素因子第3页，课件共19页，创作于2023年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）张益唐（《数学年刊》（AnnalsofMathematics））——存在无穷多对素数，其差小于7000万。第4页，课件共19页，创作于2023年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)。

3)、p为素数，2p-1称为Mersenne数；素数2p-1称为Mersenne素数。

p=2,3,5,7时，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)、越往后越稀疏：在正整数序列中,有任意长的区间中不含有素数。

对于大于等于2的整数n，连续n-1个整数n!＋2,n!＋3,…,n!＋n都不是素数。

第5页，课件共19页，创作于2023年2月素数分布7)、素数大小粗糙的估计

pn

p1p2pn-1

1，n1。

pn

22n。

(n)(log2n)/2。8)、素数定理：第6页，课件共19页，创作于2023年2月素数搜寻寻找素数的方法：Eratosthenes筛法。第7页，课件共19页，创作于2023年2月素性判定确定型算法

试除法尝试从2到√N的整数是否整除N。威廉斯方法、艾德利曼、鲁梅利法、马宁德拉.阿格拉瓦法(log(n)的多项式级算法)……随机算法

费马测试利用费马小定理来测试。

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

n

1

1modn成立，则称n是关于基数a的伪素数（Fermat伪素数，Carmichael数）。米勒-拉宾法、……第8页，课件共19页，创作于2023年2月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

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]。第9页，课件共19页，创作于2023年2月GCD和LCMn的标准分解式：n的正因数：

n的正倍数：第10页，课件共19页，创作于2023年2月带余数除法

设a与b是两个整数，b

0，则存在唯一的两个整数q和r，使得

a=bq

r，0

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

=

(b,r)。实际上给出一个求最大公因子的方法。推论设a1,a2,,an为不全为零的整数，以y0表示集合

A={y：y=a1x1

anxn，xiZ，1

i

n}中的最小正数，则对于任何yA，y0y；特别地，y0ai，1

i

n。证明：设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

i

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

i

n）。GCD和LCM第11页，课件共19页，创作于2023年2月定理

设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，下面的结论成立：

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

(ⅱ)由bc，ac及(a,b)=1可以推出abc。推论若p是素数，则下述结论成立：

(ⅰ)pab

pa或pb；

(ⅱ)pa2

pa。GCD和LCM第12页，课件共19页，创作于2023年2月推论若(a,b)=1，则(a,bc)=(a,c)。（备注1）推论若(a,bi)=1，1

i

n，则(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第13页，课件共19页，创作于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)有：两个整数的任何公倍数可以被它们的最小公倍数整除。

定理对于任意的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第14页，课件共19页，创作于2023年2月定理整数a1,a2,,an两两互素，即(ai,aj)=1，1

i,j

n，i

j的充要条件是

[a1,a2,,an]=a1

a2

an。

如果m1,m2,,mk是两两互素的整数，那么要证明m=m1m2mk整除某个整数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页，创作于2023年2月辗转相除法/Euclid算法

设a与b是两个整数，b

0，依次做带余数除法：

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页，创作于2023年2月辗转相除法/Euclid算法

引理用下面的方式定义Fibonacci数列{Fn}：

F1=F2=1，Fn=Fn1

Fn

2，n

3，那么对于任意的整数n3，有

Fn>

n2， (2)其中

=(1+51/2)/2。定理(Lame)设a,bN，a>b，使用在式(1)中的记号，则n<5log10b。

定理使用式(1)中的记号，记

P0=1，P1=q1，Pk=qkPk1

Pk2，k2，

Q0=0，Q1=1，Qk=qkQk