算術(shù)基本定理

1、大于1的整數(shù)n總有兩個(gè)不同的正約數(shù)：1和n .若n僅有兩個(gè)正約數(shù)（稱n沒 有正因子），則稱n為質(zhì)數(shù)（或素?cái)?shù)）.若n有真因子，即n可以表示為a b的形 式（這里a,b為大于1的整數(shù)），則稱n為合數(shù).正整數(shù)被分為三類：數(shù)1,素?cái)?shù)類，合數(shù)類關(guān)于素?cái)?shù)的一些重要理論1 .大于1的整數(shù)必有素約數(shù).2 .設(shè)p為素?cái)?shù)，n為任意一個(gè)整數(shù)，則或者 p整除n,或者p與n互素.事實(shí)上，p與n的最大公約數(shù)（p,n）必整除p,故由素?cái)?shù)的定義推知，或者（p,n） 1,或者（p, n） p,即或者 p與n互素，或者 p|n.3 .設(shè)p為素?cái)?shù)，a, b為整數(shù).若p|ab,則a,b中至少有一個(gè)數(shù)被p整除.事實(shí)上，若p不整除a和b

2、,由性質(zhì)2知，p與a和b均互素，從而p與ab互素。這與已知的p|ab矛盾.特別地：若素?cái)?shù)p整除an （n 1），則p|a4 .定理1素?cái)?shù)有無限多個(gè)（公元前歐幾里得給出證明）證明：（反證法）假設(shè)只有k個(gè)素?cái)?shù)，設(shè)它們是 P2±, Pko記N pi p 2 L Pw 1o （ N不一定是素?cái)?shù)）由第一節(jié)定理2可知，p有素因數(shù)p,我們要說明p pi, 1 i k從而得出 矛盾事實(shí)上，若有某個(gè)i,1 i k使得p pi,則由p | N p 1 p2L pw 1準(zhǔn)出p |1 ,這是不可能的。因此在p1, p2,L , pk之外又有一個(gè)素?cái)?shù)p,這 與假 設(shè)是矛盾的。所以素?cái)?shù)不可能是有限個(gè)。5 .引理

3、1任何大于1的正整數(shù)n可以寫成素?cái)?shù)之積，即p1 p2Lpm其中Pi, 1 i m是素?cái)?shù)證明 當(dāng)n=2時(shí)，結(jié)論顯然成立。假設(shè)對(duì)于2 n k ,式（1）成立，我們來證明式（1）對(duì)于n=k 1也成立，從而 由 歸納法推出式（1）對(duì)任何大于1的整數(shù)n成立。如果k 1是素?cái)?shù)，式（1）顯然成立。如果k 1是合數(shù)，則存在素?cái)?shù)p與整數(shù)d,使得k仁pd。由于2d k ,由歸納假定知存在素?cái)?shù) q1,q2,L qi,使得d q,q2,L qi,從而k 1 pq 1,q2,L qi。證畢。6,定理2（算術(shù)基本定理）任何大于1的整數(shù)n可以唯一地表示成n p1 1P2 2L pkk,（2）其中 pi, P2,L , Pk

4、是素?cái)?shù)，Pi P2 LPk, ai,a2 _L,ak是正整數(shù)。我們稱n Pi1P22L Pkkai,a2,L , ak是n的標(biāo)準(zhǔn)分解式，其中Pi ,1 i k是素?cái)?shù)，Pi P2 L Pk,是正整數(shù)證明：由引理i,任何大于i的整數(shù)n可以表示成式 的形式，因此，證明 表示式（2）的唯一性。Pi P2L Pk, qi q2L并且n PiP2L Pk qiq2L qi ,則由第三節(jié)定理4推論i,必有某個(gè)qj,i j假設(shè)Pi,i i k與qj,ij l都是素?cái)?shù),qi,(3)(4)i ,使得Pi |qi ,所以Pi=qi；又有可知pi二q,從而由式某個(gè)p/ i k ,使得qi | Pi,所以qi = Pi

5、o于是，由式（4）得到P2L Pk=q2L qi重復(fù)上述這一過程，得到)Piqi,1 i k 證畢。7.定理：若設(shè)（n）為n的正約數(shù)的個(gè)數(shù),為n的正約數(shù)之和，則有(1)(n)( 11)( 21)g a k1)1 1 1P 11 P 22 1g gPk k1(n) P1 1P21 Pk18.推論1使用式（2）中的記號(hào)，有（i ） n的正因（約）數(shù)d必有形式d = dPiR2L Pkk, 1 Z,0 ii,1 i k（ii） n的正倍數(shù)m必有形式m P11P22L PkkM ,M N, i N,i,1 i k9.推論2設(shè)正整數(shù)a與b的標(biāo)準(zhǔn)分解式是其中P1, P2,12kaP1 P2 Pk ,Pk是

6、互不相同的素?cái)?shù),1 1P1 P2Pkk,i (1i k）都是非負(fù)整數(shù)，則(a,b)a,b11kP1 P2Pk, i11kP1 P2Pk,min i,max i,i, 1 i k,i, 1 i ko10.推論3設(shè)a, b, ab則存在正整數(shù)u, v,使得c, n是正整數(shù),cn, (a, b) = 1uv, (u,v) = 1 。證明設(shè)c = P11 P21Pk',其中 P1, P2,Pk是互不相同的素?cái)?shù),i (1ik）是正整數(shù)。又設(shè)其中I, i (1mi n i,因此，對(duì)于每個(gè)i （112k 1a Pi P2 Pk, bk )都是非負(fù)整數(shù)。i = 0,ii k),等式P11P21Pkk

7、,由式（5）及推論2i = n i, 1可知i k,i = n i , i = 0八與i= 0 , i = n i有且只有一個(gè)成立。這就證明了 推論。證畢。11.定理：對(duì)任意的正整數(shù)m及素?cái)?shù)p,記號(hào)p |m表示p |m, p | m ,即p是m的標(biāo)準(zhǔn)分解中出現(xiàn)的p的幕.設(shè)n 1 , p為素?cái)?shù)，p p|n!,則ap這里x表示不超過實(shí)數(shù)x的最大整數(shù).由于當(dāng)p10,故上面和式中只有有限多個(gè)項(xiàng)非零？另一種表現(xiàn)形式：設(shè)p為任一素?cái)?shù)，在n!中含p的最高乘方次數(shù)記為p n!,則有:p n!nn m m 12 L m P n p,n證明：由于p是素?cái)?shù)，所有n!島含p的方戾數(shù)等于n!的各個(gè)因數(shù)1,2,L所含p的

8、方次數(shù)之總和。由性質(zhì)10可知，在1,2,L ,n中，有-個(gè)p的倍數(shù),pn個(gè)p的倍數(shù)，有3個(gè)p的倍數(shù)，L ,當(dāng)p n p時(shí)，p 有2pnm 1pn 2 l。，所以命題成立。p另證：對(duì)于任意固定的素?cái)?shù) p,以p k表示在k的標(biāo)準(zhǔn)分解式中的p的指數(shù)，則p n! =p(1) p(2) L p(n).以nj表示p(1), p(2),L ,p(n)中等于j的個(gè)數(shù)，那么p n! =1 n, 2 n2 3 L ,顯然，nj就是在1,2,L , n中滿足pj a并且pj + 1 | a的整數(shù)a的個(gè)數(shù)，所以由定理2有將上式代入式（2）,得到P （n!） 1 瞪嶺）2 （話制 3 （ flj 制 L日。r 1 P即

9、式（1）成立。證畢。二、重要方法證明某些特殊形式的數(shù)不是素?cái)?shù)（或給出其為素?cái)?shù)的必要條件）是初等數(shù)論中較為基本的問題，其方法是應(yīng)用各種分解技術(shù)（如代數(shù)式的分解），指出所給 數(shù)的一個(gè)真因子常用分解技術(shù)有：（1）利用代數(shù)式分解（如因式分解）指出其一個(gè)真因子；（2）應(yīng)用數(shù)的分解（例如算術(shù)基本定理），指出數(shù)的一個(gè)真因子；（3）運(yùn)用反證法，假定其是素?cái)?shù)，然后利用素?cái)?shù)的性質(zhì)推出矛盾.三、例題講解 例1.證明：無窮數(shù)列10001,100010001,中沒有素?cái)?shù).（教材第13頁例1）(n 2)證明：記 an 100412 400?1 )n個(gè)1an 1 10 4108 */ -4(n 1)10104n 1104

10、1對(duì)n分奇偶討論:（1）當(dāng)n為偶數(shù)時(shí)，設(shè)n 2k,則an108k 1104 18k8101 101108 1 104 18k 44k 24k 2an4易知叫I型102 1 102 1J(102)10 1 10 1 10 12k 122 10 1 10 1 10 1102 11都是大于1的整數(shù)1 (102)102 12k1綜上：命題獲證;例2.證明：對(duì)任意整數(shù)n 1,數(shù)n4 4n不是素?cái)?shù).(教材第13頁例2)證明：我們對(duì)n分奇偶討論：(1) 當(dāng)為偶數(shù)時(shí)，n4 4n大于2,且也為偶數(shù)，故結(jié)論顯然成立(2) 當(dāng)為奇數(shù)時(shí)，設(shè)n 2k 1 ,則4 ,n 4,2k 1n 4 n 4n4 4 (2k)4(n

11、2 2 22k)2 4n2 (2k)2(n2 2 22k)2 (2n 2 k)2(n2 2 22k 2n 2k)(n2 2 22k 2n 2 k)由于n 1 ,所以n2 2 22k 2n 2 k, n2 2 22k 2n 2k都是大于1的整數(shù),故n4 4n是合數(shù).綜上：n44 n不是素?cái)?shù).例3.設(shè)正整數(shù)a, b, c,d滿足ab cd ,證明：a b c d不是素?cái)?shù)證明一：本題不宜采用代數(shù)式的分解來產(chǎn)生所需的分解.我們的第一種解是應(yīng) 用數(shù)的分解，指出abed的一個(gè)真因子.由ab ed ,可設(shè)a d m，其中m, n是互素的正整數(shù).e b n故 a mu, e nu ,同理 d mv, e nv

12、故abed mu nu mv nv (m n)(u v) 是兩個(gè)大于1的整數(shù)積，從而不是素?cái)?shù).證明二：由ab ed ,得b。，因止匕abed a e dae)(a，因aaaa b c d是整數(shù).若它是一個(gè)素?cái)?shù)，設(shè)為p,則由(a c)(a d) ap (*), p|(a c)(a d)故p|(a c)或p |(a d),不妨設(shè)，p|(a c)則a c p,結(jié)合(*)式得：a d a ,即d 0,這不可能，故結(jié)論成立；例 4.設(shè)整數(shù) a,b,c,d 滿足 a b c d 0,且 a2 ac c2 b2 bd d2證明：ab cd不是素?cái)?shù).(教材第18頁習(xí)題3-4)證明：本題運(yùn)用反證法，設(shè)有滿足題設(shè)

13、的一組a,b,c,d ,使得ab cd為素?cái)?shù)，將其記為p ab cd ,于是a p帶入已知條件得到：b2 2 2 2p(p 2cd bc) (b c )(b bd d )由于p是素?cái)?shù)，故p | (b2 c2)或者p | (b2 bd d2)(i)若 p|.2 2b c p ,22、(b c八即、2b2c ab則由b2 c2 abcd ,從而 b | c(cab 2ab 2(ab cd) 2P ,推出d) 顯然(b,c)1 (因?yàn)閎2c2是素?cái)?shù))故b|(c d), 這與0 cd c b矛盾.(ii )若 p|(b bdb2 bd d2 p,故d2 ),則由 0 b 2 2 bd d 2(abcd

14、) 2p 知進(jìn)而得到2a ac于是得到 a |c(c d), b |d(c d)ac 2 cb2 bdd2ab cd ,c(c d) ab, b2 bd d(d c) ab ,都成立，但又知(ab,cd) 1 ,故被c d a和b整除.因0 c d2a,0 c d 2b從而必須有c d a,c d b ,矛盾.例5.證明：若整數(shù)a,b滿足2a2 a 3b2 b,貝U a b和2a 2b 1都是完全平方證明：已知關(guān)系式變形為（a b） （2a 2b 1 ） b （1）論證的第一個(gè)要點(diǎn)是證明整數(shù)a b與2a 2b 1互素.記（a b,2a 2b 1 ） d .若d 1,則d有素因子p,從而由（1）

15、知p | b2,因p是素?cái)?shù)，故p|b.結(jié)合p| （a b）知p|a.再由p|（2a 2b 1 ）導(dǎo)出p|1 ,這不可能，故d 1 ,即a b與2a 2b 1互 素犧此，由（1）得右 端為（1） b2是一個(gè)完全平方數(shù)，故|a b|,|2a 2b 1|均 是完全平方數(shù)？下面證明a b 0,我們運(yùn)用反證法.假設(shè)有整數(shù)a,b滿足問題中的等式，但a b 0.因已證明|a b|是一個(gè)完全 平方數(shù)故 有b a r2,這里r 0 ;結(jié)合（1）推出r | b ,再由b a r2得出r |a .設(shè)b 0r,a a什，帶入問題 中的等式可得（注意r 0,b1 a1 r）2 2a16a1r3r1 0（ 2）將上式視為

16、關(guān)于a1的二次方程，由求根公式解得a 3r .6r21,因內(nèi)是整數(shù)， 故由上式 知6r2 1是完全平方數(shù).但易知一個(gè)完全平方數(shù)被3除得的余數(shù)只能為0或1;而6r2 1 被3除得余數(shù)為2,矛盾.（或者更直接地：由aj被3除得余數(shù)為0或1,故（2）左邊被3除得的余數(shù)是1或2;但（2）的右邊為0,被3整除.矛盾.即（2）對(duì)任何整數(shù)a1及r均不 成立）從而必須有a b 0,這就證明了本題的結(jié)論.注：1.許多數(shù)論問題需證明一個(gè)正整數(shù)為1 （例如，證明整數(shù)的最大公約數(shù)是1）,由此我們常假設(shè)所說的數(shù)有一個(gè)素因子，利用素?cái)?shù)的銳利性質(zhì)（3）作進(jìn)一步論證，以導(dǎo)出矛盾.如例4(n)例6.寫出n 51480的標(biāo)準(zhǔn)分解

17、式，并求它的正約數(shù)的個(gè)數(shù)解：我們有5148022574022 1287023 5 3 429 2 3 5 32 14323 643523 5 128723 32 5 11 13(n)( 11)( 2 1)g g( k 1) (31)(2 1)(1 1)(1 1)(1 1) 96例7.求最大的正整數(shù)k,使得 10k |199!解：因?yàn)?0 2 5,正整數(shù)k的最大值取決于199!的分解式中所含5的幕指由定理2, 199!的標(biāo)準(zhǔn)分解式中所含的5的幕指數(shù)是罟即【詈L 47所以，所求的最大整數(shù)是k 47。例 8.設(shè) x 與 y 是實(shí)數(shù)，則2 x 2y3 x x y y(*)可以推出式（*）成立.證法二：

18、注意到對(duì)任意整數(shù)k及任意實(shí)數(shù) 證法k，即上述不等式如果如果x,01, y y,01,右邊左邊因此無論x2x0,1,x y y2y 2 x那么顯然有2x 2?y2?y2那么與中至少有一個(gè)不小于2，2 ,于是由此及式（1）和式（2）0或1,都有中x或y改變一個(gè)整數(shù)量，則不等式（*）兩邊改變一個(gè)相同的量 做不等式（*）只 需證明 0 x 1,0 y 1的情形即可.于是問題等價(jià)于證明：2x2 y x y下面同證例9. 一個(gè)經(jīng)典的問題設(shè)m,n是非負(fù)整數(shù)，證明：(2m)!(2n)!是一個(gè)整數(shù).m!n !(mn)!證明：我們只需證明：對(duì)每一個(gè)素?cái)?shù)p,分母m!n!(m n)!的標(biāo)準(zhǔn)分解中p的幕次，不超過分子(

19、2m)!(2 n)!中p的幕次，由定理知等價(jià)于證明2m 2nm n m niiii3i i p pi i p1Pp事實(shí)上我們能夠證明一個(gè)更強(qiáng)的命題：設(shè) X 與 y 是實(shí)數(shù)，則2x2y 3 x x y y這就是例9討論的問題.結(jié)合知命題成立.例10.設(shè)a,b,c是整數(shù)，證明：(i )(a,b)a,b ab(ii) (ab,c)(a,b),(a,c)。解為了敘述方便，不妨假定a,b,c是正整數(shù)(i )設(shè)a PiiP22L Pkk,其中Pi, P2,L , Pk是互不相同的素?cái)?shù)， 推論2，有(a,b) Pi1 P21L Pkkb Pii P2L Pkg,a,b PiRL Pkki, i(i i k)都是非負(fù)整數(shù)。由定理由此知k(a,b)a, b = pii i(i)設(shè)i min i, i, i i k ,i max i,i i koka Pp,min i i max i iPikPii i其中pi,P2, L , pk是互不相同的素?cái)?shù)，i, i, i(1 i k )都是非負(fù)整數(shù)。由定理 有kk(a,b,c)p，(a,b),(a,c)p，i1 i 1其中，對(duì)于(1 i k),有i min i, max i, i,i max min i, i, min i, i,不妨設(shè)i i,則min i , i min i,?i,所以i min i, i i即(ab,c) (