第二講：算數(shù)基本定理

1、數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)質(zhì)數(shù)質(zhì)數(shù)/合數(shù)的概念合數(shù)的概念質(zhì)數(shù)的找法質(zhì)數(shù)的找法/個(gè)數(shù)個(gè)數(shù)/分布分布/性質(zhì)性質(zhì)算數(shù)基本定理算數(shù)基本定理123第四節(jié)：質(zhì)數(shù)第四節(jié)：質(zhì)數(shù) 算術(shù)基本定理算術(shù)基本定理數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)第四節(jié)：質(zhì)數(shù)第四節(jié)：質(zhì)數(shù) 算術(shù)基本定理算術(shù)基本定理 定義定義 一個(gè)大于1的整數(shù)，如果它的正因數(shù)只有1和它本身，就叫它質(zhì)數(shù)（或素?cái)?shù)）；否則叫做合數(shù) 由該定義可知，正整數(shù)集合可分三類(lèi): 素?cái)?shù)、合數(shù)和1. 定理定理1 1 設(shè)a是任一個(gè)大于1的整數(shù)，則a的除1外 最小正因數(shù)q是一質(zhì)數(shù)，并且當(dāng)a是合數(shù)時(shí) aq 質(zhì)數(shù)質(zhì)數(shù)/合數(shù)的概念和性質(zhì)合數(shù)的概念和性質(zhì)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 證明 若a是素?cái)?shù), 顯然a的大于2的最小因數(shù)就

2、是素?cái)?shù)a; 若a是合數(shù), 則除1和a外還有其它的因數(shù)，令b是這些正因數(shù)中最小者, 可以證明b不是合數(shù)而是素?cái)?shù), 若其不然, b必有大于1且不等于b的因數(shù)c, 于是由c|b和b|c可知c|a, 即c是a的因數(shù),又有1cb, 這與假設(shè)b是a的大于1的最小因數(shù)相矛盾故b不是合數(shù)而是素?cái)?shù)因此，a的大于1的最小因數(shù)b是素?cái)?shù)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 該定理為公元前三世紀(jì)希臘數(shù)學(xué)家厄拉多塞(Eratosthenes)提出的構(gòu)造素?cái)?shù)表方法奠定了理論基礎(chǔ), 后人稱它為厄拉多塞篩法. 近代素?cái)?shù)表都是由此法略加變化構(gòu)造的. 截止 1977年, 最完善的素?cái)?shù)表是查基爾(Den Zagier)作的, 列出所有不大于 50 00

3、0 000的素?cái)?shù).質(zhì)數(shù)的找法質(zhì)數(shù)的找法若若a是合數(shù)是合數(shù), 則則a必有一素因數(shù)小于或等于必有一素因數(shù)小于或等于 a數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 質(zhì)數(shù)有多少？公元前三世紀(jì), 古希臘數(shù)學(xué)家歐幾里德Euclid就證明了素?cái)?shù)有無(wú)窮多個(gè). 定理2 (Euclid) 素?cái)?shù)有無(wú)窮多個(gè). 證明(反證法)假設(shè)素?cái)?shù)是有限多個(gè), 共有n個(gè), 令它們是p1,p2,pn, 并令N= p1p2pn+1. 若N是素?cái)?shù), 則因Npi; 其中1in, 故素?cái)?shù)個(gè)數(shù)最少是n+1個(gè), 這與假設(shè)素?cái)?shù)個(gè)數(shù)為n個(gè)矛盾. 若N不是素?cái)?shù), 則由定理1知, 大于1的最小因數(shù)p是素?cái)?shù). 由于pi|p1p2pn, 但pi不能整除1, 故pi不能整除N, 因此p

4、pi, 其中1in, 所以在p1,p2,pn,還有素?cái)?shù), 這也與已知共有n個(gè)素?cái)?shù)矛盾.質(zhì)數(shù)的個(gè)數(shù)質(zhì)數(shù)的個(gè)數(shù)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 人們對(duì)素?cái)?shù)這塊整數(shù)中的“基石”進(jìn)行大量研究，發(fā)現(xiàn)素?cái)?shù)的分布是很不規(guī)則的，而且越往后越稀疏例如，對(duì)于每個(gè)大于或等于2的整數(shù)n，連續(xù)n-1個(gè)整數(shù)n!2, n!3, , n!n都不是素?cái)?shù). 可見(jiàn)在正整數(shù)序列中, 有任意長(zhǎng)的區(qū)間中不含有素?cái)?shù). 另一方面, 任意兩個(gè)相鄰的正整數(shù)n和nl(n3)中必有一個(gè)不是素?cái)?shù).相鄰兩整數(shù)均為素?cái)?shù)只有 2和 3. 但是 n和n2均為素?cái)?shù)的則有很多, 這樣一對(duì)素?cái)?shù)稱為孿生素?cái)?shù).質(zhì)數(shù)的分布質(zhì)數(shù)的分布數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 例如在100以內(nèi)有七對(duì)孿生素?cái)?shù): (

5、3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73). 又如, 1644年, 法國(guó)數(shù)學(xué)家默森尼(M. Mersenne)研究過(guò)形如2p-1的素?cái)?shù),其中p為素?cái)?shù).人們稱它為默森尼素?cái)?shù), 截止2003年11月17日, 發(fā)現(xiàn)有40個(gè), 其中220996011-1是目前最大素?cái)?shù). 在網(wǎng)上 (/)有個(gè)基金組織資助計(jì)算M. Mersenne)素?cái)?shù)的志愿者. 猜想孿生素?cái)?shù)和默森尼素?cái)?shù)有無(wú)窮多, 但至今都尚未證明.質(zhì)數(shù)的分布質(zhì)數(shù)的分布數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 1742年, 德國(guó)數(shù)學(xué)家哥德巴赫(C.Goldbach)提出了“每個(gè)

6、大于2的偶數(shù)均可表成為兩個(gè)素?cái)?shù)之和”的著名猜想. 我國(guó)數(shù)學(xué)家陳景潤(rùn)在已有研究成果的基礎(chǔ)上, 1966年證明并在1973年發(fā)表了“每一個(gè)充分大的偶數(shù)都可表為一個(gè)素?cái)?shù)及一個(gè)不超過(guò)兩個(gè)素?cái)?shù)乘積之和”的重要論文, 這是至今關(guān)于這一猜想的最好結(jié)果. 有人驗(yàn)證了在 3.3106以內(nèi)的偶數(shù)對(duì)哥德巴赫猜想都是正確的. 但該猜想至今未證明.質(zhì)數(shù)的分布質(zhì)數(shù)的分布數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 定理定理3 3 若p是一質(zhì)數(shù),a是任一整數(shù)，則a能被p整除，或p與a互質(zhì) 證明 因?yàn)?p,a)|p , (p,a)=1或(p,a)=p,即p|a,或p與a互質(zhì) 推論推論3.13.1 設(shè) 是n個(gè)整數(shù)，p是一質(zhì)數(shù)，若p| ,則p一定能整除某一

7、質(zhì)數(shù)在整除中的性質(zhì)質(zhì)數(shù)在整除中的性質(zhì)naaa21naaa,21ka數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 定理定理4 4（算術(shù)基本定理）（算術(shù)基本定理）任一大于1的整數(shù)都能表示成質(zhì)數(shù)的乘積，即任一大于1的整數(shù) 其中 是質(zhì)數(shù)，并且，若 其中 是質(zhì)數(shù)，則算數(shù)基本定理算數(shù)基本定理nnppppppa2121,nppp,21mmqqqqqqa2121,mqqq,21nipqnmii, 2 , 1,數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 證明：（1）當(dāng)a=2時(shí)，(1)式成立 假定對(duì)一切小于a的正整數(shù)(1)式都成立，此時(shí)若a是質(zhì)數(shù)，則(1)式對(duì)a成立；若a是合數(shù)，則有兩個(gè)正整數(shù)b,c滿足a=bc,由假定 適當(dāng)調(diào)動(dòng) 的次序即得(1)式，故(1)式對(duì)a成

8、立 歸納法，即對(duì)任一大于1的整數(shù)(1)式成立。算數(shù)基本定理算數(shù)基本定理nlllpppcpppb2121,nlllppppppbca2121iP數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 若 ，則 因此， ， 故有 ，使得 ，但是質(zhì)數(shù)，故 又 所以 因而 同理可證 ，n=m算數(shù)基本定理算數(shù)基本定理mmqqqqqqa2121,nppp21|1pnppp21mqqq21jkqp ,kjpqqp|,|11kjpqqp11,11,qqppjk11qppqkj11qppqkjmqqq21|1qjkqp ,iiqp 數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 推論推論4.14.1：任一大于1的整數(shù)都能唯一寫(xiě)成 （3） 其中 （3）式叫做a的標(biāo)準(zhǔn)分解式標(biāo)準(zhǔn)分解

9、式 推論推論4.24.2：設(shè)a是一個(gè)大于1的整數(shù)，且則a的正因數(shù)d可以表示成而且當(dāng)d可以表成上述形式時(shí)，d是a的正因數(shù)算數(shù)基本定理算數(shù)基本定理kkpppa2121kii, 2 , 1, 0)(jippjikkpppa2121kii, 2 , 1, 0kkpppd2121kiii, 2 , 1, 0數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 推論推論4.34.3：設(shè)a,b是任意兩個(gè)正整數(shù)，且則其中， 算數(shù)基本定理算數(shù)基本定理kkpppa2121kii, 2 , 1, 0kkpppb2121kii, 2 , 1, 0kkpppba2121),(kkpppba2121,kiiiiiii, 2 , 1),max(),min(數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)小結(jié)a a是合數(shù)是合數(shù) a a是是 的倍數(shù)的倍數(shù)aq 質(zhì)數(shù)的判別和找法質(zhì)數(shù)的判別和找法12算數(shù)基本定理算數(shù)基本定理數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)練習(xí)1、證明：若 ,則2、198,252,198,252,3463、判