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

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

3、一個計算最大公約數的算法——輾轉相除法，又稱Euclid算法。它是數論中的一個重要方法，在其他數學分支中也有廣泛的應用。,定義 下面的一組帶余數除法，稱為輾轉相除法。,說明：,（1）利用輾轉相除法可以求兩個整數的最大公因數,6、最大公因數的兩個性質,對于兩個以上整數的最大公因數問題，不妨設,本節(jié)最后介紹另外一種求兩個整數最大公因數的方法，先給出下面幾個結果：,即當a與b是正整數時，只要使用被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é) 整除的進一步性質及最小公倍數,例 用輾轉相除法求(125, 17)，以及x，y，使得 125x ? 17y = (1

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

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

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

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

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

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

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

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

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

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

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

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