版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1/3/2023
22:11数论的基本内容按照研究方法的不同,数论可分为初等数论解析数论代数数论几何数论12/27/202219:32
1/3/2023
22:11参考书目1、南基洙主编《初等数论》;2、柯召、孙琦编著《数论讲义》,高等教育出版社;3、闵嗣鹤、严士健编《初等数论》,高等教育出版社;4、郑克明主编《初等数论》,西南师范大学出版社。12/27/202219:32
1/3/2023
22:11初等数论第一章整除
§1自然数与整数12/27/202219:32
1/3/2023
22:11归纳原理设S是N的一个子集,满足条件:(ⅰ)1∈S;(ⅱ)如果n∈S,则n+1∈S,那么,S=N.12/27/202219:32
1/3/2023
22:11定理1数学归纳法
设P(n)是关于自然数n的一种性质或命题.如果(ⅰ)当n=1时,P(1)成立;(ⅱ)由P(n)成立必可推出P(n+1)成立,那么,P(n)对所有自然数n成立.12/27/202219:32
1/3/2023
22:11定理2最小自然数原理设T是N的一个非空子集.那么,必有t0∈T,使对任意的t
∈T有t0≤t,即t0是T中的最小自然数.12/27/202219:32
1/3/2023
22:11定理3最大自然数原理设M是N的非空子集.若M有上界,即存在
a∈N,使对任意的m∈M有m
≤a,那么必有m0∈M,使对任意的m∈M有m≤m0,即m0是M中的最大自然数。12/27/202219:32
1/3/2023
22:11定理4第二数学归纳法设P(n)是关于自然数n的一种性质或命题.如果(ⅰ)当n=1时,P(1)成立;(ⅱ)设n>1.若对所有的自然数m<n,P(m)成立,则必可推出P(n)成立,那么,P(n)对所有自然数n成立.12/27/202219:32
1/3/2023
22:11定理5鸽巢原理设n是一个自然数.现有n个盒子和n+1个物体.无论怎样把这n+1个物体放入这n个盒子中,一定有一个盒子中被放了两个或两个以上的物体。12/27/202219:32
1/3/2023
22:11§2整除12/27/202219:32
1/3/2023
22:11定义1设a,b是整数,a
0,如果存在整数q,使得b=aq,则称b可被a整除,记作ab,且称b是a的倍数,a是b的约数(因数、除数);如果不存在整数q使得b=aq成立,则称b不被a整除,记为ab。被2整除的数称为偶数,不被2整除的称为奇数
12/27/202219:32
1/3/2023
22:11定理1下面的结论成立:(ⅰ)
a|b(-a)|b
a|(-b)(-a)|(-b)|a|||b|;(ⅱ)
ab,bcac;(ⅲ)
ab,ac对任意x、y,有abx+cy,一般地,abi,i=1,2,,kab1x1
b2x2
bkxk,此处xi(i=1,2,,k)是任意的整数;(ⅳ)
abacbc,c是任意的非零整数;(ⅴ)
ab且ba
a=
b;(ⅵ)
ab,b
0|a|≤|b|;ab且|b|<|a|
b=0.12/27/202219:32
1/3/2023
22:11例1证明:若3|n且7|n,则21|n.例2设a=2t-1.若a|2n,则a|n.例3设a、b是两个给定的非零整数,且有整数x、y,使得ax+by=1.证明:若a|n且b|n,则ab|n.例4设f(x)=anxn+an-1xn-1++a1x+a0
∈Z[x],其中Z[x]表示全体一元整系数多项式组成的集合.若d|b-c,则d|f(b)-f(c).12/27/202219:32
1/3/2023
22:11定义2显然每个非零整数a都有约数1,a,称这四个数为a的显然因数,a的另外的因数称为非显然因数。若整数a
0,1,并且只有约数1和a,则称a是素数(或质数);否则称a为合数。以后在本书中若无特别说明,素数总是指正素数。12/27/202219:32
1/3/2023
22:11定理2设A={d1,d2,,dk}是n的所有约数的集合,则B=也是n的所有约数的集合。解由以下三点理由可以证得结论:(ⅰ)A和B的元素个数相同;(ⅱ)若diA,即din,则n,反之亦然;(ⅲ)若di
dj,则.12/27/202219:32
1/3/2023
22:11定理3(ⅰ)a>1是合数的充要条件是
a=de,1<d<a,1<e<a;(ⅱ)若d>1,q是不可约数且d|q,则d=q.定理4若a是合数,则必有不可约数p|a.12/27/202219:32
1/3/2023
22:11定理5设整数a≥2,那么a一定可表为素数的乘积(包括a本身是素数),即a=p1p2
ps其中pj(1≤j
≤s)是素数.证明当a=2时,结论显然成立。假设对于2≤
a≤
k,式(1)成立,我们来证明式(1)对于a=k
1也成立,若k
1是素数,式(1)显成立.如果k
1是合数,则存在素数p与整数d,使得k
1=pd.由于2≤
d≤
k,由归纳假定知存在素数q1,q2,,ql,使得d=q1q2ql,从而k
1=pq1q2ql.从而由归纳法推出式(1)对任何大于1的整数a成立。证毕。12/27/202219:32
1/3/2023
22:11推论任何大于1的合数a必有一个不超过a1/2的素因数。证明由于a是合数,故存在整数b和c使a=bc,其中:1<b<a,1<c<a.若b和c均大于a1/2,则a=bc>a1/2·a1/2=a,这是不可能的.因此b和c中必有一个小于或等于a1/2.12/27/202219:32
1/3/2023
22:11例5写出不超过100的所有的素数.解将不超过100的正整数排列如下:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910012/27/202219:32
1/3/2023
22:11按以下步骤进行:(ⅰ)删去1,剩下的后面的第一个数是2,2是素数;(ⅱ)删去2后面的被2整除的数,剩下的2后面的第一个数是3,3是素数;(ⅲ)再删去3后面的被3整除的数,剩下的3后面的第一个数是5,5是素数;(ⅳ)再删去5后面的被5整除的数,剩下的5后面的第一个数是7,7是素数;
照以上步骤可以依次得到素数2,3,5,7,11,.由定理2推论可知,不超过100的合数必有一个不超过10的素约数,因此在删去7后面被7整除的数以后,就得到了不超过100的全部素数.12/27/202219:32
1/3/2023
22:11在例5中所使用的寻找素数的方法,称为Eratosthenes筛法.它可以用来求出不超过任何固定整数的所有素数.在理论上这是可行的;但在实际应用中,这种列出素数的方法需要大量的计算时间,是不可取的.12/27/202219:32
1/3/2023
22:11
定理7.(Euclid)素数有无穷多个.
证明:(反证法)假设素数是有限多个,共有n个,令它们是p1,p2,…,pn,并令a=p1p2…pn+1.若a是素数,则因a≠pi,其中1<i<n,故素数个数最少是n+1个,这与假设素数个数为n个矛盾.若a不是素数,则由定理4知,a的大于1的最小因数b是素数.由于pi|p1p2…pn,但pi不能整除1,故pi不能整除a,因此b≠pi,其中1≤i≤n,那么a也为素数.所以在p1,p2,…,pn,还有素数,这也与已知共有n个素数矛盾.12/27/202219:32
1/3/2023
22:11最大公因数与最小公倍数12/27/202219:32
1/3/2023
22:11定义3最大公因数设al,a2,…,ak和d都是整数,k≥2.若d|ai,1≤i≤k,则称d是al,a2,…,ak的公因数.所有公因数中最大的那一个数,称为al,a2,…,ak的最大公因数,记为(al,a2,…,ak).由于每个非零整数的约数的个数是有限的,所以最大公约数是存在的,并且是正整数。显然,(a,1)=1,(a,0)=|a|,(a,a)=|a|;12/27/202219:32
1/3/2023
22:11定理8下面的等式成立:(ⅰ)(a1,a2)=(a2,a1)=(-a1,a2);一般地(a1,a2,,ai,,ak)=(ai,a2,,a1,,ak)=(-a1,a2,,ak)=(|a1|,|a2|,,|ak|);(ⅱ)若a1|aj,j=2,,k,则(a1,a2)=(a1,a2,,ak)=(a1)=|a1|(ⅲ)对任意整数x,(a1,a2)=(a1,a2,a1x)(a1,,
ak)=(a1,,ak,a1x);(ⅳ)对任意整数x,(a1,a2)=(a1,a2+a1x)(a1,a2,a3,,ak)=(a1,a2+a1x,a3,,ak);(ⅴ)若p是素数,则(p,a)=1或pa;一般地(p,a1,,ak)=1或pa.12/27/202219:32
1/3/2023
22:11例512/27/202219:32
1/3/2023
22:11定义5互素如果(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,反之则不然,例如(2,6,15)=1,但(2,6)=2.12/27/202219:32
1/3/2023
22:11定理9(a1,a2,,ak)=1的充要条件是存在整数x1,x2,,xk,使得a1x1
a2x2
akxk=1.充分性若式(1)成立,如果(a1,a2,,ak)=d
>1,那么由dai(1≤i≤k)推出da1x1
a2x2
akxk=1,这是不可能的.所以有(a1,a2,,ak)=1.证毕.12/27/202219:32
1/3/2023
22:11定理10设正整数m|(a1,a2,,ak).我们有m(a1/m,a2/m,,ak/m)=(a1,a2,,ak)特别地有
=1.12/27/202219:32
1/3/2023
22:11定义6最小公倍数设a1,a2,,ak和m都是整数,k≥2.若ai|m,1≤i≤k,则称m是a1,a2,,ak的公倍数.在a1,a2,,ak所有公倍数中最小的那一个正整数,称为a1,a2,,ak的最小公倍数,记为[a1,a2,,ak].12/27/202219:32
1/3/2023
22:11定理11(ⅰ)[a1,a2]=[a2,a1]=[-a1,a2].一般地有,[a1,a2,,ai
,,
ak]=[ai,a2,,a1,,ak]=[-a1,a2,,ai,,
ak](ⅱ)若a2|a1,则[a1,a2]=|a1|;(ⅲ)对任意的d|a1[a1,a2]=[a1,a2,d][a1,a2,,ak]=[a1,a2,,ak,d]12/27/202219:32
1/3/2023
22:11定理12设m>0,我们有[ma1,…,mak]=m[a1,…,ak]12/27/202219:32
1/3/2023
22:11§3带余除法与辗转相除法12/27/202219:32
1/3/2023
22:11定理1带余数除法设a与b是两个整数,a
0,则存在唯一的两个整数q和r,使得b=aq
r,0≤r≤|a|(1)证明
存在性若ab,b=aq,qZ,可取r=0.若ab,考虑集合A={b
ka;kZ},在集合A中有无限多个正整数,设最小的正整数是r=b
k0a,则必有0<r<|a|,(2)否则就有r≥|a|.因为ab,所以r
|a|.于是r>|a|,即b
k0a>|a|,b
k0a
|a|>0,这样,在集合A中,又有正整数r1=b
k0a
|a|<r,这与r的最小性矛盾。12/27/202219:32
1/3/2023
22:11所以式(2)必定成立.取q=k0知式(1)成立.存在性得证.唯一性假设有两对整数q
、r
与q
、r
都使得式(1)成立,即b=q
a
r
=q
a
r
,0≤
r
,r
≤|a|,则(q
q)a=r
r,|r
r|<|a|,(3)因此r
r=0,r=r,再由式(3)得出q
=q
,唯一性得证.证毕.12/27/202219:32
1/3/2023
22:11定理2设a与b是两个整数,a
0,设d是一给定的整数.那么,一定存在唯一的两个整数q1和r1,使得
b=aq1
r1,d≤r1≤|a|+d(4)此外,ab的充要条件是ar1.12/27/202219:32
1/3/2023
22:11定义1称式(1)中的q是b被a除的商,r是b被a除的最小非负余数。式(4)中的r1统称为余数.由定理1可知,对于给定的整数a,可以按照被a除的余数将所有的整数分成a类。在同一类中的数被a除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。12/27/202219:32
1/3/2023
22:11推论3设a>0.任一整数被a除后所得的最小非负余数是且仅是0,1,…,a-1这a个数中的一个.由此全体整数按被a除后所得的最小非负余数可分为两两不相交的a个类.0moda,1moda,…,(a-1)modaa=2时,全体整数分为两类:0mod2,
1mod212/27/202219:32
1/3/2023
22:11例2(ⅰ)0mod2∩0mod3=0mod6;(ⅱ)1mod2∩1mod3=1mod6;(ⅲ)0mod2∩1mod3=4mod6.例31mod2=1mod6∪3mod6∪5mod612/27/202219:32
1/3/2023
22:11例4
a进位表示
设a
≥2是给定的正整数.那么,任一正整数n必可唯一表为n=rkak+rk-1ak-1+…+r1a+r0,(4)其中整数k
≥0,0≤
rj
≤a-1,(0≤j≤k),rk≠0.这就是正整数的a进位表示.12/27/202219:32
1/3/2023
22:11例5
设a>2是奇数.证明:(ⅰ)一定存在正整数d
≤a-1,使得a|2d-1.(ⅱ)设d0是满足(ⅰ)的最小正整数d.那么,
a|2h-1(h∈N)的充要条件是d0|h.(ⅲ)必有正整数d使得(2d-3,a)=1.12/27/202219:32
1/3/2023
22:11定理4
(Euclid)欧几里德算法.
设a,b是给定的两个整数,b≠0,b
a.我们一定可以重复定理1得到下面的等式:
a=bq1+r1,0<rl<|b|
b=r1q2+r2,0<r2<r1
r1=r2q3+r3,0<r3<r2…….
rn-2=rn-1qn+rn,0<rn<rn-1
rn-1=rnqn+1+0则(a,b)=rn.12/27/202219:32
1/3/2023
22:11证明:由于|b|>r1>r2>…>rn>0,故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式,即rn+1=0.根据前面定理可知:(a,b)=(b,r1)=…=(rn-1,rn)=(rn,0)=rn.欧几里德算法也称辗转相除法.12/27/202219:32
1/3/2023
22:11在Euclid算法中,由:rn=rn-2-rn-1qn,rn-1=rn-3-rn-2qn-1,得rn=rn-2(1+qnqn-1)-rn-3qn,再将rn-2=rn-4-rn-3qn-2代入上式,如此继续下去,最后得到:
rn=sa+tb,其中s和t是整数.于是有(a,b)是a和b线性组合表示定理.定理5
(ⅲ)若任给整数a,b,则存在整数x和y,使得(a,b)=ax+by.容易证明下面结论.(ⅱ)
a和b的公因数整除(a,b).12/27/202219:32
1/3/2023
22:11例6①用欧几里德算法求(1997,57).②用1997和57的线性组合表示(1997,57).③求1997和57的所有公因数.解①用下划线标识余数.1997=57·35+257=2·28+12=l·2+0因此,(1997,57)=l,即1997和57是互素的.12/27/202219:32
1/3/2023
22:11②1=57-2·28=57-(1997-57·35)·28=-28·1997+(57+57·35·28)=-28·1997+981·57③由于1997和57是互素的,公因数只有1和-1.12/27/202219:32
1/3/2023
22:11例7设m,n是正整数.证明(2m-1,2n-1)=2(m,n)-112/27/202219:32
1/3/2023
22:11§4最大公因数理论12/27/202219:32
1/3/2023
22:11定理1
aj|c(1≤j≤k)的充要条件是[a1,…,ak]|c证明:充分性显然.必要性,设[a1,…,ak]=m.c是a1,…,ak的任一公倍数,利用带余除法得:c=mq+r,0≤r<m,aj|c,aj|m,aj|r,(1≤j≤k).故a1|r,…,ak|r,即r是a1,…,ak的公倍数.但由于:1≤r<m与m是a1,…,ak的最小公倍数发生矛盾,故:r=0,即:c=mq.故m|c.即[a1,…,ak]|c12/27/202219:32
1/3/2023
22:11定理2设D是正整数.那么D=(a1,a2,,ak)的充要条件是:(ⅰ)D|aj(1≤j≤k);(ⅱ)若daj(1≤j≤k),则d(a1,a2,,ak).这个结论表明:公约数一定是最大公约数的约数。12/27/202219:32
1/3/2023
22:11
定理3
(ma1,ma2,,mak)
=
|m|(a1,a2,,ak).定理4(ⅰ)(a1,a2
,…,ak)=((
a1,a2),
a3,…,ak);(ⅱ)(a1,a2
,…,ak+r)=((
a1,…,ak
),(ak+1,…,ak+r));推论(a1,a2)(b1,b2)=(a1b1,a1b2,a2b1,a2b2)12/27/202219:32
1/3/2023
22:11定理5若(m,a)
=
1,则(m,ab)
=
(m,b).证明:(m,b)=(m,(m,a)b)=(m,mb,ab)=(m,ab).推论若(a,bi)
=
1,1≤i≤n,则(a,b1b2bn)
=
1.12/27/202219:32
1/3/2023
22:11定理6对于任意的整数a,b,m,下面的结论成立:(ⅰ)由mab及(m,a)
=
1可以推出mb;(ⅱ)由m1n,m2n及(m1,m2)
=
1可以推出m1m2n.一般地,若m1,m2,,mk两两互素,及mjn(1≤j≤k),则m1
m2
mkn.证明:
(ⅰ)(m,a)
=
1,则(m,ab)
=
(m,b),由mab,(m,ab)=|m|,故(m,b)=|m|,从而mb.(ⅱ)
m1n知n=m1n1,m2n,即m2m1n1,又(m1,m2)
=
1,知m2n1,因而m1m2n.12/27/202219:32
1/3/2023
22:11定理7设a1和a2是正整数,且(a1,a2)=d,[a1,a2]=m,则a1a2=md.12/27/202219:32
1/3/2023
22:11例1设p是素数.证明:(ⅰ)p|,1≤j≤p-1(ⅱ)对任意的正整数a,p|ap-a;(ⅲ)若(p,a)=1,则p|ap-1-1.例2证明:(ⅰ)(a,uv)=(a,(a,u)v);(ⅱ)
(a,uv)|(a,u)(a,v)12/27/202219:32
1/3/2023
22:11例3设k是正整数.若一个有理数的k次方是整数,那么,这个有理数一定是整数.12/27/202219:32
1/3/2023
22:11数论的基本内容按照研究方法的不同,数论可分为初等数论解析数论代数数论几何数论12/27/202219:32
1/3/2023
22:11参考书目1、南基洙主编《初等数论》;2、柯召、孙琦编著《数论讲义》,高等教育出版社;3、闵嗣鹤、严士健编《初等数论》,高等教育出版社;4、郑克明主编《初等数论》,西南师范大学出版社。12/27/202219:32
1/3/2023
22:11初等数论第一章整除
§1自然数与整数12/27/202219:32
1/3/2023
22:11归纳原理设S是N的一个子集,满足条件:(ⅰ)1∈S;(ⅱ)如果n∈S,则n+1∈S,那么,S=N.12/27/202219:32
1/3/2023
22:11定理1数学归纳法
设P(n)是关于自然数n的一种性质或命题.如果(ⅰ)当n=1时,P(1)成立;(ⅱ)由P(n)成立必可推出P(n+1)成立,那么,P(n)对所有自然数n成立.12/27/202219:32
1/3/2023
22:11定理2最小自然数原理设T是N的一个非空子集.那么,必有t0∈T,使对任意的t
∈T有t0≤t,即t0是T中的最小自然数.12/27/202219:32
1/3/2023
22:11定理3最大自然数原理设M是N的非空子集.若M有上界,即存在
a∈N,使对任意的m∈M有m
≤a,那么必有m0∈M,使对任意的m∈M有m≤m0,即m0是M中的最大自然数。12/27/202219:32
1/3/2023
22:11定理4第二数学归纳法设P(n)是关于自然数n的一种性质或命题.如果(ⅰ)当n=1时,P(1)成立;(ⅱ)设n>1.若对所有的自然数m<n,P(m)成立,则必可推出P(n)成立,那么,P(n)对所有自然数n成立.12/27/202219:32
1/3/2023
22:11定理5鸽巢原理设n是一个自然数.现有n个盒子和n+1个物体.无论怎样把这n+1个物体放入这n个盒子中,一定有一个盒子中被放了两个或两个以上的物体。12/27/202219:32
1/3/2023
22:11§2整除12/27/202219:32
1/3/2023
22:11定义1设a,b是整数,a
0,如果存在整数q,使得b=aq,则称b可被a整除,记作ab,且称b是a的倍数,a是b的约数(因数、除数);如果不存在整数q使得b=aq成立,则称b不被a整除,记为ab。被2整除的数称为偶数,不被2整除的称为奇数
12/27/202219:32
1/3/2023
22:11定理1下面的结论成立:(ⅰ)
a|b(-a)|b
a|(-b)(-a)|(-b)|a|||b|;(ⅱ)
ab,bcac;(ⅲ)
ab,ac对任意x、y,有abx+cy,一般地,abi,i=1,2,,kab1x1
b2x2
bkxk,此处xi(i=1,2,,k)是任意的整数;(ⅳ)
abacbc,c是任意的非零整数;(ⅴ)
ab且ba
a=
b;(ⅵ)
ab,b
0|a|≤|b|;ab且|b|<|a|
b=0.12/27/202219:32
1/3/2023
22:11例1证明:若3|n且7|n,则21|n.例2设a=2t-1.若a|2n,则a|n.例3设a、b是两个给定的非零整数,且有整数x、y,使得ax+by=1.证明:若a|n且b|n,则ab|n.例4设f(x)=anxn+an-1xn-1++a1x+a0
∈Z[x],其中Z[x]表示全体一元整系数多项式组成的集合.若d|b-c,则d|f(b)-f(c).12/27/202219:32
1/3/2023
22:11定义2显然每个非零整数a都有约数1,a,称这四个数为a的显然因数,a的另外的因数称为非显然因数。若整数a
0,1,并且只有约数1和a,则称a是素数(或质数);否则称a为合数。以后在本书中若无特别说明,素数总是指正素数。12/27/202219:32
1/3/2023
22:11定理2设A={d1,d2,,dk}是n的所有约数的集合,则B=也是n的所有约数的集合。解由以下三点理由可以证得结论:(ⅰ)A和B的元素个数相同;(ⅱ)若diA,即din,则n,反之亦然;(ⅲ)若di
dj,则.12/27/202219:32
1/3/2023
22:11定理3(ⅰ)a>1是合数的充要条件是
a=de,1<d<a,1<e<a;(ⅱ)若d>1,q是不可约数且d|q,则d=q.定理4若a是合数,则必有不可约数p|a.12/27/202219:32
1/3/2023
22:11定理5设整数a≥2,那么a一定可表为素数的乘积(包括a本身是素数),即a=p1p2
ps其中pj(1≤j
≤s)是素数.证明当a=2时,结论显然成立。假设对于2≤
a≤
k,式(1)成立,我们来证明式(1)对于a=k
1也成立,若k
1是素数,式(1)显成立.如果k
1是合数,则存在素数p与整数d,使得k
1=pd.由于2≤
d≤
k,由归纳假定知存在素数q1,q2,,ql,使得d=q1q2ql,从而k
1=pq1q2ql.从而由归纳法推出式(1)对任何大于1的整数a成立。证毕。12/27/202219:32
1/3/2023
22:11推论任何大于1的合数a必有一个不超过a1/2的素因数。证明由于a是合数,故存在整数b和c使a=bc,其中:1<b<a,1<c<a.若b和c均大于a1/2,则a=bc>a1/2·a1/2=a,这是不可能的.因此b和c中必有一个小于或等于a1/2.12/27/202219:32
1/3/2023
22:11例5写出不超过100的所有的素数.解将不超过100的正整数排列如下:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910012/27/202219:32
1/3/2023
22:11按以下步骤进行:(ⅰ)删去1,剩下的后面的第一个数是2,2是素数;(ⅱ)删去2后面的被2整除的数,剩下的2后面的第一个数是3,3是素数;(ⅲ)再删去3后面的被3整除的数,剩下的3后面的第一个数是5,5是素数;(ⅳ)再删去5后面的被5整除的数,剩下的5后面的第一个数是7,7是素数;
照以上步骤可以依次得到素数2,3,5,7,11,.由定理2推论可知,不超过100的合数必有一个不超过10的素约数,因此在删去7后面被7整除的数以后,就得到了不超过100的全部素数.12/27/202219:32
1/3/2023
22:11在例5中所使用的寻找素数的方法,称为Eratosthenes筛法.它可以用来求出不超过任何固定整数的所有素数.在理论上这是可行的;但在实际应用中,这种列出素数的方法需要大量的计算时间,是不可取的.12/27/202219:32
1/3/2023
22:11
定理7.(Euclid)素数有无穷多个.
证明:(反证法)假设素数是有限多个,共有n个,令它们是p1,p2,…,pn,并令a=p1p2…pn+1.若a是素数,则因a≠pi,其中1<i<n,故素数个数最少是n+1个,这与假设素数个数为n个矛盾.若a不是素数,则由定理4知,a的大于1的最小因数b是素数.由于pi|p1p2…pn,但pi不能整除1,故pi不能整除a,因此b≠pi,其中1≤i≤n,那么a也为素数.所以在p1,p2,…,pn,还有素数,这也与已知共有n个素数矛盾.12/27/202219:32
1/3/2023
22:11最大公因数与最小公倍数12/27/202219:32
1/3/2023
22:11定义3最大公因数设al,a2,…,ak和d都是整数,k≥2.若d|ai,1≤i≤k,则称d是al,a2,…,ak的公因数.所有公因数中最大的那一个数,称为al,a2,…,ak的最大公因数,记为(al,a2,…,ak).由于每个非零整数的约数的个数是有限的,所以最大公约数是存在的,并且是正整数。显然,(a,1)=1,(a,0)=|a|,(a,a)=|a|;12/27/202219:32
1/3/2023
22:11定理8下面的等式成立:(ⅰ)(a1,a2)=(a2,a1)=(-a1,a2);一般地(a1,a2,,ai,,ak)=(ai,a2,,a1,,ak)=(-a1,a2,,ak)=(|a1|,|a2|,,|ak|);(ⅱ)若a1|aj,j=2,,k,则(a1,a2)=(a1,a2,,ak)=(a1)=|a1|(ⅲ)对任意整数x,(a1,a2)=(a1,a2,a1x)(a1,,
ak)=(a1,,ak,a1x);(ⅳ)对任意整数x,(a1,a2)=(a1,a2+a1x)(a1,a2,a3,,ak)=(a1,a2+a1x,a3,,ak);(ⅴ)若p是素数,则(p,a)=1或pa;一般地(p,a1,,ak)=1或pa.12/27/202219:32
1/3/2023
22:11例512/27/202219:32
1/3/2023
22:11定义5互素如果(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,反之则不然,例如(2,6,15)=1,但(2,6)=2.12/27/202219:32
1/3/2023
22:11定理9(a1,a2,,ak)=1的充要条件是存在整数x1,x2,,xk,使得a1x1
a2x2
akxk=1.充分性若式(1)成立,如果(a1,a2,,ak)=d
>1,那么由dai(1≤i≤k)推出da1x1
a2x2
akxk=1,这是不可能的.所以有(a1,a2,,ak)=1.证毕.12/27/202219:32
1/3/2023
22:11定理10设正整数m|(a1,a2,,ak).我们有m(a1/m,a2/m,,ak/m)=(a1,a2,,ak)特别地有
=1.12/27/202219:32
1/3/2023
22:11定义6最小公倍数设a1,a2,,ak和m都是整数,k≥2.若ai|m,1≤i≤k,则称m是a1,a2,,ak的公倍数.在a1,a2,,ak所有公倍数中最小的那一个正整数,称为a1,a2,,ak的最小公倍数,记为[a1,a2,,ak].12/27/202219:32
1/3/2023
22:11定理11(ⅰ)[a1,a2]=[a2,a1]=[-a1,a2].一般地有,[a1,a2,,ai
,,
ak]=[ai,a2,,a1,,ak]=[-a1,a2,,ai,,
ak](ⅱ)若a2|a1,则[a1,a2]=|a1|;(ⅲ)对任意的d|a1[a1,a2]=[a1,a2,d][a1,a2,,ak]=[a1,a2,,ak,d]12/27/202219:32
1/3/2023
22:11定理12设m>0,我们有[ma1,…,mak]=m[a1,…,ak]12/27/202219:32
1/3/2023
22:11§3带余除法与辗转相除法12/27/202219:32
1/3/2023
22:11定理1带余数除法设a与b是两个整数,a
0,则存在唯一的两个整数q和r,使得b=aq
r,0≤r≤|a|(1)证明
存在性若ab,b=aq,qZ,可取r=0.若ab,考虑集合A={b
ka;kZ},在集合A中有无限多个正整数,设最小的正整数是r=b
k0a,则必有0<r<|a|,(2)否则就有r≥|a|.因为ab,所以r
|a|.于是r>|a|,即b
k0a>|a|,b
k0a
|a|>0,这样,在集合A中,又有正整数r1=b
k0a
|a|<r,这与r的最小性矛盾。12/27/202219:32
1/3/2023
22:11所以式(2)必定成立.取q=k0知式(1)成立.存在性得证.唯一性假设有两对整数q
、r
与q
、r
都使得式(1)成立,即b=q
a
r
=q
a
r
,0≤
r
,r
≤|a|,则(q
q)a=r
r,|r
r|<|a|,(3)因此r
r=0,r=r,再由式(3)得出q
=q
,唯一性得证.证毕.12/27/202219:32
1/3/2023
22:11定理2设a与b是两个整数,a
0,设d是一给定的整数.那么,一定存在唯一的两个整数q1和r1,使得
b=aq1
r1,d≤r1≤|a|+d(4)此外,ab的充要条件是ar1.12/27/202219:32
1/3/2023
22:11定义1称式(1)中的q是b被a除的商,r是b被a除的最小非负余数。式(4)中的r1统称为余数.由定理1可知,对于给定的整数a,可以按照被a除的余数将所有的整数分成a类。在同一类中的数被a除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。12/27/202219:32
1/3/2023
22:11推论3设a>0.任一整数被a除后所得的最小非负余数是且仅是0,1,…,a-1这a个数中的一个.由此全体整数按被a除后所得的最小非负余数可分为两两不相交的a个类.0moda,1moda,…,(a-1)modaa=2时,全体整数分为两类:0mod2,
1mod212/27/202219:32
1/3/2023
22:11例2(ⅰ)0mod2∩0mod3=0mod6;(ⅱ)1mod2∩1mod3=1mod6;(ⅲ)0mod2∩1mod3=4mod6.例31mod2=1mod6∪3mod6∪5mod612/27/202219:32
1/3/2023
22:11例4
a进位表示
设a
≥2是给定的正整数.那么,任一正整数n必可唯一表为n=rkak+rk-1ak-1+…+r1a+r0,(4)其中整数k
≥0,0≤
rj
≤a-1,(0≤j≤k),rk≠0.这就是正整数的a进位表示.12/27/202219:32
1/3/2023
22:11例5
设a>2是奇数.证明:(ⅰ)一定存在正整数d
≤a-1,使得a|2d-1.(ⅱ)设d0是满足(ⅰ)的最小正整数d.那么,
a|2h-1(h∈N)的充要条件是d0|h.(ⅲ)必有正整数d使得(2d-3,a)=1.12/27/202219:32
1/3/2023
22:11定理4
(Euclid)欧几里德算法.
设a,b是给定的两个整数,b≠0,b
a.我们一定可以重复定理1得到下面的等式:
a=bq1+r1,0<rl<|b|
b=r1q2+r2,0<r2<r1
r1=r2q3+r3,0<r3<r2…….
rn-2=rn-1qn+rn,0<rn<rn-1
rn-1=rnqn+1+0则(a,b)=rn.12/27/202219:32
1/3/2023
22:11证明:由于|b|>r1>r2>…>rn>0,故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式,即rn+1=0.根据前面定理可知:(a,b)=(b,r1)=…=(rn-1,rn)=(rn,0)=rn.欧几里德算法也称辗转相除法.12/27/202219:32
1/3/2023
22:11在Euclid算法中,由:rn=rn-2-rn-1qn,rn-1=rn-3-rn-2qn-1,得rn=rn-2
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 酒店维修零星工程协议
- 地下停车场安全施工协议
- 转让限价房合同样本
- 水利工程文件规划
- 酒店大堂科技展览租赁合同
- 地下车库彩绘施工合同
- 舞蹈兼职教师聘用合同范本
- 林业保护新司机劳动合同
- 连锁店管理指南供应链管理
- 外籍市场营销专家聘用合同
- 2024年消防月主题培训课件:全民消防 生命至上(含11月火灾事故)
- 人教版(2024年新版)七年级数学上册期中模拟测试卷(含答案)
- 2023年度学校食堂食品从业人员考核试题(附答案)
- 2024广西公需课高质量共建“一带一路”谱写人类命运共同体新篇章答案
- 2024年连云港专业技术人员继续教育《饮食、运动和健康的关系》92分(试卷)
- 2024年安徽合肥交通投资控股有限公司招聘笔试参考题库含答案解析
- 说教材说目标-《长方形和正方形》单元说课一等奖
- 2022-2023年度中国家族财富可持续发展报告
- 收款确认函-模板(共2页)
- 老年服务伦理与礼仪课件
- 称骨歌及说明
评论
0/150
提交评论