初等數(shù)論第一章整除課件

8/23/2023

12:39數(shù)論的基本內(nèi)容按照研究方法的不同，數(shù)論可分為初等數(shù)論解析數(shù)論代數(shù)數(shù)論幾何數(shù)論8/2/202319:12數(shù)論

8/23/2023

12:39參考書(shū)目1、南基洙主編《初等數(shù)論》；2、柯召、孫琦編著《數(shù)論講義》，高等教育出版社；3、閔嗣鶴、嚴(yán)士健編《初等數(shù)論》，高等教育出版社；4、鄭克明主編《初等數(shù)論》，西南師范大學(xué)出版社。8/2/202319:12參考

8/23/2023

12:39初等數(shù)論第一章整除

§1自然數(shù)與整數(shù)8/2/202319:12初等

8/23/2023

12:39歸納原理設(shè)S是N的一個(gè)子集，滿足條件：(ⅰ)1∈S;(ⅱ)如果n∈S，則n+1∈S,那么，S=N.8/2/202319:12歸納

8/23/2023

12:39定理1數(shù)學(xué)歸納法

設(shè)P(n)是關(guān)于自然數(shù)n的一種性質(zhì)或命題.如果(ⅰ)當(dāng)n=1時(shí)，P(1)成立；(ⅱ)由P(n)成立必可推出P(n+1)成立，那么，P(n)對(duì)所有自然數(shù)n成立.8/2/202319:12定理

8/23/2023

12:39定理2最小自然數(shù)原理設(shè)T是N的一個(gè)非空子集.那么，必有t0∈T,使對(duì)任意的t

∈T有t0≤t，即t0是T中的最小自然數(shù).8/2/202319:12定理

8/23/2023

12:39定理3最大自然數(shù)原理設(shè)M是N的非空子集.若M有上界，即存在

a∈N,使對(duì)任意的m∈M有m

≤a,那么必有m0∈M，使對(duì)任意的m∈M有m≤m0，即m0是M中的最大自然數(shù)。8/2/202319:12定理

8/23/2023

12:39定理4第二數(shù)學(xué)歸納法設(shè)P(n)是關(guān)于自然數(shù)n的一種性質(zhì)或命題.如果(ⅰ)當(dāng)n=1時(shí)，P(1)成立；(ⅱ)設(shè)n>1.若對(duì)所有的自然數(shù)m<n,P(m)成立，則必可推出P(n)成立，那么,P(n)對(duì)所有自然數(shù)n成立.8/2/202319:12定理

8/23/2023

12:39定理5鴿巢原理設(shè)n是一個(gè)自然數(shù).現(xiàn)有n個(gè)盒子和n+1個(gè)物體.無(wú)論怎樣把這n+1個(gè)物體放入這n個(gè)盒子中，一定有一個(gè)盒子中被放了兩個(gè)或兩個(gè)以上的物體。8/2/202319:12定理

8/23/2023

12:39§2整除8/2/202319:12§2

8/23/2023

12:39定義1設(shè)a，b是整數(shù)，a

0，如果存在整數(shù)q，使得b=aq，則稱b可被a整除，記作a

b，且稱b是a的倍數(shù)，a是b的約數(shù)(因數(shù)、除數(shù))；如果不存在整數(shù)q使得b=aq成立，則稱b不被a整除，記為ab。被2整除的數(shù)稱為偶數(shù)，不被2整除的稱為奇數(shù)

8/2/202319:12定義

8/23/2023

12:39定理1下面的結(jié)論成立：(ⅰ)

a|b(-a)|b

a|(-b)(-a)|(-b)|a|||b|；(ⅱ)

a

b，b

c

a

c；(ⅲ)

a

b,a

c對(duì)任意x、y,有a

bx+cy,一般地，a

bi，i=1,2,

,ka

b1x1

b2x2

bkxk，此處xi（i=1,2,

,k）是任意的整數(shù)；(ⅳ)

a

bac

bc，c是任意的非零整數(shù)；(ⅴ)

a

b且b

a

a=

b；(ⅵ)

a

b，b

0

|a|≤|b|；a

b且|b|<|a|

b=0.8/2/202319:12定理

8/23/2023

12:39例1證明：若3|n且7|n，則21|n.例2設(shè)a=2t-1.若a|2n,則a|n.例3設(shè)a、b是兩個(gè)給定的非零整數(shù)，且有整數(shù)x、y，使得ax+by=1.證明：若a|n且b|n,則ab|n.例4設(shè)f(x)=anxn+an-1xn-1++a1x+a0

∈Z[x],其中Z[x]表示全體一元整系數(shù)多項(xiàng)式組成的集合.若d|b-c,則d|f(b)-f(c).8/2/202319:12例1

8/23/2023

12:39定義2顯然每個(gè)非零整數(shù)a都有約數(shù)

1，

a，稱這四個(gè)數(shù)為a的顯然因數(shù)，a的另外的因數(shù)稱為非顯然因數(shù)。若整數(shù)a

0，

1，并且只有約數(shù)

1和

a，則稱a是素?cái)?shù)（或質(zhì)數(shù)）；否則稱a為合數(shù)。以后在本書(shū)中若無(wú)特別說(shuō)明，素?cái)?shù)總是指正素?cái)?shù)。8/2/202319:12定義

8/23/2023

12:39定理2設(shè)A={d1,d2,

,dk}是n的所有約數(shù)的集合，則B=也是n的所有約數(shù)的集合。解由以下三點(diǎn)理由可以證得結(jié)論：(ⅰ)A和B的元素個(gè)數(shù)相同；(ⅱ)若di

A，即di

n，則n，反之亦然；(ⅲ)若di

dj，則.8/2/202319:12定理

8/23/2023

12:39定理3(ⅰ)a>1是合數(shù)的充要條件是

a=de,1<d<a,1<e<a;(ⅱ)若d>1,q是不可約數(shù)且d|q,則d=q.定理4若a是合數(shù)，則必有不可約數(shù)p|a.8/2/202319:12定理

8/23/2023

12:39定理5設(shè)整數(shù)a≥2,那么a一定可表為素?cái)?shù)的乘積(包括a本身是素?cái)?shù))，即a=p1p2

ps其中pj（1≤j

≤s)是素?cái)?shù).證明當(dāng)a=2時(shí)，結(jié)論顯然成立。假設(shè)對(duì)于2≤

a≤

k，式(1)成立，我們來(lái)證明式(1)對(duì)于a=k

1也成立，若k

1是素?cái)?shù)，式(1)顯成立.如果k

1是合數(shù)，則存在素?cái)?shù)p與整數(shù)d，使得k

1=pd.由于2≤

d≤

k，由歸納假定知存在素?cái)?shù)q1,q2,,ql，使得d=q1q2

ql，從而k

1=pq1q2

ql.從而由歸納法推出式(1)對(duì)任何大于1的整數(shù)a成立。證畢。8/2/202319:12定理

8/23/2023

12:39推論任何大于1的合數(shù)a必有一個(gè)不超過(guò)a1/2的素因數(shù)。證明由于a是合數(shù)，故存在整數(shù)b和c使a＝bc,其中:1<b<a,1<c<a.若b和c均大于a1/2,則a＝bc＞a1/2·a1/2＝a,這是不可能的.因此b和c中必有一個(gè)小于或等于a1/2.8/2/202319:12推論

8/23/2023

12:39例5寫(xiě)出不超過(guò)100的所有的素?cái)?shù).解將不超過(guò)100的正整數(shù)排列如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991008/2/202319:12例5

8/23/2023

12:39按以下步驟進(jìn)行：(ⅰ)刪去1，剩下的后面的第一個(gè)數(shù)是2，2是素?cái)?shù)；(ⅱ)刪去2后面的被2整除的數(shù)，剩下的2后面的第一個(gè)數(shù)是3，3是素?cái)?shù)；(ⅲ)再刪去3后面的被3整除的數(shù)，剩下的3后面的第一個(gè)數(shù)是5，5是素?cái)?shù)；(ⅳ)再刪去5后面的被5整除的數(shù)，剩下的5后面的第一個(gè)數(shù)是7，7是素?cái)?shù)；

照以上步驟可以依次得到素?cái)?shù)2,3,5,7,11,

.由定理2推論可知，不超過(guò)100的合數(shù)必有一個(gè)不超過(guò)10的素約數(shù)，因此在刪去7后面被7整除的數(shù)以后，就得到了不超過(guò)100的全部素?cái)?shù).8/2/202319:12按以

8/23/2023

12:39在例5中所使用的尋找素?cái)?shù)的方法,稱為Eratosthenes篩法.它可以用來(lái)求出不超過(guò)任何固定整數(shù)的所有素?cái)?shù).在理論上這是可行的；但在實(shí)際應(yīng)用中，這種列出素?cái)?shù)的方法需要大量的計(jì)算時(shí)間，是不可取的.8/2/202319:12在例

8/23/2023

12:39

定理7.(Euclid)素?cái)?shù)有無(wú)窮多個(gè).

證明：(反證法)假設(shè)素?cái)?shù)是有限多個(gè),共有n個(gè),令它們是p1,p2,…,pn,并令a=p1p2…pn+1.若a是素?cái)?shù),則因a≠pi，其中1<i<n,故素?cái)?shù)個(gè)數(shù)最少是n+1個(gè),這與假設(shè)素?cái)?shù)個(gè)數(shù)為n個(gè)矛盾.若a不是素?cái)?shù),則由定理4知,a的大于1的最小因數(shù)b是素?cái)?shù).由于pi|p1p2…pn,但pi不能整除1,故pi不能整除a,因此b≠pi,其中1≤i≤n,那么a也為素?cái)?shù).所以在p1,p2,…,pn,還有素?cái)?shù),這也與已知共有n個(gè)素?cái)?shù)矛盾.8/2/202319:12

定

8/23/2023

12:39最大公因數(shù)與最小公倍數(shù)8/2/202319:12最大

8/23/2023

12:39定義3最大公因數(shù)設(shè)al,a2,…,ak和d都是整數(shù),k≥2.若d|ai，1≤i≤k,則稱d是al,a2,…,ak的公因數(shù).所有公因數(shù)中最大的那一個(gè)數(shù)，稱為al,a2,…,ak的最大公因數(shù),記為(al,a2,…,ak).由于每個(gè)非零整數(shù)的約數(shù)的個(gè)數(shù)是有限的，所以最大公約數(shù)是存在的，并且是正整數(shù)。顯然，(a,1)=1，(a,0)=|a|，(a,a)=|a|；8/2/202319:12定義

8/23/2023

12:39定理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|(ⅲ)對(duì)任意整數(shù)x，(a1,a2)=(a1,a2,a1x)(a1,,

ak)=(a1,

,ak,a1x)；(ⅳ)對(duì)任意整數(shù)x,（a1,a2)=(a1,a2+a1x)(a1,a2,a3,,ak)=(a1,a2+a1x,a3,,ak)；(ⅴ)若p是素?cái)?shù),則(p,a)=1或p

a；一般地（p,a1,

,ak)=1或p

a.8/2/202319:12定理

8/23/2023

12:39例58/2/202319:12例5

8/23/2023

12:39定義5互素如果(a1,a2,

,ak)=1，則稱a1,a2,

,ak是互素的（或互質(zhì)的）；如果(ai,aj)=1，1≤i,j≤k，i

j，則稱a1,a2,

,ak是兩兩互素的（或兩兩互質(zhì)的）.顯然，a1,a2,

,ak兩兩互素可以推出(a1,a2,

,ak)=1，反之則不然，例如(2,6,15)=1，但(2,6)=2.8/2/202319:12定義

8/23/2023

12:39定理9(a1,a2,

,ak)=1的充要條件是存在整數(shù)x1,x2,

,xk，使得a1x1

a2x2

akxk=1.充分性若式(1)成立，如果(a1,a2,

,ak)=d

>1，那么由d

ai（1≤i≤k）推出d

a1x1

a2x2

akxk=1，這是不可能的.所以有(a1,a2,

,ak)=1.證畢.8/2/202319:12定理

8/23/2023

12:39定理10設(shè)正整數(shù)m|(a1,a2,

,ak).我們有m(a1/m,a2/m,

,ak/m)=(a1,a2,

,ak)特別地有

=1.8/2/202319:12定理

8/23/2023

12:39定義6最小公倍數(shù)設(shè)a1,a2,

,ak和m都是整數(shù),k≥2.若ai|m,1≤i≤k,則稱m是a1,a2,

,ak的公倍數(shù).在a1,a2,

,ak所有公倍數(shù)中最小的那一個(gè)正整數(shù),稱為a1,a2,

,ak的最小公倍數(shù),記為[a1,a2,

,ak].8/2/202319:12定義

8/23/2023

12:39定理11(ⅰ)[a1,a2]=[a2,a1]=[-a1,a2].一般地有,[a1,a2,

,ai

,,

ak]=[ai,a2,

,a1,,ak]=[-a1,a2,

,ai,,

ak](ⅱ)若a2|a1,則[a1,a2]=|a1|；(ⅲ)對(duì)任意的d|a1[a1,a2]=[a1,a2,d][a1,a2,

,ak]=[a1,a2,

,ak,d]8/2/202319:12定理

8/23/2023

12:39定理12設(shè)m>0,我們有[ma1,…,mak]=m[a1,…,ak]8/2/202319:12定理

8/23/2023

12:39§3帶余除法與輾轉(zhuǎn)相除法8/2/202319:12§3

8/23/2023

12:39定理1帶余數(shù)除法設(shè)a與b是兩個(gè)整數(shù)，a

0,則存在唯一的兩個(gè)整數(shù)q和r，使得b=aq

r，0≤r≤|a|(1)證明

存在性若a

b，b=aq，q

Z，可取r=0.若ab，考慮集合A={b

ka；k

Z}，在集合A中有無(wú)限多個(gè)正整數(shù)，設(shè)最小的正整數(shù)是r=b

k0a，則必有0<r<|a|，(2)否則就有r≥|a|.因?yàn)閍b，所以r

|a|.于是r>|a|，即b

k0a>|a|，b

k0a

|a|>0，這樣,在集合A中,又有正整數(shù)r1=b

k0a

|a|<r，這與r的最小性矛盾。8/2/202319:12定理

8/23/2023

12:39所以式(2)必定成立.取q=

k0知式(1)成立.存在性得證.唯一性假設(shè)有兩對(duì)整數(shù)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

，唯一性得證.證畢.8/2/202319:12所以

8/23/2023

12:39定理2設(shè)a與b是兩個(gè)整數(shù)，a

0，設(shè)d是一給定的整數(shù).那么，一定存在唯一的兩個(gè)整數(shù)q1和r1，使得

b=aq1

r1，d≤r1≤|a|+d(4)此外，a

b的充要條件是a

r1.8/2/202319:12定理

8/23/2023

12:39定義1稱式(1)中的q是b被a除的商，r是b被a除的最小非負(fù)余數(shù)。式(4)中的r1統(tǒng)稱為余數(shù).由定理1可知，對(duì)于給定的整數(shù)a，可以按照被a除的余數(shù)將所有的整數(shù)分成a類。在同一類中的數(shù)被a除的余數(shù)相同。這就使得許多關(guān)于全體整數(shù)的問(wèn)題可以歸化為對(duì)有限個(gè)整數(shù)類的研究。8/2/202319:12定義

8/23/2023

12:39推論3設(shè)a>0.任一整數(shù)被a除后所得的最小非負(fù)余數(shù)是且僅是0,1,…,a-1這a個(gè)數(shù)中的一個(gè).由此全體整數(shù)按被a除后所得的最小非負(fù)余數(shù)可分為兩兩不相交的a個(gè)類.0moda,1moda,…,(a-1)modaa=2時(shí)，全體整數(shù)分為兩類：0mod2，

1mod28/2/202319:12推論

8/23/2023

12:39例2(ⅰ)0mod2∩0mod3=0mod6;(ⅱ)1mod2∩1mod3=1mod6；(ⅲ)0mod2∩1mod3=4mod6.例31mod2=1mod6∪3mod6∪5mod68/2/202319:12例2

8/23/2023

12:39例4

a進(jìn)位表示

設(shè)a

≥2是給定的正整數(shù).那么，任一正整數(shù)n必可唯一表為n=rkak+rk-1ak-1+…+r1a+r0,(4)其中整數(shù)k

≥0，0≤

rj

≤a-1，(0≤j≤k)，rk≠0.這就是正整數(shù)的a進(jìn)位表示.8/2/202319:12例4

8/23/2023

12:39例5

設(shè)a>2是奇數(shù).證明：(ⅰ)一定存在正整數(shù)d

≤a-1,使得a|2d-1.(ⅱ)設(shè)d0是滿足(ⅰ)的最小正整數(shù)d.那么，

a|2h-1(h∈N)的充要條件是d0|h.(ⅲ)必有正整數(shù)d使得（2d-3,a)=1.8/2/202319:12例5

8/23/2023

12:39定理4

(Euclid)歐幾里德算法.

設(shè)a,b是給定的兩個(gè)整數(shù)，b≠0,b

a.我們一定可以重復(fù)定理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.8/2/202319:12定理

8/23/2023

12:39證明:由于|b|＞r1＞r2＞…＞rn＞0,故歐幾里德算法中的帶余除法必在有限步內(nèi)得到一個(gè)余數(shù)是零的等式,即rn+1=0.根據(jù)前面定理可知：(a,b)=(b,r1)=…=(rn-1,rn)=(rn,0)=rn.歐幾里德算法也稱輾轉(zhuǎn)相除法.8/2/202319:12證明

8/23/2023

12:39在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代入上式,如此繼續(xù)下去,最后得到:

rn=sa+tb,其中s和t是整數(shù).于是有(a,b)是a和b線性組合表示定理.定理5

(ⅲ)若任給整數(shù)a,b,則存在整數(shù)x和y,使得(a,b)=ax+by.容易證明下面結(jié)論．(ⅱ)

a和b的公因數(shù)整除(a,b).8/2/202319:12在E

8/23/2023

12:39例6①用歐幾里德算法求(1997,57).②用1997和57的線性組合表示(1997,57)．③求1997和57的所有公因數(shù)．解①用下劃線標(biāo)識(shí)余數(shù)．1997＝57·35+257＝2·28+12＝l·2+0因此,(1997,57)=l,即1997和57是互素的.8/2/202319:12例6

8/23/2023

12:39②1=57-2·28=57-(1997-57·35)·28=-28·1997+(57+57·35·28）=-28·1997+981·57③由于1997和57是互素的,公因數(shù)只有1和-1.8/2/202319:12②

8/23/2023

12:39例7設(shè)m,n是正整數(shù).證明（2m-1,2n-1)=2(m,n)-18/2/202319:12例7

8/23/2023

12:39§4最大公因數(shù)理論8/2/202319:12§4

8/23/2023

12:39定理1

aj|c(1≤j≤k)的充要條件是[a1,…,ak]|c證明：充分性顯然.必要性，設(shè)[a1,…,ak]=m.c是a1,…,ak的任一公倍數(shù),利用帶余除法得:c=mq+r,0≤r<m,aj|c,aj|m,aj|r,(1≤j≤k).故a1|r,…,ak|r,即r是a1,…,ak的公倍數(shù).但由于:1≤r＜m與m是a1,…,ak的最小公倍數(shù)發(fā)生矛盾,故:r=0,即:c＝mq.故m|c.即[a1,…,ak]|c8/2/202319:12定理

8/23/2023

12:39定理2設(shè)D是正整數(shù).那么D=（a1,a2,

,ak）的充要條件是：(ⅰ)D|aj(1≤j≤k);(ⅱ)若d

aj(1≤j≤k),則d

(a1,a2,

,ak).這個(gè)結(jié)論表明：公約數(shù)一定是最大公約數(shù)的約數(shù)。8/2/202319:12定理

8/23/2023

12:39

定理3

(ma1,ma2,

,mak)

=

|m|(a1,a2,

,ak).定理4(ⅰ)(a1,a2

,…,ak)=((

a1,a2),