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

1、數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)質(zhì)數(shù)質(zhì)數(shù)/合數(shù)的概念合數(shù)的概念質(zhì)數(shù)的找法質(zhì)數(shù)的找法/個數(shù)個數(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ù)基本定理 定義定義 一個大于1的整數(shù)，如果它的正因數(shù)只有1和它本身，就叫它質(zhì)數(shù)（或素數(shù)）；否則叫做合數(shù) 由該定義可知，正整數(shù)集合可分三類: 素數(shù)、合數(shù)和1. 定理定理1 1 設(shè)a是任一個大于1的整數(shù)，則a的除1外 最小正因數(shù)q是一質(zhì)數(shù)，并且當a是合數(shù)時 aq 質(zhì)數(shù)質(zhì)數(shù)/合數(shù)的概念和性質(zhì)合數(shù)的概念和性質(zhì)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 證明 若a是素數(shù), 顯然a的大于2的最小因數(shù)就

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

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

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

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

6、大于2的偶數(shù)均可表成為兩個素數(shù)之和”的著名猜想. 我國數(shù)學家陳景潤在已有研究成果的基礎(chǔ)上, 1966年證明并在1973年發(fā)表了“每一個充分大的偶數(shù)都可表為一個素數(shù)及一個不超過兩個素數(shù)乘積之和”的重要論文, 這是至今關(guān)于這一猜想的最好結(jié)果. 有人驗證了在 3.3106以內(nèi)的偶數(shù)對哥德巴赫猜想都是正確的. 但該猜想至今未證明.質(zhì)數(shù)的分布質(zhì)數(shù)的分布數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 定理定理3 3 若p是一質(zhì)數(shù),a是任一整數(shù)，則a能被p整除，或p與a互質(zhì) 證明 因為(p,a)|p , (p,a)=1或(p,a)=p,即p|a,或p與a互質(zhì) 推論推論3.13.1 設(shè) 是n個整數(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）當a=2時，(1)式成立 假定對一切小于a的正整數(shù)(1)式都成立，此時若a是質(zhì)數(shù)，則(1)式對a成立；若a是合數(shù)，則有兩個正整數(shù)b,c滿足a=bc,由假定 適當調(diào)動 的次序即得(1)式，故(1)式對a成

8、立 歸納法，即對任一大于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ù)都能唯一寫成 （3） 其中 （3）式叫做a的標準分解式標準分解

9、式 推論推論4.24.2：設(shè)a是一個大于1的整數(shù)，且則a的正因數(shù)d可以表示成而且當d可以表成上述形式時，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是任意兩個正整數(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ǔ)練習1、證明：若 ,則2、198,252,198,252,3463、判