算術基本定理

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, b為整數(shù).若p|ab，

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

3、有限個05. 引理 1 任何大于 1 的正整數(shù) n 可以寫成素數(shù)之積，即p1 p2 L pm(1)證明 當 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。由于2d k , 由歸納假定知存在素數(shù) q1,q2,L ql ，使得 d q1,q2,L ql ，從而 k 1 pq1,q2,L ql 。 證畢。6. 定理 2( 算術基本定理 )任何大于 1 的整數(shù) n 可以唯一地

4、表示成n p1 1 p2 2L pkk ，(2)其中pi,P2,L,Pk是素數(shù)，PiP2LPk,ai,a2丄,ak是正整數(shù)。我們稱n Pi1 P22 L Pkk ai,a2,L , ak是n的標準分解式，其中Pi ,1 i k是素數(shù)， PiP2 L Pk ,是正整數(shù) .證明：由引理i,任何大于i的整數(shù)n可以表示成式 的形式，因此，證明 表示式 (2) 的唯一性。假設 Pi,ii k 與 qj,i j l 都是素數(shù)，PiP2 LPk，qiq2 Lql，(3)并且nPiP2L Pkqiq2L ql ，(4)則由第三節(jié)定理4推論i，必有某個qj,i jl ，使得Pi |qi ，所以 Pi=qi ；又

5、有某個p/ i k，使得qi | Pi，所以qi = Pi。于是，由式 可知pi二q，從而由式(4) 得到重復上述這一過程，得到k l, Pi qi,i i k 證畢。7. 定理：若設(n)為n的正約數(shù)的個數(shù)，(n)為n的正約數(shù)之和，則有(I) (n)( 11)( 21)g a k 1)(2)(n)占斗g斗P1 1P2 1Pk 18. 推論1使用式(2)中的記號，有(i ) n的正因(約)數(shù)d必有形式d = dP11P22 L Pkk, 1 Z,0 i i,1 i k(ii) n的正倍數(shù)m必有形式9. 推論2設正整數(shù)a與b的標準分解式是a P11 P22 Pkk , b P11 P21 Pkk

6、 ,其中P1, P2, , Pk是互不相同的素數(shù)，i, i (1 ik)都是非負整數(shù)，則10. 推論3 設a, b, c, n是正整數(shù)，ab = cn , (a, b) = 1 ,(5)則存在正整數(shù)u, v，使得a = un, b = vn, c = uv, (u, v) = 1。證明 設c = P11P21 Pkk，其中P1, P2, , Pk是互不相同的素數(shù)，i ( 1 ik)是正整數(shù)。又設12k11ka P1 P2 Pk , b P1 P2 Pk ,其中I, i (1 i k)都是非負整數(shù)。由式 及推論2可知min i, i = 0 , i i = ni, 1 i k,因此，對于每個i

7、(1 ik)，等式i =ni, i = 0 與 i = 0 , i =ni有且只有一個成立。這就證明了推論。證畢。11. 定理：對任意的正整數(shù)m及素數(shù)p，記號p |m表示p |m, p 11 m , 即p是m的標準分解中出現(xiàn)的p的幕.設n 1 , p為素數(shù)，p p | n!，則ap 飛i i PPP這里x表示不超過實數(shù)x的最大整數(shù).由于當p1 n時，則件 0,故上面和 P式中只有有限多個項非零另一種表現(xiàn)形式：設p為任一素數(shù)，在n!中含p的最高乘方次數(shù)記為p n!，則有：證明：由于p是素數(shù)，所有n!中所含p的方次數(shù)等于n!的各個因數(shù)1,2,L ,n所含p的方次數(shù)之總和。由性質10可知，在1,2,

8、L ,n中，有-個p的倍數(shù),pn有2p個p的倍數(shù)，有 3個P的倍數(shù)，L ，當p n p 時， pnm 1pn 2 l o,所以命題成立。 p另證：對于任意固定的素數(shù)p，以p k表示在k的標準分解式中的p的指數(shù)，則以nj表示p(1),p(2),L ,p(n)中等于j的個數(shù)，那么p n! =1 n, 2 n2 3 島 L ,(2)顯然，nj就是在1,2,L , n中滿足pj a并且pj + 1 | a的整數(shù)a的個數(shù)，所以由定理2有將上式代入式(2)，得到即式(1)成立。證畢。二、重要方法證明某些特殊形式的數(shù)不是素數(shù)(或給出其為素數(shù)的必要條件)是初等數(shù)論中較為基本的問題，其方法是應用各種分解技術(如

9、代數(shù)式的分解)，指出所給數(shù)的一個真因子常用分解技術有：(1) 利用代數(shù)式分解(如因式分解)指出其一個真因子；(2) 應用數(shù)的分解(例如算術基本定理)，指出數(shù)的一個真因子；(3) 運用反證法，假定其是素數(shù)，然后利用素數(shù)的性質推出矛盾.三、例題講解例1.證明：無窮數(shù)列10001,100010001,中沒有素數(shù).(教材第13頁例1) 證明：記 an 10Q412 40491,(n 2)，貝Un個1對n分奇偶討論：(1)當n為偶數(shù)時，設n 2k，則an8k 10 110418k8101 10110811041顯然是大于1的整數(shù)，當k 2時，陣空1是大于1的整數(shù)104 1108 1 108 1而當k 1

10、時，a21000113 137是合數(shù).(2)當為奇數(shù)時，設n 2k 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，則由于n 1，所以n2 2 22k 2n 2k, n2 2 22k 2n 2k都是大于1的整數(shù), 故n4 4n是合數(shù).綜上：n44n不是素數(shù).例3.設正整數(shù)a, b, c,d滿足ab cd，證明：a b c d不是素數(shù)證明一：本題不宜采用代數(shù)式的分解來產生所需的分解

11、我們的第一種解 是應用數(shù)的分解，指出abed的一個真因子.由ab ed，可設a 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ù).證明二：由 ab ed，得 b ，因此 abed a e d(a_e)(a_)，因aaaa b e d是整數(shù).若它是一個素數(shù)，設為p，則由(a e)(a d) ap (*)， p |(ae)(a d)故 p|(a e)或 p |(a d)，不妨設，p|(a e)則 a e p，結合(*)式得：a d a，即d 0，這不可能，故結

12、論成立；例 4.設整數(shù) a,b, e,d 滿足 a bed 0，且 a2 ae e2 b2 bd d2證明：ab ed不是素數(shù).(教材第18頁習題3-4)證明：本題運用反證法，設有滿足題設的一組a,b,e,d，使得ab ed為素數(shù)， 將其記為p ab ed，于是a p ed帶入已知條件得到：b由于p是素數(shù)，故p | (b2 e2)或者p | (b2 bd d2)(i)若 p | (b2 e2)，則由 b2 e2 ab ab 2ab 2(ab ed) 2p，推出 b2 e2 p，即 b2 e2 ab ed，從而 b | e(e d)，顯然(b,c) 1 (因為 b2 e2是 素數(shù))故b|(e d

13、)，這與0 e d e b矛盾.(ii ) 若 p|(b2 bd d2)，貝由 0 b2 bd d2 2(ab ed) 2p 知 b2 bd d2 p，故2 2 2 2aac cb bddab cd,進而得到a2acc（c d）ab,b2bdd（d c） ab,于是得到a |c（c d）,b |d（c d）都成立，但又知（ab,cd） 1，故被c d a和b整除. 因0 c d 2a,0 c d 2b從而必須有c d a,c d b，矛盾.例5.證明：若整數(shù)a,b滿足2a2 a 3b2 b，則a b和2a 2b 1都是完全平方 數(shù).證明：已知關系式變形為2（a b）（2a 2b 1） b （

14、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）得右端為（1）b2是一個完全平方數(shù)，故|a b|,|2a 2b 1|均 是完全平方數(shù).下面證明a b 0，我們運用反證法.假設有整數(shù)a,b滿足問題中的等式，但a b 0.因已證明|a b|是一個完全 平方數(shù)故有b a r2，這里r 0 ;結合（1）推出r | b，再由b a r2得出r |

15、 a . 設b b, a r，帶入問題中的等式可得（注意r 0,d印r）2 2a16a1r 3r 1 0（ 2）將上式視為關于a1的二次方程，由求根公式解得a 3r 一 6廠1，因內是整數(shù)， 故由上式知6r2 1是完全平方數(shù).但易知一個完全平方數(shù)被3除得的余數(shù)只能為 0或1；而6r2 1被3除得余數(shù)為2,矛盾.（或者更直接地：由aj被3除得余數(shù)為0或1，故（2）左邊被3除得的余數(shù)是1或2;但（2）的右邊為0,被3整除.矛盾.即（2）對任何整數(shù)ai及r均不成立）從而必須有a b 0,這就證明了本題的結論.注：1.許多數(shù)論問題需證明一個正整數(shù)為 1 （例如，證明整數(shù)的最大公約數(shù) 是1），由此我們常

16、假設所說的數(shù)有一個素因子，利用素數(shù)的銳利性質（3）作進一步論證，以導出矛盾.如例4例6.寫出n 51480的標準分解式，并求它的正約數(shù)的個數(shù)（n）;解：我們有 例7.求最大的正整數(shù)k，使得10k|199!解：因為10 2 5,正整數(shù)k的最大值取決于199!的分解式中所含5的幕指由定理2，199!的標準分解式中所含的5的幕指數(shù)是所以，所求的最大整數(shù)是k 47。例8.設x與y是實數(shù)，則2 x 2y3 xx y y(*)設xx,01，yy,01，則右邊xx yy2x2?y，(1)左邊2x2y 2x2?y2 2 ，如果0，那么顯然有2 2 ;如果1,那么與中至少有一個不小于舟，于是221 。證法因此無

17、論0或1,都有22 ，由此及式（1）和式（2）可以推出式（*）成立.證法二：注意到對任意整數(shù)k及任意實數(shù)k ，即上述不等式中x或y改變一個整數(shù)量，則不等式（*）兩邊改變一個相同的量.故不等式（*）只需證明0 x 1,0 y 1的情形即可.于是問題等價于證明：2x2 y x y下面同證法一例9.一個經典的問題設m,n是非負整數(shù)，證明：(2m)!(2n)!是一個整數(shù). m!n !(mn)!證明：我們只需證明：對每一個素數(shù) p，分母m!n!(m n)!的標準分解中p的幕次，不超過分子(2m)!(2 n)!中p的幕次，由定理知等價于證明2m2nmllll 1ppl 1pnPm nl p事實上我們能夠證

18、明一個更強的命題：設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ù)。(i )設a Pi1 P22L Pkk，b pi1 p21L Pkkb，其中P1, P2,L，Pk是互不相同的素數(shù),i, i(1 i k)都是非負整數(shù)。由定理1推論2，有由此知k(a,b)a, b= Pii 1minPii max i, iab ;其中 p1， p2，L ，其中，對于(1api i ， bi1pk 是互不相同的素數(shù)，(a,b,c)kpii，i1i k) ，有minmax minpi i， ci1pi i ，i1i, i, i (1i k) 都是非負整數(shù)。由定理k(a,b),(a,c)pii ，i1i, max i, i ，i, i, min i, i ，不妨設 imin i , i min i,?i ， 所以i min i, i i