初等數(shù)論ppt (1)

1、初等數(shù)論,一、數(shù)論發(fā)展史 數(shù)論是研究整數(shù)性質(zhì)的一門(mén)很古老的數(shù)學(xué)分支， 其初等部分是以整數(shù)的整除性為中心的，包括整除性、不定方程、同余式、連分?jǐn)?shù)、素?cái)?shù)（即整數(shù)）分布 以及數(shù)論函數(shù)等內(nèi)容，統(tǒng)稱(chēng)初等數(shù)論（Elementary Number Theory）。,初等數(shù)論的大部分內(nèi)容早在古希臘歐幾里德的《 幾何原本》中就已出現(xiàn)。歐幾里得證明了素?cái)?shù)有無(wú)窮多個(gè)，他還給出求兩個(gè)自然數(shù)的最大公約數(shù)的方法， 即所謂歐幾里得算法。我國(guó)古代在數(shù)論方面

2、亦有杰出之貢獻(xiàn)，現(xiàn)在一般數(shù)論書(shū)中的“中國(guó)剩余定理”正是我國(guó)古代《孫子算經(jīng)》中的下卷第26題，我國(guó)稱(chēng)之為“孫子定理”。,近代初等數(shù)論的發(fā)展得益于費(fèi)馬、歐拉、拉格朗日、勒讓德和高斯等人的工作。1801年，高斯的《算術(shù)探究》是數(shù)論的劃時(shí)代杰作。 “數(shù)學(xué)是科學(xué)之王，數(shù)論是數(shù)學(xué)之王”。 -----高斯,由于自20世紀(jì)以來(lái)引進(jìn)了抽象數(shù)學(xué)和高等分析的巧妙工具，數(shù)論得到進(jìn)一步的發(fā)展，從而開(kāi)闊了新的研究領(lǐng)域，出現(xiàn)了代數(shù)數(shù)論、解析數(shù)論、幾何

3、數(shù)論等 新分支。而且近年來(lái)初等數(shù)論在計(jì)算器科學(xué)、組合數(shù)學(xué)、密碼學(xué)、代數(shù)編碼、計(jì)算方法等領(lǐng)域內(nèi)更得到了 廣泛的應(yīng)用，無(wú)疑同時(shí)間促進(jìn)著數(shù)論的發(fā)展。,二 幾個(gè)著名數(shù)論難題,初等數(shù)論是研究整數(shù)性質(zhì)的一門(mén)學(xué)科，歷史上遺留下來(lái)沒(méi)有解決的大多數(shù)數(shù)論難題其問(wèn)題本身容易搞懂，容易引起人的興趣，但是解決它們卻非常困難。,其中，非常著名的問(wèn)題有：哥德巴赫猜想 ；費(fèi)爾馬大定理 ；孿生素?cái)?shù)問(wèn)題 ；完全數(shù)問(wèn)題等。,1742年,由德國(guó)中學(xué)教師哥德巴赫在教學(xué)中首

4、先發(fā)現(xiàn)的。1742年6月7日，哥德巴赫寫(xiě)信給當(dāng)時(shí)的大數(shù)學(xué)家歐拉,正式提出了以下的猜想： 一個(gè)大于6的偶數(shù)可以表示為不同的兩個(gè)質(zhì)數(shù)之和。 陳景潤(rùn)在1966年證明了“哥德巴赫猜想”的“一個(gè)大偶數(shù)可以表示為一個(gè)素?cái)?shù)和一個(gè)不超過(guò)兩個(gè)素?cái)?shù)的乘積之和”〔所謂的1+2〕，是篩法的光輝頂點(diǎn)，至今仍是“哥德巴赫猜想”的最好結(jié)果。,1、哥德巴赫猜想：,2、費(fèi)爾馬大定理：,費(fèi)馬是十七世紀(jì)最卓越的數(shù)學(xué)家之一，他在數(shù)學(xué)許多領(lǐng)域中都有極大的貢獻(xiàn)，因?yàn)樗?/p>

5、本行是專(zhuān)業(yè)的律師，世人冠以“業(yè)余王子”之美稱(chēng)。在三百七十多年前的某一天，費(fèi)馬正在閱讀一本古希臘數(shù)學(xué)家戴奧芬多斯的數(shù)學(xué)書(shū)時(shí)，突然心血來(lái)潮在書(shū)頁(yè)的空白處，寫(xiě)下一個(gè)看起來(lái)很簡(jiǎn)單的定理。,經(jīng)過(guò)8年的努力，英國(guó)數(shù)學(xué)家 安德魯·懷爾斯 終于在1995年完成了該定理的證明。,3、孿生素?cái)?shù)問(wèn)題,存在無(wú)窮多個(gè)素?cái)?shù) p, 使得 p+2 也是素?cái)?shù)。,究竟誰(shuí)最早明確提出這一猜想已無(wú)法考證，但是1849年法國(guó)數(shù)學(xué) Alphonse de Po

6、lignac（阿爾方·波利尼亞克 ） 提出猜想：對(duì) 于任何偶數(shù) 2k, 存在無(wú)窮多組以2k為間隔的素?cái)?shù)。對(duì)于 k=1，這就是孿生素?cái)?shù)猜想，因此人們有時(shí)把 Alphonse de Polignac 作為孿生素?cái)?shù)猜想的提出者。不同的 k 對(duì)應(yīng)的素?cái)?shù)對(duì)的命名也很有趣，k=1 我們已經(jīng)知道叫做孿生素?cái)?shù)； k=2 (即間隔為4) 的素?cái)?shù)對(duì)被稱(chēng)為 cousin prime ；而 k=3 (即間隔為 6) 的素?cái)?shù)對(duì)竟然被稱(chēng)為 sexy pr

7、ime (不過(guò)別想歪了，之所以稱(chēng)為 sexy prime 其實(shí)是因?yàn)?sex 正好是拉丁文中的 6。),1966年利用篩法 (sieve method) 陳景潤(rùn)證明了： 存在無(wú)窮多個(gè)素?cái)?shù) p， 使得 p+2 要么是素?cái)?shù)， 要么是兩個(gè)素?cái)?shù)的乘積。 一般認(rèn)為， 由于篩法本身的局限性， 這一結(jié)果在篩法范圍內(nèi)很難被超越,2013年，5月14日，《自然》（Nature）雜志在線(xiàn)報(bào)道張益唐證明了“存在無(wú)窮多個(gè)之差小于7000萬(wàn)的素?cái)?shù)對(duì)”，這一研究隨

8、即被認(rèn)為在孿生素?cái)?shù)猜想這一終極數(shù)論問(wèn)題上取得了重大突破，甚至有人認(rèn)為其對(duì)學(xué)界的影響將超過(guò)陳景潤(rùn)的“1+2”證明。,4、最完美的數(shù)——完全數(shù)問(wèn)題,下一個(gè)具有同樣性質(zhì)的數(shù)是28, 28=1+2+4+7+14.接著是496和8128.他們稱(chēng)這類(lèi)數(shù)為完美數(shù). 歐幾里德在大約公元前350-300年間證明了:,注意以上談到的完全數(shù)都是偶完全數(shù),至今仍然不知道有沒(méi)有奇完全數(shù)。,完美數(shù)又稱(chēng)為完全數(shù),最初是由畢達(dá)哥拉斯的信徒發(fā)現(xiàn)的,他們注意到

9、,數(shù)6有一個(gè)特性,它等于它自己的因子(不包括它自身)的和， 如：6=1+2+3.,三、我國(guó)古代數(shù)學(xué)的偉大成就,公元前100多年，漢朝人撰，是一部既談天體又談數(shù)學(xué)的天文歷算著作，主要討論蓋天說(shuō)，提出了著名的“勾三股四弦五”這個(gè)勾股定理的一個(gè)特例。,1、周髀算經(jīng),2、孫子算經(jīng) 約成書(shū)于四、五世紀(jì)，作者生平和編寫(xiě)年代都不清楚?，F(xiàn)在傳本的《孫子算經(jīng)》共三卷。卷上敘述算籌記數(shù)的縱橫相間制度和籌算乘除法則，卷中舉例說(shuō)明籌算分?jǐn)?shù)算法

10、和籌算開(kāi)平方法。卷下第31題，可謂是后世“雞兔同籠”題的始祖，后來(lái)傳到日本，變成“鶴龜算”。,具有重大意義的是卷下第26題：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？《孫子算經(jīng)》不但提供了答案，而且還給出了解法。南宋大數(shù)學(xué)家秦九韶則進(jìn)一步開(kāi)創(chuàng)了對(duì)一次同余式理論的研究工作，推廣“物不知數(shù)”的問(wèn)題。德國(guó)數(shù)學(xué)家高斯﹝1777-1855﹞于1801年出版的《算術(shù)探究》中明確地寫(xiě)出了上述定理。1852年，

11、英國(guó)基督教士偉烈亞士將《孫子算經(jīng)》中物不知數(shù)問(wèn)題的解法傳到歐洲，1874年馬蒂生指出孫子的解法符合高斯的定理，從而在西方的數(shù)學(xué)史里將這一個(gè)定理稱(chēng)為“中國(guó)剩余定理” 。,周髀算經(jīng),孫子算經(jīng),1983年在湖北省江陵縣張家山，出土了一批西漢初年，即呂后至文帝初年的竹簡(jiǎn)，共千余支。經(jīng)初步整理，其中有律令、《脈書(shū)》、《引書(shū)》、歷譜、日書(shū)等多種古代珍貴的文獻(xiàn)，還有一部數(shù)學(xué)著作，據(jù)寫(xiě)在一支竹簡(jiǎn)背面的字跡辨認(rèn)，這部竹簡(jiǎn)算書(shū)的書(shū)名叫《算

12、數(shù)書(shū)》。 《算數(shù)書(shū)》是中國(guó)現(xiàn)已發(fā)現(xiàn)的最古的一部算書(shū)，大約比現(xiàn)有傳本的《九章算術(shù)》還要早近二百年，而且《九章算術(shù)》是傳世抄本或刊書(shū)，《算數(shù)書(shū)》則是出土的竹筒算書(shū)，屬于更可珍貴的第一手資料，所以《算數(shù)書(shū)》引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，目前正在被深入研究之中。,3、算數(shù)書(shū),《數(shù)術(shù)記遺》相傳是漢末徐岳所作，亦有數(shù)學(xué)史家認(rèn)為本書(shū)是北周甄鸞自著。 《數(shù)術(shù)記遺》把大數(shù)的名稱(chēng)按不同的涵義排列三個(gè)不同的數(shù)列，另一部份是關(guān)于一個(gè)

13、幻方的清楚的說(shuō)明，它成為數(shù)論中這一發(fā)現(xiàn)的最古的文字記載之一，書(shū)中至少提到了四種算盤(pán)，因此它是談到算盤(pán)的最古老的書(shū)籍。,4、數(shù)術(shù)記遺,算數(shù)書(shū),數(shù)術(shù)記遺 中的算盤(pán),根據(jù)研究，西漢的張蒼 、耿壽昌曾經(jīng)做過(guò)增補(bǔ)和整理，其時(shí)大體已成定本。最后成書(shū)最遲在東漢前期。九章算術(shù)將書(shū)中的所有數(shù)學(xué)問(wèn)題分為九大類(lèi)，就是“九章”。 三國(guó)時(shí)期的劉徽為《九章》作注，加上自己心得體會(huì)，使其便于了解，可以流傳下來(lái)。 唐代的李淳風(fēng)又重新做注(

14、656年)，作為《算數(shù)十經(jīng)》之一，版刻印刷，作為通用教材。,5、九章算術(shù),《九章算術(shù)》的出現(xiàn)，標(biāo)志著我國(guó)古代數(shù)學(xué)體系的正式確立，當(dāng)中有以下的一些特點(diǎn)：1.是一個(gè)應(yīng)用數(shù)學(xué)體系，全書(shū)表述為應(yīng)用問(wèn)題集的形式；2.以算法為主要內(nèi)容，全書(shū)以問(wèn)、答、術(shù)構(gòu)成，“術(shù)”是主要需闡述的內(nèi)容；3.以算籌為工具。 《九章算術(shù)》取得了多方面的數(shù)學(xué)成就，包括：分?jǐn)?shù)運(yùn)算、比例問(wèn)題、雙設(shè)法、一些面積、體積計(jì)算、一次方程組解法、負(fù)數(shù)概念的引入及負(fù)

15、數(shù)加減法則、開(kāi)平方、開(kāi)立方、一般二次方程解法等?！毒耪滤阈g(shù)》的思想方法對(duì)我國(guó)古代數(shù)學(xué)產(chǎn)生了巨大的影響。自隋唐之際，《九章算術(shù)》已傳入朝鮮、日本，現(xiàn)在更被譯成多種文字。,6、海島算經(jīng) 《海島算經(jīng)》由三國(guó)劉徽所著，最初是附于他所注的《九章算術(shù)》（263）之后，唐初開(kāi)始單行，體例亦是以應(yīng)用問(wèn)題集的形式。 全書(shū)共9題，全是利用測(cè)量來(lái)計(jì)算高深廣遠(yuǎn)的問(wèn)題，首題測(cè)算海島的高、遠(yuǎn)，故得名?！逗u算經(jīng)》是中國(guó)最早的一部測(cè)量

16、數(shù)學(xué)事著，亦為地圖學(xué)提供了數(shù)學(xué)基礎(chǔ)。,7、算經(jīng)十書(shū) 　 唐代國(guó)子監(jiān)內(nèi)設(shè)立算學(xué)館，置博士、助教指導(dǎo)學(xué)生學(xué)習(xí)數(shù)學(xué)，規(guī)定《周髀算經(jīng)》、《九章算術(shù)》、《孫子算經(jīng)》、《五曹算經(jīng)》、《夏侯陽(yáng)算經(jīng)》、《張丘建算經(jīng)》、《海島算經(jīng)》、《五經(jīng)算術(shù)》、《綴術(shù)》、《緝古算經(jīng)》十部算經(jīng)為課本，用以進(jìn)行數(shù)學(xué)教育和考試，后世通稱(chēng)為算經(jīng)十書(shū)．算經(jīng)十書(shū)是中國(guó)漢唐千余年間陸續(xù)出現(xiàn)的十部數(shù)學(xué)著作．北宋時(shí)期（1084年），曾將一部算經(jīng)刊刻發(fā)行，這是世界上

17、最早的印刷本數(shù)學(xué)書(shū)．（此時(shí)《綴術(shù)》已經(jīng)失傳，實(shí)際刊刻的只有九種）。,8、測(cè)圓海鏡《測(cè)圓海鏡》由中國(guó)金、元時(shí)期數(shù)學(xué)家 李冶所著，成書(shū)于1248年。全書(shū)共有12卷，170問(wèn)。這是中國(guó)古代論述容圓的一部專(zhuān)箸，也是天元術(shù)的代表作。《測(cè)圓海鏡》所討論的問(wèn)題大都是已知 勾股形而求其內(nèi)切圓、旁切圓等的直徑一類(lèi)的問(wèn)題。在《測(cè)圓海鏡》問(wèn)世之前，我國(guó)雖有文字代表未知數(shù)用以列方程和多項(xiàng)式的工作，但是沒(méi)有留下很有系統(tǒng)的記載。李冶在《測(cè)圓海鏡》中系統(tǒng)而概

18、栝地總結(jié)了天元術(shù)，使文詞代數(shù)開(kāi)始演變成符號(hào)代數(shù)。 所謂天元術(shù)，就是設(shè)“天元一”為未知數(shù)，根據(jù)問(wèn)題的已知條件，列出兩個(gè)相等的多項(xiàng)式，經(jīng)相減后得出一個(gè)高次方式程，稱(chēng)為天元開(kāi)方式，這與現(xiàn)代設(shè)x為未知數(shù)列方程一樣。歐洲的數(shù)學(xué)家，到了16世紀(jì)以后才完全作到這一點(diǎn)。,測(cè)圓海鏡,費(fèi)馬 [法]1601-1665，是數(shù)學(xué)史上最偉大的業(yè)余數(shù)學(xué)家，提出了費(fèi)馬大、小定理；在坐標(biāo)幾何，無(wú)窮小，概率論等方面有巨大貢獻(xiàn)。,哥德巴赫 1690-1764，

19、德國(guó)數(shù)學(xué)家；曾擔(dān)任中學(xué)教師，1725年到俄國(guó)，被選為彼得堡科學(xué)院院士.,希爾伯特[德]1862～1943，他領(lǐng)導(dǎo)的數(shù)學(xué)學(xué)派是19世紀(jì)末20世紀(jì)初數(shù)學(xué)界的一面旗幟，希爾伯特被稱(chēng)為“數(shù)學(xué)界的無(wú)冕之王”。著《數(shù)論報(bào)告》、《幾何基礎(chǔ)》、《線(xiàn)性積分方程一般理論基礎(chǔ)》.,華羅庚1910—1985，是中國(guó)解析數(shù)論、矩陣幾何學(xué)、典型群、自安函數(shù)論等多方面研究的創(chuàng)始人和開(kāi)拓者。以華氏命名的數(shù)學(xué)科研成果很多。被列為芝加哥科學(xué)技術(shù)博物

20、館中當(dāng)今世界88位數(shù)學(xué)偉人之一。,陳景潤(rùn)1933－1996，主要研究解析數(shù)論，他研究哥德巴赫猜想和其他數(shù)論問(wèn)題的成就，至今仍然在世界上遙遙領(lǐng)先。其成果也被稱(chēng)之為陳氏定理。,王元1930－50年代至60年代初，首先在中國(guó)將篩法用于哥德巴赫猜想研究，并證明了命題3+4，1957年又證明2+3，這是中國(guó)學(xué)者首次在此研究領(lǐng)域躍居世界領(lǐng)先地位.,數(shù)論是以嚴(yán)格和簡(jiǎn)潔著稱(chēng)，內(nèi)容既豐富又深刻。我將會(huì)介紹數(shù)論中最基本的概念和理論，希望大家能對(duì)這

21、門(mén)學(xué)問(wèn)產(chǎn)生興趣，并且對(duì)中小學(xué)時(shí)代學(xué)習(xí)過(guò)的一些基本概念，例如整除性、最大公因子、最小公倍數(shù)、輾轉(zhuǎn)相除法等，有較深入的了解。,第一章 整數(shù)的整除性第一節(jié) 整除的概念,一、基本概念 1、自然數(shù)、整數(shù) 2、正整數(shù)、負(fù)整數(shù) 3、奇數(shù)、偶數(shù)一個(gè)性質(zhì)： 整數(shù)+整數(shù)=整數(shù) 整數(shù)-整數(shù)=整數(shù) 整數(shù)*整數(shù)=整數(shù),,,關(guān)于奇數(shù)和偶數(shù)性質(zhì)：1.奇數(shù)+奇數(shù)=偶數(shù)； 奇數(shù)+偶數(shù)=奇數(shù)； 偶數(shù)+偶數(shù)=偶數(shù)；2

22、.兩個(gè)數(shù)之和是奇（偶）數(shù)，則這兩個(gè)數(shù)的奇偶性相反（同）。3.若干個(gè)整數(shù)之和為奇數(shù)，則這些數(shù)中必有奇數(shù)，且奇數(shù)的個(gè)數(shù)為奇數(shù)個(gè)；若干個(gè)整數(shù)之和為偶數(shù)，則這些數(shù)中若有奇數(shù)，奇數(shù)的個(gè)數(shù)必為偶數(shù)個(gè)。,關(guān)于奇數(shù)和偶數(shù)性質(zhì)：4.奇數(shù)×奇數(shù)=奇數(shù)； 奇數(shù)×偶數(shù)=偶數(shù)； 偶數(shù)×偶數(shù)=偶數(shù)；5.若干個(gè)整數(shù)之積為奇數(shù)，則這些數(shù)必為奇數(shù)；若干個(gè)整數(shù)之積為偶數(shù)，則這些數(shù)中至少有一個(gè)是偶數(shù)。6.若a是整數(shù)，則|a| 與

23、a 有相同的奇偶性。7.若a ，b 是整數(shù)，則a +b 與a -b 奇偶性相同。,例1 在1,2,3，? ，1998,1999這1999個(gè)數(shù)的前面任意添加一個(gè)正號(hào)或負(fù)號(hào)，問(wèn)它們的代數(shù)和是奇數(shù)還是偶數(shù)？例2 設(shè)n 為奇數(shù)， 是1,2， ? ，n 的任意一個(gè)排列，證明 必是偶

24、數(shù)。,例3 將正方形ABCD分割成 個(gè)相等的小方格（n 是正整數(shù)），把相對(duì)的頂點(diǎn)A,C染成紅色，B,D染成藍(lán)色，其他交點(diǎn)任意染成紅藍(lán)兩色中的一種顏色，證明：恰有三個(gè)頂點(diǎn)同顏色的小方格的數(shù)目必是偶數(shù)。,例4 設(shè)正整數(shù)d 不等于2,5,13，證明集合 中可以找到兩個(gè)數(shù)a ，b ，使得a b-1 不是完全平方數(shù)。,,二、整除,1、定義：設(shè)a，b是整數(shù)，b≠0。如果存在一個(gè)整數(shù)q使得

25、等式： a=bq 成立，則稱(chēng)b能整除a或a能被b整除，記b∣a；如果這樣的q不存在，則稱(chēng)b不能整除a，記為b a。,注：顯然每個(gè)非零整數(shù)a都有約數(shù) ?1，?a，稱(chēng)這四個(gè)數(shù)為a的平凡約數(shù)，a的另外的約數(shù)稱(chēng)為非平凡約數(shù)。,,,素?cái)?shù)：定義 設(shè)整數(shù)n≠0，±1.如果除了顯然因數(shù)±1，±n以外，n沒(méi)有其他因數(shù)，那么，n叫做素?cái)?shù)（或質(zhì)數(shù)或不可約數(shù)），否則，n叫做合數(shù).

26、規(guī)定：若沒(méi)有特殊說(shuō)明，素?cái)?shù)總是指正整數(shù)，通常寫(xiě)成p或 p1， p2，…， pn. 例 整數(shù)2，3，5，7都是素?cái)?shù)，而整數(shù)4，6，8，10，21都是合數(shù).,2、整除的性質(zhì),設(shè)a，b，c是整數(shù) （1）a ∣ a （2）如果 a ∣ b ， b ∣ c ，則a ∣ c （3）如果 a ∣b ， a ∣c ,則對(duì)任意整數(shù)m，n 有a ∣mb+cn.,（4）如果a ∣ c ，則對(duì)任何整數(shù)b ， a ∣ b c.

27、 （5）若（ a，b ）=1，且a ∣ b c，則a ∣ c （6）若（ a，b ）=1，且a ∣c， b ∣ c則a b ∣ c （7）若（ a，b ）=1，且a b ∣c，則a ∣c， b ∣ c,（8）若在等式 中，除某一項(xiàng)外，其余各項(xiàng)都能被c整除，則這一項(xiàng)也能被c整除。,（3）素?cái)?shù)判定法則：設(shè)n是一個(gè)正整數(shù)，如果對(duì)所有的素?cái)?shù)p≤ ，

28、都有p n，則n一定是素?cái)?shù).,（1）設(shè)p為素?cái)?shù) ，若p ∣ b a ，則p ∣a 或 p ∣b .（2） p|a 或 (p，a)=1 . p ? ? p?a,常用結(jié)論：,（4） 任何大于1的整數(shù)a都至少有一個(gè)素約數(shù)。,推論 任何大于1的合數(shù)a必有一個(gè)不超過(guò) 的素約數(shù)。,,,,例6 證明：121 ，n?Z。,,10以?xún)?nèi)

29、的素?cái)?shù)是 2,3,5,7，用它們除100以?xún)?nèi)大于10的數(shù)，刪去所有能被它們整除的數(shù)，剩下的(含2,3,5, 7在內(nèi))就是100以?xún)?nèi)的所有素?cái)?shù)．,表19.2 篩 法,最后剩下2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89和97 . 這25個(gè)數(shù)就是100 以?xún)?nèi)的全部素?cái)?shù)．再用這

30、25個(gè)素?cái)?shù)除1002＝10000以?xún)?nèi)大于100的數(shù)，刪去所有能被它們整除的數(shù)，可以得到10000以?xún)?nèi)的所有素?cái)?shù)．重復(fù)這個(gè)做法可以得到任意給定的正整數(shù)以?xún)?nèi)的所有素?cái)?shù)．這個(gè)方法叫做埃拉托斯特尼(Eratosthene)篩法．,人們一直在尋找更大的素?cái)?shù)。近代已知的最大素?cái)?shù)差不多總是形如 2n – 1 的數(shù)。當(dāng)n是合數(shù)時(shí)， 2n – 1 一定是合數(shù)．設(shè)n=ab，其中a>1,b>1，有,當(dāng)n為素?cái)?shù)時(shí), 22 – 1=3, 23

31、 – 1＝7, 24 – 1＝31, 27 – 1=127 都是素?cái)?shù), 而 211 – 1 = 2047 = 23 x 89 是合數(shù)．,設(shè)P為素?cái)?shù), 稱(chēng)如 2p–1的數(shù)為梅森(Matin Merdenne)數(shù).到 2002年為止找到的最大梅森素?cái)?shù)是213466917 – 1, 這個(gè)數(shù)有 4百萬(wàn)位．,可除性判別方法,判別方法1：（整數(shù)被2整除） 如果一個(gè)整數(shù)的末尾數(shù)字能被2整除，則該數(shù)能被2整除。即：若2∣a0，

32、，則2 ∣N.判別方法2：（整數(shù)被5整除） 如果一個(gè)整數(shù)的末尾數(shù)字能被5整除，則該數(shù)能被5整除。即：若5∣a0，，則5∣N.判別方法3：（整數(shù)被3整除） 如果一個(gè)整數(shù)的各位數(shù)字之和能被3整除，則該數(shù)能被3整除。即：若3∣an+an-1+…a1+a0，，則3 ∣N.判別方法4：（整數(shù)被9整除）如果一個(gè)整數(shù)的各位數(shù)字之和能被9整除，則該數(shù)能被9整除。即：若9∣an+an-1+…a1+a0，，則9 ∣

33、N.,例6 有一個(gè)自然數(shù)乘以9后，得到一個(gè)僅由數(shù)字1組成的多位數(shù)，求這個(gè)自然數(shù)最小為多少？,12345679,判別方法5：（整數(shù)被4或25整除） 如果一個(gè)數(shù)的末兩位數(shù)能被4或25整除，那么，這個(gè)數(shù)就一定能被4或25整除．判別方法6：（整數(shù)被8或125整除） 如果一個(gè)數(shù)的末三位數(shù)能被8或125整除，那么，這個(gè)數(shù)就一定能被8或125整除．,可除性判別方法,可除性判別方法,判別方法7：（整數(shù)被11整除）

34、(1) 如果一個(gè)整數(shù)將其最后三位數(shù)字去掉后得到的位數(shù)少3位的新整數(shù)與該整數(shù)末三位數(shù)字組成的數(shù)之差能被11整除，則該整數(shù)能11整除.即如果 ，則11︱N.(2)把一個(gè)數(shù)由右邊向左邊數(shù),將奇位上的數(shù)字與偶位上的數(shù)字分別加起來(lái),再求它們的差,如果這個(gè)差是11的倍數(shù)(包括0),那么,原來(lái)這個(gè)數(shù)就一定能被11整除。例如：判斷491678能不能被11整除。

35、 →奇位數(shù)字的和9+6+8=23 ，→偶位數(shù)位的和4+1+7=12  ，23-12=11因此,491678能被11整除。這種方法叫“奇偶位差法”。,可除性判別方法,判別方法8：（整數(shù)被13整除） 如果一個(gè)整數(shù)將其最后三位數(shù)字去掉后得到的位數(shù)少3位的新整數(shù)與該整數(shù)末三位數(shù)字組成的數(shù)之差能被13整除，則該整數(shù)能13整除.即如果

36、 ， 則13︱N.判別方法9：（整數(shù)被7整除）（適用于數(shù)字位數(shù)少時(shí)）一個(gè)數(shù)割去末位數(shù)字，再?gòu)牧粝聛?lái)的數(shù)中減去所割去數(shù)字的2倍，這樣，一次次減下去，如果最后的結(jié)果是7的倍數(shù)（包括0），那么，原來(lái)的這個(gè)數(shù)就一定能被7整除．例如：判斷133是否7的倍數(shù)的過(guò)程如下：13－3×2＝7，所以133是7的倍數(shù),例7 設(shè)a，b，c是三個(gè)互不相等的正整數(shù)，求證：三數(shù)中至少有一個(gè)能被10整除。,例8 設(shè)n 為自然數(shù)，

37、求證：能被1985整除。,例9 設(shè)p為大于5的素?cái)?shù) ，求證：240︱,例10 p ? 5是素?cái)?shù) ，且2 p +1也是素?cái)?shù)，證明： 4 p +1必是合數(shù)。,例11 請(qǐng)確定最小正整數(shù)A，其末位數(shù)為6，若將末位的6移至首位，其余數(shù)字不變，則為原數(shù)的4倍。,,例12 一個(gè)正整數(shù)，如果用7進(jìn)位制表示，則為 ，如果用5進(jìn)位制表示為 ，請(qǐng)用10進(jìn)位制表示此數(shù)。,,例13 證明：對(duì)任何自然數(shù)n 和k

38、 ，數(shù)都不能分解成若干個(gè)連續(xù)的自然數(shù)之積。,例14 設(shè)r是正奇數(shù)，證明：對(duì)任意的正整數(shù)n，有,例15 設(shè)A = { }是n的所有約數(shù)的集合，則B = { } 也是n的所有約數(shù)的集合。,例16 以d(n)表示n的正約數(shù)的個(gè)數(shù)， 例如： d(1) = 1，d(2) = 2，d

39、(3) = 2， d(4) = 3，? 。 問(wèn)：d(1) ? d(2) ? ? ? d(1997)是否為偶數(shù)？,例17 設(shè)凸2n邊形M的頂點(diǎn)是 ，點(diǎn)O在M的內(nèi)部，用1, 2, ?, 2n將M的2n條邊分別編號(hào)，又將 也同樣進(jìn)行編號(hào)，若把這些編號(hào)作為相應(yīng)的線(xiàn)段的長(zhǎng)度，證明

40、：無(wú)論怎么編號(hào)，都不能使得三角形 的周長(zhǎng)都相等。,第二節(jié) 帶余除法,第二節(jié) 帶余除法,可以看出：b整除a的充要條件是 r=0。,設(shè)a，b是兩個(gè)整數(shù)，其中b>0.則存在唯一的整數(shù)q，r使得a=bq+r，0≤r<b. 證明（存在性）考慮一個(gè)整數(shù)序列 …，

41、-3b，-2b，-b，0，b，2b，3b，…它們將實(shí)數(shù)軸分成長(zhǎng)度為b的區(qū)間，而a必定落在其中的一個(gè)區(qū)間中，因此存在一個(gè)整數(shù)q使得 qb≤a<(q+1)b我們令r=a-bq，則有a=bq+r，0≤r<b,(唯一性) 如果分別有整數(shù)q，r和q1，r1滿(mǎn)足（2），則 a= bq+r， 0≤r<b， a= bq1+r1，0≤r1<b兩式相減，我

42、們有 b(q-q1) =-(r-r1)當(dāng)q≠q1左邊的絕對(duì)值大于等于b，而右邊的絕對(duì)值小于b，這是不可能的.故q=q1，r=r1.,例1 利用帶余數(shù)除法，由a, b的值求q, r .,,,,如果允許b取負(fù)值，則要求,則a必在此序列的某兩項(xiàng)之間，,,存在性得證 ；下證唯一性.,當(dāng)b為奇數(shù)時(shí)，②式中的等號(hào)不能成立，,當(dāng)b為偶數(shù)時(shí),s, t可以不唯一，舉例如下：,注：該例為簡(jiǎn)化輾轉(zhuǎn)相除法求最大公約數(shù)提供了依據(jù)。,帶

43、余數(shù)除法的應(yīng)用舉例,例2 證明：形如3n-1的數(shù)不是平方數(shù)。,例3、任意給出的5個(gè)整數(shù)中，必有3個(gè)數(shù)之和被3整除。,證明：,由帶余除法有,例6 設(shè)a，b，x，y是整數(shù)，k和m是正整數(shù)，并且則ax ? by 和 ab 被 m 除的余數(shù)分別與 和 被m除的余數(shù)相同。特別地， 與 被m除的余數(shù)相同。,例7 設(shè)

44、 為不全為零的整數(shù)，以 表示集合A = { y | y = ， ，1 ? i ? n } 中的最小正數(shù)，則 對(duì)于任何 y?A， ；特別地， 1 ? i ? n。,例8 設(shè)

45、 ?Z，f(x) = ，已知f(0) 與f(1)都不是3的倍數(shù)，證明：若方程f(x) = 0有整數(shù)解，則3?f(?1) = 。,例9 證明：若a被9除的余數(shù)是3，4，5或6，則方程

46、 沒(méi)有整數(shù)解。,第三節(jié) 最大公約數(shù),如果 ，1 ? i, j ? n ，i ? j，則稱(chēng) 是兩兩互素的（或兩兩互質(zhì)的）。,例1 已知兩個(gè)自然數(shù)的和為165，它們的最大公約數(shù) 為15，求這兩個(gè)數(shù)。,15與150，或30與135，或45與120，或60與105，或

47、75與90.,【定理2】設(shè)b是任一正整數(shù)，則（i)0與b的公因數(shù)就是,b的因數(shù)，反之， b的因數(shù)也就是0與b的公因數(shù)。,(ii)(0,b)=b,(a, 1) = 1， (a, a) = |a|； (a, b) = (b, a)；,【定理3】設(shè) a = qb+r, 其中a,b,q,r都是整數(shù), 則 (a，b) = (b，r)．,證：只需證 a與b 和 b與r 有相同的公因子．設(shè)d是a與b的公因子, 即d|a且d

48、|b．注意到 r=a-qb, 由 性質(zhì)有 d|r. 從而, d|b且 d|r, 即 d也是 b與r 的公因子．反之一樣, 設(shè) d 是 b與 r的公因子, 即 dlb且 dlr．注意到, a=qb+r, 故有 d|a . 從而, d|a且 d|b，即 d也是a與b的公因子．,【定理4】 設(shè) ，記A = { y | y =

49、 ，? ? i ? k }。如果 是集合A中最小的正數(shù)，則 。,推論1 設(shè)d是 的一個(gè)公約數(shù)，則 。,推論2 ( ) = |m|(

50、 )。,推論3 記? = ( )，則= 1，特別地, = 1,【定理5】( ) = 1的充要條件是存在整數(shù) ，使得

51、 = 1。,【定理6】若 (a, b) = 1，則(a, bc) = (a, c)。,推論 若 (a, ) = 1，1 ? i ? n，則(a, ) = 1。,【定理7】,例1 證明：若n是正整數(shù)，則 是既約分?jǐn)?shù)。,例2 設(shè)a，b是整數(shù)，且9? ，則3?(a, b

52、)。,例3,設(shè)a和b是正整數(shù)，b > 2，則 。,第四節(jié) 輾轉(zhuǎn)相除法,定義 下面的一組帶余數(shù)除法，稱(chēng)為輾轉(zhuǎn)相除法。,例1 求下面各組數(shù)的最大公因數(shù)。,解：,1859 1573,,,1,1573,,286,5,1430,143,2,286,,0,注：亦可通過(guò)分解因數(shù)的方法求最大公因數(shù).,補(bǔ)充說(shuō)明：利用§1.1習(xí)題4的結(jié)論，可以使得輾轉(zhuǎn)相除法求最大公因數(shù)更

53、為快速一些。每次除得余數(shù)的絕對(duì)值不超過(guò)除數(shù)的一半，余數(shù)可以為負(fù)。,例2 求（76501，9719）.,76501 9719,,,8,,77752,1251,8,10008,289,4,1156,,95,3,285,4,24,96,,1,4,4,0,=1.,例3 利用輾轉(zhuǎn)相除法計(jì)算 (27090, 21672, 11352).,27090 21672 11352,,,2,22704,（2）,22704,,4386,1032,

54、11,11352,4,4128,0,,258,4,1032,0,所以，(27090, 21672, 11352)=258.,定理2 設(shè)a，b不全為0，則存在整數(shù) s, t，使得,證明：利用P4習(xí)題1-3的結(jié)論.,一方面，,另一方面，,特別地，,證：必要性的證明由定理2直接可得。,例 用輾轉(zhuǎn)相除法求(125, 17)，以及x，y，使得 125x ? 17y = (125, 17)。,解 做輾轉(zhuǎn)相除法：,,,本節(jié)最后

55、介紹另外一種求兩個(gè)整數(shù)最大公因數(shù)的方法，先給出下面幾個(gè)結(jié)果：,即當(dāng)a與b是正整數(shù)時(shí)，只要使用被2除的除法運(yùn)算和減法運(yùn)算就可以計(jì)算出(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é) 最小公倍數(shù),定

56、義1 ： 整數(shù)a1, a2, ?, ak的公共倍數(shù)稱(chēng)為a1, a2, ?, ak的公倍數(shù)。a1, a2, ?, ak的正公倍數(shù)中的最小的一個(gè)叫做a1, a2, ?, ak的最小公倍數(shù)，記為[a1, a2, ?, ak].,定理1： 下面的等式成立：(ⅰ) [a, 1] = |a|，[a, a] = |a|；(ⅱ) [a, b] = [b, a]；(ⅲ) [a1, a2, ?, ak] = [|a1|, |a2| ?,

57、|ak|]；(ⅳ) 若a?b，則[a, b] = |b|。,定理2 對(duì)任意的正整數(shù)a，b，有,推論1 兩個(gè)整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除。,推論2 設(shè)m，a，b是正整數(shù)，則[ma, mb] = m[a, b]。,定理3,注：把多個(gè)整數(shù)的公倍數(shù)化為兩個(gè)數(shù)的公倍數(shù)來(lái)計(jì)算。,推論 若m是a1, a2, ?, an的公倍數(shù)，則[a1, a2, ?, an]?m 。,定理4 整數(shù)a1, a2, ?,

58、an兩兩互素，即(ai, aj) = 1，1 ? i, j ? n，i ? j 的充要條件是,[a1, a2, ?, an] = a1a2?an .,例3 設(shè)a，b，c是正整數(shù)，證明 [a, b, c](ab, bc, ca) = abc 。,證：[a, b, c] = [[a, b], c] =,(ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b)),代入即得證.,例4 對(duì)于任意的整數(shù) 及

59、整數(shù)k，1 ? k ? n，證明：[ ] = [[ ],[ ]],例5 設(shè)a，b，c是正整數(shù)，證明：[a, b, c][ab, bc, ca] = [a, b][b, c][c, a]。,第六節(jié) 算術(shù)基本定理,證明 當(dāng)n = 2時(shí)，結(jié)論顯

60、然成立。,由于2 ? d ? k，由歸納假定知存在素?cái)?shù)q1, q2, ?, ql，使得d = q1q2?ql，從而k ? 1 = pq1q2?ql。,假設(shè)對(duì)于2 ? n ? k，式(1)成立，下證式(1)對(duì)于n = k ? 1也成立，,從而由歸納法推出式(1)對(duì)任何大于1的整數(shù)n成立。,如果k ? 1是素?cái)?shù)，式(1)顯然成立。,若k ? 1是合數(shù)，則存在素?cái)?shù)p與整數(shù)d，使得k ? 1 = pd。,引理1 任何大于1的正整數(shù)n可以寫(xiě)

61、成素?cái)?shù)之積，即n = p1p2?pm， (1)其中pi（1 ? i ? m）是素?cái)?shù)。,定理1(算術(shù)基本定理) 任何大于1的整數(shù)n可以唯一地表示成 ， (2)其中p1, p2, ?, pk是素?cái)?shù)，p1 < p2 < ? < pk，?1, ?2, ?, ?k是正

62、整數(shù)。,證明 由引理1，任何大于1的整數(shù)n可以表示成式(2)的形式，因此，只需證明表示式(2)的唯一性。,假設(shè)pi（1 ? i ? k）與qj（1 ? j ? l）都是素?cái)?shù)，p1 ? p2 ? ? ? pk，q1 ? q2 ? ? ? ql， (3)并且 n = p1p2?pk = q1q2?ql ， (4)則由第三節(jié)定理4推論1，必有某個(gè)qj（1 ?

63、j ? l），使得p1?qj，所以p1 = qj；又有某個(gè)pi（1 ? i ? k），使得q1?pi，所以q1 = pi。,于是，由式(3)可知p1 = q1，從而由式(4)得到p2?pk = q2?ql 。重復(fù)上述這一過(guò)程，得到k = l，pi = qi ，1 ? i ? k 。,定義1 使用定理1中的記號(hào)，稱(chēng) 是n的標(biāo)準(zhǔn)分解式, 其中pi（1 ? i ? k）是素?cái)?shù), p1 < p2 < ? < pk

64、，? i（1 ? i ? k）是正整數(shù).,推論1 使用式(2)中的記號(hào)，有(ⅰ) n的正因數(shù)d必有形 ， ?i?Z，0 ? ?i ? ? i，1 ? i ? k；(ⅱ) n的正倍數(shù)m必有形式 M?N，?i?N，?i ? ? i，1 ? i ? k。,推論2 設(shè)正整數(shù)a與b的標(biāo)準(zhǔn)分解式是

65、其中pi(1 ? i ? k)，qi(1 ? i ? l)與ri(1 ? i ? s)是兩兩不相同的素?cái)?shù)，?i，?i(1 ? i ? k)，?i(1 ? i ? l)與?i(1 ? i ? s)都是非負(fù)整數(shù)，則,(a, b) = ， ?i = min{?i, ?i}，1 ? i ? k，[a, b] =

66、 ， ?i = max{?i, ?i}，1 ? i ? k。,推論2 ? 設(shè)正整數(shù)a與b的標(biāo)準(zhǔn)分解式是其中p1, p2, ?, pk 是互不相同的素?cái)?shù)，?i，?i（1 ? i ? k）都是非負(fù)整數(shù)，則,例1 寫(xiě)出51480的標(biāo)準(zhǔn)分解式。,解 我們有51480 = 2?25740 = 22 ? 12870 = 23 ? 6435= 23 ? 5 ? 128

67、7 = 23 ? 5 ? 3 ? 429= 23 ? 5 ? 32 ? 143 = 23 ? 32 ? 5 ? 11 ? 13.,例2 設(shè)a，b，c是整數(shù)，證明： (ⅰ) (a, b)[a, b] = ab；,證明 為了敘述方便，不妨假定a，b，c是正整數(shù)。(ⅰ) 設(shè),其中p1, p2, ?, pk是互不相同的素?cái)?shù), ?i，?i(1 ? i ? k)都是非負(fù)整數(shù)。由定理1推論2 ?，有由此知,例2 設(shè)a，

68、b，c是整數(shù)，證明： (ⅱ) (a, [b, c]) = [(a, b), (a, c)]。,(ⅱ) 設(shè)其中p1, p2, ?, pk是互不相同的素?cái)?shù), ?i，?i，?i(1 ? i ? k)都是非負(fù)整數(shù). 由定理1推論2 ?, 有 其中，對(duì)于1 ? i ? k，有 ?i = min{?i, max{?i, ?i}}，,?i = max{min{?i, ?i}, min{?i, ?i}}，不妨設(shè)?i ? ?i，