第一章整數(shù)的可除性第一章整數(shù)的可除性第一章整數(shù)的可除性第一章整數(shù)的可除性--PAGE11---PAGE12-第一章整數(shù)的可除性§1整除整數(shù)集對于加、減、乘三種運(yùn)算都是封閉的，但是對于除法運(yùn)算不封閉。為此，我們引進(jìn)整除的概念。1a,b∈Z，b≠0q∈Za=bqb整除a或a被bbab為a（約數(shù)a為b如果不存在滿足等式=bq的整數(shù)qb不能整除a或a不被bb|a。1a,b,c∈Z，b≠0，c≠0，則c|b，b|ac|a；b|abc|ac；反之亦真；c|a，c|bm,n∈Zc|(ma+nb)；（4）如果b|a，a≠0，那么|b|≤|a|；（5）如果b|a，a|b，那么|b|=|a|。證明可選證。帶余除法）設(shè)a,b∈Z，b≠0q,r∈Za=bq+r，0≤r<|b|qr是唯一的。證明b|aq=a/b，r=0即可。b!|aE={a-bk|k∈Z}EE中有最=a-b>0<bb!a≠b>br=-b|>，r’∈Erq,r∈Za=bq+r，0≤r<|b|。q’,r’∈Za=bq’+r’，0≤r’<|b|b(q-q’)=r’-r，于b|(r’-r)0≤|r’-r|<|b|r’-r=0r=r’q=q’。2a=bq+r，0≤r<|b|qab除所得的（不完全）rab除所得的余數(shù)。r=0ab1b=15，則a=255時(shí)，a=17b+0q=17，r=0；a=417時(shí)，a=27b+12a=-81時(shí)，a=-6b+9q=-6，r=9。222整除稱為偶數(shù)，2k2k+1，k∈Z。類似地，任一整數(shù)可表示為3k，3k+1，3k+2三種形式之一。例3設(shè)a=2t-1，若a|2n，則a|n。4x,y∈Zax+by=1a|n，b|n，ab|n。§2最大公因數(shù)與最小公倍數(shù)1a1,a2,…,ann(n≥2)dda1,a2,…,an的一個(gè)公因數(shù)；整數(shù)a1,a,,an的公因數(shù)中最大的一個(gè)稱為最大公因數(shù)若a1,a2,an)=，則稱1a2,…an互質(zhì)（互素；a1,a2,…,ana1,a2,…,an兩兩互質(zhì)。注1任意整數(shù)a1a2…an必有公因數(shù)（1。2a1,a2,…,an0最大公因數(shù)必然存在而且唯一（§11之(4)）注3最大公因數(shù)一定是正整數(shù)。注4(a1,a2,…,an)=1相當(dāng)于a1,a2,…,an的公因數(shù)只有±1。注5兩兩互質(zhì)必互質(zhì)，反之未然。1a1,a2,…,ann個(gè)不全為零的整數(shù)，則(1) a1,a2,…,an與|a1|,|a2|,…,|an|的公因數(shù)相同；(2) (a1,a2,…,an|a1|,|a2|,…,|an|)2b是任一正整數(shù)，則0bb的因數(shù)，反之亦然；(2) (0,b)=b。推論b(0,b)=|b|。3a,b,ca=bq+cq∈Za,b與(b,c)(a,b)=(b,c)。4a1,a2,…,ana1,a2,…,an的整線性組合的集S={a1x1+a2x2+…+anxn|xi∈Z，i=1,2,…,n}(a1,a2,…,an)的所有倍數(shù)組成。ax 證明因?yàn)镾中有正整數(shù)所以S中有最小正整數(shù)設(shè)為D= ’ax 11 22+ax’，則對于任意的ax+ax+…+ax∈S，有ax+ax+…+axnn 11 22 nn 11 22 nn=(ax+ax++ax+0<ax+ax+ax=axxq)+11 22 nn 11 22 nn 1 1 1a(x-x’q)+…+a(x-x’q)∈S，若r>0，則與D是最小正整數(shù)矛盾，故r=0，即2 2 2 n n nS中任一整數(shù)都是D的倍數(shù)。反之，D的倍數(shù)也屬于S，故S=DZ={Da|a∈Z}。設(shè)d=(a,a,…,a)，下證：D=d。1 2 n由于d|aa,a,…,ai 1 2 n∈S，所以D|a，i=1,2,…,n，從而D≤d。因此，D=d。i推論設(shè)a,a,…,a 是不全為零的整數(shù)，則存在整數(shù) x,x,…,x，使得1 2 n 1 2 nax+ax+…+ax=(a,a,…,a)，這一等式稱為裴蜀（Bezout）等式。11 22 nn 1 2 n特別地，(a,a,…,a)=1的充分必要條件為存在整數(shù) x,x,…,x，使得1 2 n 1 2 nax+ax+…+ax=1。11 22 nn定理5 a,

,,

的每一個(gè)公因數(shù)都是(a

,,

)的因數(shù)；(a,a1 2

1 ,,

n)((a,a1

),,an

1 2 n設(shè)mZ(ma1

,ma2

,,

)m(a,a1

,,an)；設(shè)(a

,,

a)d(1

a,

a,,n)1；1 2

d d d設(shè)(ambm(abm可推廣）(6) 若c|ab且(cb)c|a。證明由裴蜀等式推出；將裴蜀等式相乘；可推出，c|ab，c|acc|abac)a|b。最大公因數(shù)的求法：1、由定理5(2)可知，求兩個(gè)以上整數(shù)的最大公因數(shù)可以轉(zhuǎn)化為求兩個(gè)整數(shù)的最大公因數(shù)，對此，我們有下面算法：輾轉(zhuǎn)相除法（歐幾里得(Euclid算法）abZ，b復(fù)做帶余除法，有限步之后必然停止（即余數(shù)為零）用b除a：a

r，0

|b|；0 0 0用r除b：brq r，0rr；0 01 1 1 0用r除r：r rq r，0r r；1 0 0 12 2 2 1用r 除r

r

r，0r r ；n1用r除r

n2：r

n2

n1n q 。

n n1n則(a,b)rn

n1

n1

n n1事實(shí)上，由于余數(shù)滿足r0

r r1

后余數(shù)必為零，另一方面，由定理3，我們有(a,b)(b,r0

)(r0

,r) (r ,r1 n1

)r。n2、上述算法不僅能算出(a,b)，而且可以求出方程axby(a,b)的一組整數(shù)解，具體做法就是將算式倒推。1 設(shè)a求(a,b)及x,y。定義2 設(shè)a,a1 2

, ,an

是n(n2)個(gè)非零整數(shù)，若整數(shù)D滿足a|D，in，則稱D為aai 1

,,

的一個(gè)公倍數(shù)；na,a

,,

的一切公倍數(shù)中的最小正數(shù)稱為a,a

,,

的最小公倍數(shù)，1 2[a,a1 2

n, ,a。n

1 2 n定理6 [a,a1 2

, ,an

][|a1

|,|a2

|, ,|an

|]；aa,a[aa,,

]的倍數(shù)；1 2 n 1 2 n設(shè)mZ[ma1

,ma2

, ,man

],a1

, ,an[a,a1 2

, ,an

][[a,a1

], ,an(a,b)[a,b]ab|；(6) 若a1a2,an[a1a2,ana1a2an|。證明由定義；(2)設(shè)Sa1 2

,,

的全體公倍數(shù)}，則S恰好是S中最小正整數(shù)D的所有n倍數(shù)構(gòu)成的集合，故D[a,a1 2

, ,an(3)(4)由定義；可設(shè)ab(ab[abaxby，于是b|axa,)b|xab|ax[a,b]a,b|ab[a,b]ab，( , [ , 一般情形，設(shè)(a,b)d，則a b 于是a b ab，及定( , [ , d d d d d2(a,b)[a,b]

a b a

dd2ab

ab；( , )[ , ]d d d d d2(6)由(4)(5)及定理5(6)可推之。補(bǔ)充習(xí)題：、設(shè)nZ

14n

是既約分?jǐn)?shù)。、設(shè)nZ，則n。、設(shè)mnZ，m(2m,2n。、設(shè)mnaZ，a(am,ana(m,n)。、設(shè)abxyZ，滿足axby(a0|x|b|0|y|a|。6、設(shè)a,bZ，證明：存在x,y,u,vZ，使得axu，byv，(x,y)1且[a,b]xy。、設(shè)m,nZ，(m,n)證明：(d,mn)(d,m)(d,(2) mnddd1正因數(shù)。、設(shè)nZ，證明：(an,bn)(a,b)n；

，其中d,d2 1

分別是m,n的2(2)設(shè)(a,b)1，a,bZ，abcn，則a,b都是正整數(shù)的n次方冪，事實(shí)上，a(a,c)n，b(b,c)n。一般地，若若干個(gè)兩兩互質(zhì)的正整數(shù)之積是整數(shù)的n次冪，則這些整數(shù)都是正整數(shù)的n次方冪。、設(shè)nZ，k2n|2knk。§3算術(shù)基本定理定義11數(shù)；否則稱為合數(shù)。注正整數(shù)分為三類：1，質(zhì)數(shù)類，合數(shù)類。定1 設(shè)aZ，a則a的外最小正因q是一質(zhì)數(shù)，并且a是數(shù)時(shí)，q 。證明假設(shè)q不是質(zhì)數(shù)，則q除1及本身外還有一正因數(shù)q，因而1qq，但q|a，故q1

1 1|a，這與q是a的除1外的最小正因數(shù)矛盾，從而q是質(zhì)數(shù)。當(dāng)a是合數(shù)時(shí)，aa1

q，其中a1a是質(zhì)數(shù)，由于q是a外的最小正因數(shù)，所qa，于是q2qaa，也即q 。1 1定理2 若p是一質(zhì)數(shù)，a是任一整數(shù)，則p|a或(a,p)。證明pa|ppapa或pap，即p|a或(a,p)。 推論設(shè)a,a, ,a是n個(gè)整數(shù)，p是質(zhì)數(shù)，若p|aa a，則a,a, , 1 2 n 12 n 1 2 n中至少有一個(gè)被p整除。證明假設(shè)aa1 2

,,

都不能被p整除，則(p,an

)1，i1,2,,n，從而(p,aa12

an

)1，這與p|aa12

an

矛盾，故結(jié)論成立。定理3 質(zhì)數(shù)有無窮多個(gè)。（公元前世紀(jì)，Euclid）證明（反證法）假設(shè)質(zhì)數(shù)只有有限多個(gè)，設(shè)p,p1 2

, ,pr

是全部質(zhì)數(shù)，考慮Npp1 2

N必有質(zhì)因數(shù)p，由假設(shè)p必然等于某個(gè)pi

(1ir)，因而p整除Npp1 2

算術(shù)基本定理）

的整appp，pp p，其p,p,,

是質(zhì)數(shù)，并且若1 2 n 1 2 n 1 2 naqqq，qq qqq,qmn，pq，12 m 1 2 m 1 2 m i ii1,2,,n。證明存在性（用數(shù)學(xué)歸納法）當(dāng)a2時(shí)，因?yàn)?是質(zhì)數(shù)，所以結(jié)論成立。假設(shè)結(jié)論對小于a的正整數(shù)都成立，下面考慮a，如果a是質(zhì)數(shù)，則結(jié)論成立；若a是合數(shù)，則有bcZ滿足abc1ba1ca，由歸納假設(shè)，b,c都可以寫成若干個(gè)質(zhì)數(shù)的乘積，于是a也能寫成有限個(gè)質(zhì)數(shù)的乘積，適當(dāng)調(diào)動(dòng)次序后便得結(jié)論。唯一性因?yàn)閍ppp qqq，pp，qq q，1 2 n 12 m 1 n 1 2 m所以p|q

q，q|ppp

q，使得p|q，q|p，又pq1 1

m 1 1 2 n

k j 1 j 1 k k j均為質(zhì)數(shù)，故p1

q，qj 1

p，又pk

p，q1

q，故q1

pp1

q，從而1p q，于是有p1 1

q2

，同法可得pm

q，依此類推，最后可得2nm，pi

q，in。i推1 任一大的整a能夠唯一地寫成1app2pki,,,ppij。11 2 k i i j1 上式叫a的標(biāo)準(zhǔn)分解式；注2 為了討論的方便，我可以插進(jìn)若干質(zhì)數(shù)的次冪而寫成下面形式1app2pki,,,ppij。11 2 k i i j1推論2 app2pk的標(biāo)準(zhǔn)分解式，則正的約數(shù)的充分11 2 k1必要條件是其標(biāo)準(zhǔn)分解式為dpp2pk，0，i1,2,,k。11 2 k i i證明充分性是顯然的。必要性若d1，則結(jié)論已成立；若d1，則由d|a可知，d的質(zhì)因數(shù)必在1pp,pddpp2pk1

0，i1,2,1 2 k 1 2 k i,k。下證：i

，i。（反證）i1假設(shè)有一個(gè)1

pj|d及d|apj

|p

pj1pj1pk，j j

j 1 j

jk即ppj

,,

,pj1

j

, ,pk

之一相同，矛盾，因此，i

，i,k，i結(jié)論成立。推論3 設(shè)a,bZ，且它們的標(biāo)準(zhǔn)分解式為11app2pk，bpp2pk，,11

1,2,,k，1 2 k 1 2 k i i則(a,b)p1p2pk，其中 ,1 2

i i i[a,b]p1p2pk，其中

,。1 2

i i i證明令mp1p2pk，則m|a，m|b，又任一公因數(shù)必整除m，1 2 k故m(a,b)。同樣可證另一結(jié)論。幼拉脫斯展納（Eratosthenes）篩法任給一個(gè)正整數(shù)N，把不超過N的一切正整數(shù)按大小關(guān)系排成一串1,2,3,,N，首先劃去1，第一個(gè)留下來的是2，然后從2起劃去2的一切倍數(shù)，第一個(gè)留下來的是3，然后從3起劃去3的一切倍數(shù)，，一直到劃去不超過N的質(zhì)數(shù)的一切倍數(shù)，最后留下來的就是不超過N一切質(zhì)數(shù)。例造不超過的質(zhì)數(shù)表。補(bǔ)充習(xí)題1、設(shè)n2，證明：n和n!之間必有質(zhì)數(shù)，由此說明質(zhì)數(shù)有無窮多個(gè)。、設(shè)nn在正整數(shù)序列中，可以有任意長的一段區(qū)間中不包含質(zhì)數(shù)。、證明：形4m的質(zhì)數(shù)有無窮多個(gè)；(2) 6m的質(zhì)數(shù)有無窮多個(gè)；4、如果p，p2，p4都是質(zhì)數(shù)，那么p3。10n110n2是質(zhì)數(shù)，則n必為質(zhì)數(shù)，反之不成立。設(shè)mZ，證明：若2m為質(zhì)數(shù)，則m的方冪；記Fn

22nn

費(fèi)馬數(shù)），證明：若mn，則Fn

|(Fm

2)；(FFm n

)1，mn。由此說明，質(zhì)數(shù)有無窮多個(gè)。(費(fèi)馬數(shù)中的質(zhì)數(shù)稱為費(fèi)馬質(zhì)數(shù)，如，F(xiàn)0

3，F(xiàn)1

5，F(xiàn)2

17，F(xiàn)3

257，F(xiàn) 65537都是質(zhì)數(shù)，費(fèi)馬猜測：F4

都是質(zhì)數(shù)。但F5

6416700417不是質(zhì)數(shù)（歐拉173），)設(shè)m,nZ，m,n證明：若mn是質(zhì)數(shù)，則m并且n是質(zhì)數(shù)；(設(shè)是質(zhì)數(shù)，記M 2pp

梅森數(shù)），證明：若pq，(M ,M )。p q(梅森數(shù)中的質(zhì)數(shù)稱為梅森質(zhì)數(shù)（1644，法），它與偶完全數(shù)緊密相關(guān)，到1996年底，找到34個(gè)梅森質(zhì)數(shù)，未知：是否有無窮多個(gè)梅森質(zhì)數(shù)？)8、設(shè)a,b,c,dZ，滿足abcd，證明：a4b4c4d4不是質(zhì)數(shù)。、證明) (a,,c])[(a,b),(a,c)；(2) [abc([ab],[a。1、證明) 111Z，(n；2 n(2) 11 1 Z(n。3 2n1§4函數(shù)[x]，{x}及其在數(shù)論中的一個(gè)應(yīng)用函數(shù)[x與是定義在實(shí)數(shù)集上的函數(shù)，函數(shù)[x]的值等于不大于x的最大整數(shù)，函數(shù){x}的值是x[x]，[x]叫做x的整數(shù)部分(也稱為高斯函數(shù))，4,[ }{x}4,[ }例[]3,[e]2,[]

20,[3]1,{3.14}0.14,{32。性質(zhì)(1) x[x]

3 5 5 5(2) [x]x[x]1[x]0(3) [nx]nZ；(4) [x][y][x{y}{x(5) [x[xxZ時(shí) xZ時(shí)；[ {{(6) 設(shè)a,b>則ababa，0ba [ {{b b b(7) a,bZa/r/