初等數(shù)論-第一章

1、一、整除的概念 帶余數(shù)除法,二、最大公因數(shù)與輾轉(zhuǎn)相除法,第一章 整數(shù)的可除性,三、整除的進一步性質(zhì),四、質(zhì)數(shù) 算術基本定理,五、取整函數(shù)及其在數(shù)論中的一個應用,第一節(jié) 整除的概念 帶余數(shù)除法,2、整除的基本定理,定理1（傳遞性）：a?b，b?c ? a?c,定理2：若a，b都是m的倍數(shù)，則a?b都是m的倍數(shù),3、帶余數(shù)除法,帶余數(shù)除法的應用舉例,例1 證明形如3n-1的數(shù)不是平方數(shù)。,例2、任意給出的5個整數(shù)中，必有

2、3個數(shù)之和被3整除。,第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法,2、任意整數(shù)的最大公因數(shù)可轉(zhuǎn)化為正整數(shù)來討論,3、下面先討論兩個非負整數(shù)的最大公因數(shù),定理2、設b是任一正整數(shù)，則（i)0與b的公因數(shù)就是,b的因數(shù)，反之， b的因數(shù)也就是0與b的公因數(shù)。,(ii)(0,b)=b,4、定理3 設a,b,c是三個不全為零的整數(shù)，且,a=bq+c,其中q是非零整數(shù)，則a,b與b,c有相同的公因數(shù)，,因而(a,b)=(b,c),5、下面要介紹

3、一個計算最大公約數(shù)的算法——輾轉(zhuǎn)相除法，又稱Euclid算法。它是數(shù)論中的一個重要方法，在其他數(shù)學分支中也有廣泛的應用。,定義 下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法。,說明：,（1）利用輾轉(zhuǎn)相除法可以求兩個整數(shù)的最大公因數(shù),6、最大公因數(shù)的兩個性質(zhì),對于兩個以上整數(shù)的最大公因數(shù)問題，不妨設,本節(jié)最后介紹另外一種求兩個整數(shù)最大公因數(shù)的方法，先給出下面幾個結果：,即當a與b是正整數(shù)時，只要使用被2除的除法運算和減法運算就可以計算

4、出(a,b),例1、求（12345,678）,解： （12345,678）=（12345，339）,=（12006,339）,=（6003,339）,=（5664,339）,=（177,339）,=（177,162）,=（177，81）,=（96,81）,=（3,81）=3,所以，命題得證。,第三節(jié) 整除的進一步性質(zhì)及最小公倍數(shù),例 用輾轉(zhuǎn)相除法求(125, 17)，以及x，y，使得 125x ? 17y = (1

5、25, 17)。,解 做輾轉(zhuǎn)相除法：,,,則,對于兩個以上整數(shù)的最小公倍數(shù)問題，不妨設,注：多項式的帶余除法類似于整數(shù)的帶余除法,第四節(jié) 質(zhì)（素）數(shù) 算術基本定理,,一、質(zhì)（素）數(shù),1、定義 一個大于1的整數(shù)，如果它的正因數(shù)只有1,及它本身，就叫做質(zhì)數(shù)（或素數(shù)）；否則就叫合數(shù)。,2、與素數(shù)相關的性質(zhì)定理,注：利用第三節(jié)推論2.2證明。,證：必要性顯然。,對于一個給定的整數(shù)，我們根據(jù)上述定理不僅可以,判別它是否

6、是素數(shù)，且還可以找出所有不大于它的素數(shù),把1劃去，剩下第一個數(shù)是2,2是素數(shù)。從2起劃去它,后面所有2的倍數(shù)，剩下的第一個數(shù)是3，它不是2的倍,所以它是素數(shù)。,依次，當我們把所有的不大于,的素數(shù)。,這種方法是希臘時代幼拉脫斯展納發(fā)明的，,好像用篩子篩出素數(shù)一樣，稱幼拉脫斯展納篩法。,,數(shù)的素性檢驗方法問題在近幾年得到了飛速的發(fā)展,,若用計算機編成程序,對于10位數(shù),幾乎瞬間即可完成,,對于一個20位數(shù),則需要2個小時,對于一個50位數(shù)就

7、需,要一百億年,令人吃驚的是,要檢驗一個一百位數(shù),需要,的時間就猛增到10^36年.到了1980年,這種困難的情況,,得到了改觀,阿德曼(Adleman),魯梅利(Rumely),科恩,(Cohen),和倫斯特拉(Lenstra)研究出一種非常復雜的,過去,要檢驗一個數(shù)是否是素數(shù)，最簡單方法是試除法，,,檢驗一個20位數(shù)只消10秒鐘,對于一個50位數(shù)用15秒鐘,,100位數(shù)用40秒鐘,如果要他檢驗一個1000位數(shù),只要用,一個星期也就夠

8、了.但是大部分的素性檢驗法都不能分,解出因數(shù)來,只能回答一個數(shù)是否是素數(shù).,技巧,現(xiàn)在以他們的名字的首字母命名的ARCL檢驗法,定理3、素數(shù)的個數(shù)是無窮的。,注：2000多年前，古希臘數(shù)學家歐幾里得（前330-,前275），著有《幾何原本》，他在此書中率先證明了,素數(shù)的無限性，這個證明一直被當作數(shù)學證明的典范，,受到歷代數(shù)學家的推崇，因為這一定理及其證明既簡潔、,優(yōu)美而不失深刻。其證明思路如下：,證明: 假設正整數(shù)中只有

9、有限個質(zhì)數(shù)，設為,關于素數(shù)的個數(shù)，有著名的素數(shù)定理：,下面列舉的數(shù)字也可以說明定理的真實性。,素數(shù)定理是古典素數(shù)分布的理論核心，這個定理,大約是在1798年高斯與勒讓德作為猜想提出的。之后,許多學者都做過深入的研究，但都沒有成功。1896年，,法國數(shù)學家哈達馬及比利時數(shù)學家德.瓦利-普斯因同時,獨立地證明了它，他們是用黎曼zata函數(shù)獲得解決的。,1949年，挪威數(shù)學家賽爾伯格與匈牙利數(shù)學家愛爾特希,第一次給出不用很多函數(shù)論知識，也可以

10、說是一個初等,的證明。他們的證明是依靠一個不等式，但是這個所謂,的初等證明也是非常復雜的。1950年，賽爾伯格還因為,這個證明獲得了菲爾茨獎。,下面介紹與素數(shù)有關的某些問題,1、費馬數(shù)：,費馬在1640年設計了一個公式，給出一些素數(shù)。,然而他大錯特錯了！只有五個素數(shù)被發(fā)現(xiàn)是遵從于這個,公式的，它們是3,5,17,257和65537,分別對應于n=0,1,2,3,4,2、費馬數(shù)與尺規(guī)作圖的聯(lián)系：,尺規(guī)作圖是指用沒有刻度的直尺和圓規(guī)作圖。尺

11、規(guī)作圖,瑞士科學家歐拉于1732年舉出,故費馬的猜測不正確。,規(guī)作圖使用的直尺和圓規(guī)帶有想像性質(zhì)，跟現(xiàn)實中的并,非完全相同：1、直尺必須沒有刻度，無限長，且只能,使用直尺的固定一側。只可以用它來將兩個點連在一起，,不可以在上畫刻度； 2、圓規(guī)可以開至無限寬，但上面,亦不能有刻度。它只可以拉開成之前構造過的長度。,只準許使用有限次，來解決不同的平面幾何作圖題。尺,是起源于古希臘的數(shù)學課題。只使用圓規(guī)和直尺，并且,一般地，任意正n邊形有以下

12、結論：,3、梅森數(shù),梅森數(shù)(Mersenne number)是指形如2^p－1的正整數(shù)，,其中指數(shù)p是素數(shù)，常記為Mp 。若Mp是素數(shù)，則稱,為梅森素數(shù)。,早在公元前300多年，古希臘數(shù)學家歐幾里得,就開創(chuàng)了研究2^P－1的先河，他在名著《幾何原本》,第九章中論述完美數(shù)時指出：如果2^P－1是素數(shù)，,則(2^p－1)2^(p－1)是完美數(shù)。,梅森在歐幾里得、費馬等人的有關研究的基礎上 ，對,2^P－1作了大量的計算、驗證工作，并于164

13、4年在他的,《物理數(shù)學隨感》一書中斷言：對于p=2，3，5，7，,13，17，19，31，67，127，257時，2^P－1是素數(shù),而對于其他所有小于257的數(shù)時，2^P－1是合數(shù)。,前面的7個數(shù)屬于被證實的部分，是他整理前人的工作,得到的；而后面的4個數(shù)屬于被猜測的部分。,值得提出的是：雖然梅森的斷言中包含著若干錯誤，,但他的工作極大地激發(fā)了人們研究2^P－1型素數(shù)的熱情，,在梅森素數(shù)的基礎研究方面，法國數(shù)學家魯卡斯和美國,數(shù)學家雷默

14、都做出了重要貢獻；以他們命名的“魯卡斯-,雷默方法”是目前已知的檢測梅森素數(shù)素性的最佳方法。,此外，中國數(shù)學家和語言學家周海中給出了梅森素數(shù)分,布的精確表達式，為人們尋找梅森素數(shù)提供了方便；這,一研究成果被國際上命名為“周氏猜測”。,2005年，美國數(shù)學家C.Cooper和S.Boone領導的科,研小組發(fā)現(xiàn)了第43個梅森素數(shù)，該素數(shù)有9 152 052位數(shù)，,是目前知道的最大的素數(shù)，,該素數(shù)是：,關于梅森數(shù)有下列的一個命題：,二、算術基

15、本定理,1、定理4 任一大于1的整數(shù)能表成素數(shù)的乘積，,即任一大于1的整數(shù),此為算術基本定理。,2、正整數(shù)的標準分解式,推論4.1 任一大于1的整數(shù)a能夠唯一地寫成,推論4.2 設a是任一大于1的整數(shù)，且,推論4.3 設a,b是任意兩個正整數(shù)，且,注：利用推論容易證明：,定理5 設a是任一大于1的正整數(shù),,第五節(jié) 函數(shù)[x],{x}及其在數(shù)論中的一個應用,一、取整函數(shù)及性質(zhì),1、取整函數(shù)[x]的定義:,函數(shù)[x

16、]與{x}是對于一切實數(shù)都有定義的函數(shù)，函數(shù),[x]的值等于不大于x的最大整數(shù)；,函數(shù){x}的值是x-[x].,把[x]叫做x的整數(shù)部分，{x}叫做x的小數(shù)部分。,問題：這兩個函數(shù)的圖像如何？,2、取整函數(shù)的簡單性質(zhì),例題,則原命題等價于證,注：此為厄米特恒等式。,二、取整函數(shù)的一個應用,例3、求50！中3的最高冪,[3（50?。?16+5+1],例4、求1000！的十進制表示式中末尾連續(xù)零的個數(shù),解：1000！的十進制表示式中因子5的