算術基本定理

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

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

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

4、ak是n的標準分解式，其中Pi ,1 i k是素數(shù)，Pi P2 Pk，是正整數(shù)證明：由引理1,任何大于1的整數(shù)n可以表示成式 的形式，因此，證明 表示式(2)的唯一性。假設Pi,1 i k與qj,1 j l都是素數(shù)，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的正約數(shù)的個數(shù)，(

5、n)為n的正約數(shù)之和，那么有1(n) ( i 1)( 2 A ( k 1)I,21/k 1 A2(n)P11 -P2_ _1P1 1P2 1Pk 18. 推論1使用式(2)中的記號，有(i ) n的正因約數(shù)d必有形式d = d pg2 Pkk, 1Z,0 i i,1 i k(ii) n的正倍數(shù)m必有形式m P/P22 PkkM,M N, i N, i i,1 i k9.推論2設正整數(shù)a與b的標準分解式是a12k.P1 P2Pk ， b11P1 P2kPk ，其中P1, P2, Pk是互不相同的素數(shù)，i， i1 i k都是非負整數(shù),那么(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是正整數(shù)，ab=cn，(a, b) = 1(5)那么存在正整數(shù)u，v，使得a =nnu， b = v， c =uv，(u,v) = 10證明 設c = p11 p21 pkk，其中P1, P2, , Pk是互不相同的素數(shù)，i 1i k是正整數(shù)。又設a Pi1 P22 Pkk, b pi1 P21 Pkk ,其中i, i 1 i k都是非負整數(shù)。由式 及推論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.定理：對任意的正整數(shù)m及素數(shù)p，記號p |m表示p |m, p 1 | m，即p是m的標準分解中出現(xiàn)的p的幕.設n 1， p為素數(shù)，p p | n!，那么ap這里x表示不超過實數(shù)x p1 n時，那么呂p0，故上面和式中只有有限多個項非零.另一種表現(xiàn)形式:設p為任一素數(shù)，在n!中含p的最高乘方次數(shù)記為p n!，那么有:p n!證明：由于p是素數(shù)，所有n!中所含p的方次數(shù)等于n!的各個因數(shù)1,2,，n 所含p的方次數(shù)之總和。由性質10可知，在1,2,，n中，有-個p的倍數(shù),pn有2p個p的倍數(shù)，有 3個p的倍數(shù)，當p n p 時，

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

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

10、 10 1 10 1而當k 1時，a210001 13 137是合數(shù).(2)當為奇數(shù)時，設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的整數(shù)102 1 102 1綜上：命題獲證；例2.證明：對任意整數(shù)n 1，數(shù)n4 4n不是素數(shù).教材第13頁例2證明：我們對n分奇偶討論：(1) 當為偶數(shù)時，n4 4n大于2,且也為偶數(shù)，故結論顯然成立.(2) 當為奇數(shù)時，設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的整數(shù)，故n4 4n是合數(shù).綜上：n4 4n不是素數(shù).例3.設正整數(shù)a, b, c,d滿足ab cd，證明：a b c d不是素數(shù)證明一：是應用數(shù)的分解，指出abed的一個真因子.由ab ed，可設旦d m，其中m,n是互素的正整數(shù)e b n故 a mu, e nu，同理 d mv, e nv故abed mu nu mv nv (m n)(u v)是兩個大于1的整數(shù)積，從而不是素數(shù)證明二：

12、由ab cd，得b竺，因此a b acd a cd竺a(a c)(aad)，因a b c d是整數(shù).假設它是一個素數(shù)，設為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.設整數(shù)a,b, c, d滿足a b c d0，且 a2 acc2 b2bd d2證明：ab cd不是素數(shù).教材第18頁習題3-4證明：此題運用反證法，設有滿足題設的一組a,b,c,d，使得ab cd為素數(shù), 將其記為p ab cd，于是a -cd帶入條件得到：b2 2 2 2p(p

13、 2cd bc) (b c )(b bd d )由于p是素數(shù)，故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是素數(shù)故 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.證明：假設整數(shù)a,b滿足2a2 a 3b2 b，那么a b和2a 2b 1都是完全平 方數(shù)證明：關系式變形為(a b)(2a 2b 1) b2 1論證的第一個要點是證明整數(shù)a b與2a 2b 1 (a b,2a 2b 1) d .假設 d 1,那么d有素因子p，從而由1知p| b2,因p是素數(shù)，故p|b.結合p|(a b) 知p|a.再由p|(2a 2b 1)導出p|1，這不可能，故d 1，即a b與2a 2b 1互 素因此，由1得右端為1b2是一個完全平方數(shù)，故|a b|,|2a 2b 1|均 是完全平方數(shù)下面證明a b

15、0，我們運用反證法.假設有整數(shù)a,b滿足問題中的等式，但a b 0 .因已證明| a b|是一個完全 平方數(shù)故有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是整數(shù)， 故由上式知6r2 1是完全平方數(shù).但易知一個完全平方數(shù)被3除得的余數(shù)只能為 0或1；而6r2 1被3除得余數(shù)為2,矛盾.(或者更直接地：由a12被3除得余數(shù)為0或1，故2左邊被3除得的余數(shù) 是1或2;但2的右邊為0,被3整除.矛盾.即

16、2對任何整數(shù)ai及r均不 成立)從而必須有a b 0，這就證明了此題的結論.注：1例6.寫出n 51480的標準分解式，并求它的正約數(shù)的個數(shù)(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.求最大的正整數(shù)k，使得10k |199!解：因為10 2 5,正整數(shù)k的最大值取決于199!的分解式中所含5的幕指由定理2, 199!的標準分解式中所含的5的幕指數(shù)是47r199199199丁

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

18、 n)!證明：我們只需證明：對每一個素數(shù) p，分母m!n!(m n)!的標準分解中p的幕次，不超過分子(2m)!(2 n)!中p的幕次，由定理知等價于證明2m2nmllll 1ppl 1pnl pm nlp事實上我們能夠證明一個更強的命題：設X與y是實數(shù)，那么2x2y 3 x xyy這就是例9討論的問題. 結合知命題成立.例10.設a,b,c是整數(shù)，證明：(i )(a,b)a,b ab ;(ii)(ab,c)(a,b),(a,c)。解 為了表達方便，不妨假定a,b,c是正整數(shù)。apg2 PkP1S21 Pkkb，其中Pi, P2,Pk是互不相同的素數(shù),i(1 i k)都是非負整數(shù)。由定理 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是互不相同的素數(shù),i, i, i(1 i k)都是非負整數(shù)。由定理有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,