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

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

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

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

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é) 整除的進(jìn)一步性質(zhì)及最小公倍數(shù),例 用輾轉(zhuǎn)相除法求(125, 17)，以及x，y，使得 125x ? 17y = (1

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

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

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

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

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

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

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

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

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

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

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

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