算術基本定理

1、關于質和計算根本定理的問題一、知識大于1的整數n總有兩個不同的正約數：1和n.假設n僅有兩個正約數稱 n沒有正因子，那么稱n為質數或素數假設n有真因子，即n可以表示為a b 的形式這里a,b為大于1的整數，那么稱n為合數.正整數被分為三類：數1,素數類，合數類關于素數的一些重要理論1. 大于1的整數必有素約數.2. 設p為素數，n為任意一個整數，那么或者 p整除n，或者p與n互素.事實上，p與n的最大公約數p,n必整除p，故由素數的定義推知，或者p,n 1，或者p,n p，即或者 p與n互素，或者 p|n.3. 設p為素數，a,bp|ab，那么a, b中至少有一個數被p整除.事實上，假設p不整

2、除a和b，由性質2知，p與a和b均互素，從而p與ab 互素。這與的p | ab矛盾.特別地：假設素數p整除an n 1，那么p | a4. 定理1素數有無限多個公元前歐幾里得給出證明證明：反證法假設只有k個素數，設它們是 J, p2,，pk。記NP1P2Pw1。 N不一定是素數由第一節(jié)定理2可知，p有素因數p，我們要說明p p,1 i k從而得出 矛盾事實上，假設有某個i,1 i k使得p 5那么由p I N P1P2 Pw 1推出P |1 ，這是不可能的。因此在P-!，P2,，Pk之外又有一個素數P，這 與假設是矛盾的。所以素數不可能是有限個5. 引理1任何大于1的正整數n可以寫成素數之積，

3、即nP1P2 Pm 其中口,1 i m是素數。證明 當n=2時，結論顯然成立。假設對于2 n k，式(1)成立，我們來證明式(1)對于n=k 1也成立，從而 由歸納法推出式(1)對任何大于1的整數n成立。如果k 1是素數，式(1)顯然成立。如果k 1是合數，那么存在素數p與整數d，使得k仁pd。由于2 d k，由歸納假定知存在素數 qq,qi，使得d qq,q，從而k 1 pqq,qi。 證畢。6. 定理2(算術根本定理)任何大于1的整數n可以唯一地表示成n P/P22 Pkk，(2)其中P1，P2,，Pk是素數，P1P2Pk，厲月2,ak是正整數。我們稱n Pl1 P22Pkk Oi，a2,

4、ak是n的標準分解式，其中Pi ,1 i k是素數，Pi P2 Pk，是正整數證明：由引理1,任何大于1的整數n可以表示成式 的形式，因此，證明 表示式(2)的唯一性。假設Pi,1 i k與qj,1 j l都是素數，P1 P2 Pk，q q?q，并且n P4 Pk qq?qi，(4)那么由第三節(jié)定理4推論1，必有某個q ,1 j l，使得P | cj，所以P1=qi ;又有某個Pi,1 i k，使得q | Pi，所以q1=Pi。于是，由式可知?=q1，從而由式得到P2 Pk=cfe qi重復上述這一過程，得到k l, Pi qi,1 i k 證畢。7. 定理：假設設(n)為n的正約數的個數，(

5、n)為n的正約數之和，那么有1(n) ( i 1)( 2 A ( k 1)I,21/k 1 A2(n)P11 -P2_ _1P1 1P2 1Pk 18. 推論1使用式(2)中的記號，有(i ) n的正因約數d必有形式d = d pg2 Pkk, 1Z,0 i i,1 i k(ii) n的正倍數m必有形式m P/P22 PkkM,M N, i N, i i,1 i k9.推論2設正整數a與b的標準分解式是a12k.P1 P2Pk ， b11P1 P2kPk ，其中P1, P2, Pk是互不相同的素數，i， i1 i k都是非負整數,那么(a,b)11kP1 P2Pk， imin i ,i，1 i

6、 k，a,b11kP1 P2Pk ， imax i,i，1 i k。10.推論3設a，b，c，n是正整數，ab=cn，(a, b) = 1(5)那么存在正整數u，v，使得a =nnu， b = v， c =uv，(u,v) = 10證明 設c = p11 p21 pkk，其中P1, P2, , Pk是互不相同的素數，i 1i k是正整數。又設a Pi1 P22 Pkk, b pi1 P21 Pkk ,其中i, i 1 i k都是非負整數。由式 及推論2可知mi n i, i = 0 , i i = ni, 1 i k,因此，對于每個i 1 ik，等式i = n i， i = 0 與 i = 0

7、 ， i = n i有且只有一個成立。這就證明了推論。證畢。11.定理：對任意的正整數m及素數p，記號p |m表示p |m, p 1 | m，即p是m的標準分解中出現的p的幕.設n 1， p為素數，p p | n!，那么ap這里x表示不超過實數x p1 n時，那么呂p0，故上面和式中只有有限多個項非零.另一種表現形式:設p為任一素數，在n!中含p的最高乘方次數記為p n!，那么有:p n!證明：由于p是素數，所有n!中所含p的方次數等于n!的各個因數1,2,，n 所含p的方次數之總和。由性質10可知，在1,2,，n中，有-個p的倍數,pn有2p個p的倍數，有 3個p的倍數，當p n p 時，

8、pnm 1p呂0，所以命題成立。p另證：對于任意固定的素數p，以p k表示在k的標準分解式中的p的指數，那么pn! =p(1) p(2)祕 n).以nj表示p(1), p(2),，p(n)中等于j的個數，那么p n! =1 m 2 n? 3 g ，(2)顯然，nj就是在1,2,n中滿足pj a并且p十1 | a的整數a的個數，所以 由定理2有。腫。將上式代入式(2)，得到問)吧冷)2(罰制3(罰制-【制。r 1 p即式成立。證畢。二、重要方法證明某些特殊形式的數不是素數或給出其為素數的必要條件是初等數論 中較為根本的問題，其方法是應用各種分解技術如代數式的分解 ，指出所給 數的一個真因子常用分

9、解技術有：(1) 利用代數式分解如因式分解指出其一個真因子；(2) 應用數的分解例如算術根本定理，指出數的一個真因子；3運用反證法，假定其是素數，然后利用素數的性質推出矛盾.三、例題講解 例1.證明：無窮數列10001,100010001,中沒有素數.教材第13頁例1證明：記 an 1000110001,(n2)，那么n個 1an 1 104108104(n °104n 1104 1對n分奇偶討論:1當n為偶數時，設n 2k，那么an108k 1104 1108k 1 108 1108 1 104 188k8、k顯然10J 是大于1的整數，當k 2時，巴廠啤 1是大于1的整數10 1

10、 10 1 10 1而當k 1時，a210001 13 137是合數.(2)當為奇數時，設n 2k 1 ,n an8k 410 14k 24k 210 1 10 1(102)2k11 (102)2k 1104 1102 1 102 1102 1102 1易知 竺 1,1都是大于1的整數102 1 102 1綜上：命題獲證；例2.證明：對任意整數n 1，數n4 4n不是素數.教材第13頁例2證明：我們對n分奇偶討論：(1) 當為偶數時，n4 4n大于2,且也為偶數，故結論顯然成立.(2) 當為奇數時，設n 2k 1，那么4,n 4,2k 1n 4 n 4n4 4 (2k)4(n2 2 22k)2

11、 4n2 (2k)2(n2 2 22k)2 (2n2k)2(n2 2 22k 2n 2k)(n2 2 22k 2n 2k)由于n 1，所以n2 2 22 k 2n 2k,n2 2 22k 2n 2k都是大于1的整數，故n4 4n是合數.綜上：n4 4n不是素數.例3.設正整數a, b, c,d滿足ab cd，證明：a b c d不是素數證明一：是應用數的分解，指出abed的一個真因子.由ab ed，可設旦d m，其中m,n是互素的正整數e b n故 a mu, e nu，同理 d mv, e nv故abed mu nu mv nv (m n)(u v)是兩個大于1的整數積，從而不是素數證明二：

12、由ab cd，得b竺，因此a b acd a cd竺a(a c)(aad)，因a b c d是整數.假設它是一個素數，設為p，那么由(a c)(a d) ap*，p |(ac)(a d)故 p|(a c)或 p|(a d)，不妨設,p|(ac)那么a cp，結合*式得：ad a，即d 0，這不可能，故結論成立；例4.設整數a,b, c, d滿足a b c d0，且 a2 acc2 b2bd d2證明：ab cd不是素數.教材第18頁習題3-4證明：此題運用反證法，設有滿足題設的一組a,b,c,d，使得ab cd為素數, 將其記為p ab cd，于是a -cd帶入條件得到：b2 2 2 2p(p

13、 2cd bc) (b c )(b bd d )由于p是素數，故p| (b2 c2)或者p| (b2 bd d2)i假設 p |(b2 c2)，那么由 b2 c2 ab ab 2ab 2(ab cd) 2p，推出2 2b c p，即 b2 c2 abcd，從.而 b | c(cd)，顯然(b,c)1因為b2c2是素數故 b|(cd)，這與0c dcb矛盾.ii假設p|(b2bdd2)，那么由02 2b bd d 2(ab cd)2p知b2 bd d2p，故2 aac2 cb2 bdd2ab cd，進而得到2a acc(cd)ab, b2bdd(d c) ab，于是得到a| c(c d),b |

14、 d(c d)都成立，但又知(ab,cd) 1，故被c d a和例5.證明：假設整數a,b滿足2a2 a 3b2 b，那么a b和2a 2b 1都是完全平 方數證明：關系式變形為(a b)(2a 2b 1) b2 1論證的第一個要點是證明整數a b與2a 2b 1 (a b,2a 2b 1) d .假設 d 1,那么d有素因子p，從而由1知p| b2,因p是素數，故p|b.結合p|(a b) 知p|a.再由p|(2a 2b 1)導出p|1，這不可能，故d 1，即a b與2a 2b 1互 素因此，由1得右端為1b2是一個完全平方數，故|a b|,|2a 2b 1|均 是完全平方數下面證明a b

15、0，我們運用反證法.假設有整數a,b滿足問題中的等式，但a b 0 .因已證明| a b|是一個完全 平方數故有bar2，這里r 0 ；結合1丨推出r | b，再由b a r2得出r | a . 設b b|,a r，帶入問題中的等式可得(注意r 0,厲r)訂 6* 3r2 1 0 2將上式視為關于 的二次方程，由求根公式解得a1 3r 6r2 1，因a1是整數， 故由上式知6r2 1是完全平方數.但易知一個完全平方數被3除得的余數只能為 0或1；而6r2 1被3除得余數為2,矛盾.(或者更直接地：由a12被3除得余數為0或1，故2左邊被3除得的余數 是1或2;但2的右邊為0,被3整除.矛盾.即

16、2對任何整數ai及r均不 成立)從而必須有a b 0，這就證明了此題的結論.注：1例6.寫出n 51480的標準分解式，并求它的正約數的個數(n);解：我們有514802 2574022 1287023 6435 23 5 128723 5 3 42923 5 32 14323 32 5 11 13(n) ( 1 1)( 2 1卜( k 1) (3 1)(2 1)(1 1)(1 1)(1 1) 96例7.求最大的正整數k，使得10k |199!解：因為10 2 5,正整數k的最大值取決于199!的分解式中所含5的幕指由定理2, 199!的標準分解式中所含的5的幕指數是47r199199199丁

17、子I片所以，所求的最大整數是k 47 o例8.設x與y是實數，那么2x2y3 x x yy(*)設xx,01, yy,01，那么右邊xx yy2x2?y(1)左邊2x2y 2x2?y22 ,如果0，那么顯然有22 ；如果1,那么與中至少有一個不小、于丄，于是2221o證法因此無論0或1,都有,由此及式(1)和式可以推出式(*)成立.證法二：注意到對任意整數k及任意實數k ,即上述不等式中x或y改變一個整數量，那么不等式(*)兩邊改變一個相同的量.故不等式(*)只 需證明0 x 1,0 y 1的情形即可.例9.一個經典的問題設m,n是非負整數，證明：(2m)!(2n)!是一個整數.m!n !(m

18、 n)!證明：我們只需證明：對每一個素數 p，分母m!n!(m n)!的標準分解中p的幕次，不超過分子(2m)!(2 n)!中p的幕次，由定理知等價于證明2m2nmllll 1ppl 1pnl pm nlp事實上我們能夠證明一個更強的命題：設X與y是實數，那么2x2y 3 x xyy這就是例9討論的問題. 結合知命題成立.例10.設a,b,c是整數，證明：(i )(a,b)a,b ab ;(ii)(ab,c)(a,b),(a,c)。解 為了表達方便，不妨假定a,b,c是正整數。apg2 PkP1S21 Pkkb，其中Pi, P2,Pk是互不相同的素數,i(1 i k)都是非負整數。由定理 1推論2，(a,b)a,bP11 P21 Pkk，Pl1 P21 Pkmin i, i，1 imax i, i， 1 ik，k。由此知(a,b)a, b=Pimin i, i max*pikPii 1i ab ;Pii，kP i，其中Pl, P2,，Pk是互不相同的素數,i, i, i(1 i k)都是非負整數。由定理有kk(a,b,c) Pii, (a,b),(a,c) Pii ,i 1i 1其中，對于(1 i k)，有i min i, max i, ，i maxmin i, , min i,