初等數(shù)論閔嗣鶴版課件

1、第一章 整數(shù)的可除性一 初等數(shù)論及其主要內(nèi)容 數(shù)論是研究整數(shù)性質(zhì)的一門很古老的數(shù)學(xué)分支，其初等部分是以整數(shù)的整除性為中心的，包括整除性、不定方程、同余式、連分?jǐn)?shù)、素?cái)?shù)（即質(zhì)數(shù)）分布 以及數(shù)論函數(shù)等內(nèi)容，統(tǒng)稱初等數(shù)論 （elementary number theory） 。 初等數(shù)論是數(shù)論中不求助于其他數(shù)學(xué)學(xué)科的幫助，只依靠初等的方法來(lái)研究整數(shù)性質(zhì)的分支。 自古以來(lái)，數(shù)學(xué)家對(duì)于整數(shù)性質(zhì)的研究一直十分重視，初等數(shù)論的大部份內(nèi)容早在古希臘歐幾里德的幾何原本（公元前3世紀(jì)）中就已出現(xiàn)。歐幾里得證明了素?cái)?shù)有無(wú)窮多個(gè)，他還給出求兩個(gè)自然數(shù)的最大公約數(shù)的方法，即所謂歐幾里得算法。我國(guó)古代在數(shù)論方面亦有杰出之

2、貢獻(xiàn)，現(xiàn)在一般數(shù)論書中的“中國(guó)剩余定理”，正是我國(guó)古代孫子算經(jīng)中的下卷第26題，我國(guó)稱之為孫子定理。 近代初等數(shù)論的發(fā)展得益於費(fèi)馬、歐拉、拉格朗日、勒讓德和高斯等人的工作。1801年，德國(guó)數(shù)學(xué)家高斯集中前人的大成，寫了一本書叫做算術(shù)探究，開(kāi)始了現(xiàn)代數(shù)論的新紀(jì)元。高斯還提出：“數(shù)學(xué)是科學(xué)之王，數(shù)論是數(shù)學(xué)之王”。二 數(shù)論的發(fā)展 由于自20世紀(jì)以來(lái)引進(jìn)了抽象數(shù)學(xué)和高等分析的巧妙工具，數(shù)論得到進(jìn)一步的發(fā)展，從而開(kāi)闊了新的研究領(lǐng)域，出現(xiàn)了代數(shù)數(shù)論、解析數(shù)論、幾何數(shù)論等新分支。而且近年來(lái)初等數(shù)論在計(jì)算機(jī)科學(xué)、組合數(shù)學(xué)、密碼學(xué)、代數(shù)編碼、計(jì)算方法等領(lǐng)域內(nèi)更得到了 廣泛的應(yīng)用，無(wú)疑同時(shí)也促進(jìn)著數(shù)論的發(fā)展。 我

3、國(guó)近代：在解析數(shù)論、丟番圖方程，一致分布等方面有過(guò)重要貢獻(xiàn)，出現(xiàn)了華羅庚、閔嗣鶴等一流的數(shù)論專家，其中華羅庚在三角和估值、堆砌素?cái)?shù)論方面的研究享有盛名。 特別是在“篩法”、歌德巴赫猜想方面的研究，已取得世界領(lǐng)先的優(yōu)異成績(jī)。陳景潤(rùn)在1966年證明歌德巴赫猜想方面證明了”1+2”(一個(gè)大偶數(shù)可以表示為一個(gè)素?cái)?shù)和一個(gè)不超過(guò)兩個(gè)素?cái)?shù)的乘積之和)三、幾個(gè)著名數(shù)論難題 初等數(shù)論是研究整數(shù)性質(zhì)的一門學(xué)科，歷史上遺留下來(lái)沒(méi)有解決的大多數(shù)數(shù)論難題其問(wèn)題本身容易搞懂，容易引起人的興趣，但是解決它們卻非常困難。 其中，非常著名的問(wèn)題有：哥德巴赫猜想 ；費(fèi)爾馬大定理 ；孿生素?cái)?shù)問(wèn)題 ；完全數(shù)問(wèn)題等。 1742年,由德

4、國(guó)中學(xué)教師哥德巴赫在教學(xué)中首先發(fā)現(xiàn)的。1742年6月7日，哥德巴赫寫信給當(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)樗谋拘惺菍I(yè)的律師，世人冠以“業(yè)余王子”之美稱。在三百七十多年前的某一天，費(fèi)馬正在閱讀一本古希臘數(shù)學(xué)家戴奧芬多斯的數(shù)學(xué)書時(shí)，突然心血來(lái)潮在書頁(yè)的空白處

5、，寫下一個(gè)看起來(lái)很簡(jiǎn)單的定理。 經(jīng)過(guò)8年的努力，英國(guó)數(shù)學(xué)家 安德魯懷爾斯 終于在1995年完成了該定理的證明。)3( nzyxnnn方程 無(wú)非0整數(shù)解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 Polignac 提出猜想： 對(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 (即間

6、隔為4) 的素?cái)?shù)對(duì)被稱為 cousin prime ；而 k=3 (即間隔為 6) 的素?cái)?shù)對(duì)竟然被稱為 sexy prime (不過(guò)別想歪了，之所以稱為 sexy prime 其實(shí)是因?yàn)?sex 正好是拉丁文中的 6。) 4、最完美的數(shù)完全數(shù)問(wèn)題 下一個(gè)具有同樣性質(zhì)的數(shù)是28, 28=1+2+4+7+14.接著是496和8128.他們稱這類數(shù)為完美數(shù). 歐幾里德在大約公元前350-300年間證明了: 注意以上談到的完全數(shù)都是偶完全數(shù),至今仍然不知道有沒(méi)有奇完全數(shù)。 完美數(shù)又稱為完全數(shù),最初是由畢達(dá)哥拉斯的信徒發(fā)現(xiàn)的,他們注意到,數(shù)6有一個(gè)特性,它等于它自己的因子(不包括它自身)的和， 如：6=

7、1+2+3.若 是素?cái)?shù)，則 是完全數(shù) 12 n) 12(21nn 在培養(yǎng)中學(xué)生思維能力方面大有作用。四、初等數(shù)論在中小學(xué)教育中的作用國(guó)際數(shù)學(xué)奧林匹克從1959年起到2002年已經(jīng)舉行了43屆比賽，大致統(tǒng)計(jì)，在總共260道題目中，可以主要用初等數(shù)論知識(shí)來(lái)解及初等數(shù)論知識(shí)有關(guān)的約有82題，約占31.5%。第一節(jié) 整除的概念 帶余數(shù)除法qabqabb a如果不存在整數(shù) 使得成立，則稱 不被 整除，記為。2、整除的基本定理、整除的基本定理思考：逆命題是否成立？1、m|(ab) m|a,m|b2、m|(ab) ，m|am|bbmbamam|)( |,|定理2特例：m|a m|aq3 3、帶余數(shù)除法、帶余

8、數(shù)除法4,00a bbqrabqrrbqr帶余數(shù)除法的第二種表示定理若是兩個(gè)整數(shù)，其中，則存在著兩個(gè)整數(shù)及 ，使得，成立，而且 及 是唯一的。,00,qZaq brab qrbbqq r證明分析：作整數(shù)序列，-3 b ,-2 b ,- b ,0,b ,2 b ,3 b ,則a必滿足q ba(q+1)b ,其中令可得到分和來(lái)討論進(jìn)一步證明的唯一性。4,02a bbbqrabqrrqrqr帶余數(shù)除法的第三種表示（課后習(xí)題）定理若是兩個(gè)整數(shù)，其中，則存在著兩個(gè)整數(shù)及 ，使得，成立，而且當(dāng)b是奇數(shù)時(shí)， 及 是唯一的；當(dāng)b是偶數(shù)時(shí)， 及有可能是不唯一的。5,252313,1;52212,1abqrqr

9、例當(dāng)時(shí)，可有（） （） （），即或（） （） ，即222222,220000,qZbbbbqrq r證明分析：作序列3 b2 bbb 2 b 3 b，-,-,-,0,bb則a必滿足qa(q+1),其中分q為偶數(shù)時(shí)和；q為偶數(shù)時(shí)和來(lái)討論 及 的存在性 進(jìn)一步證明的唯一性。例例1 求當(dāng)b=15時(shí), a取下列數(shù)值時(shí)的不完全商和余數(shù).1、a=81; 2、a=-81; 例例2(1)一個(gè)數(shù)除以2,余數(shù)可能為 ,所有的整數(shù)按被2除所得的余數(shù)分類可分為 . (2)一個(gè)數(shù)除以3,余數(shù)可能為 ,所有的整數(shù)按被3除所得的余數(shù)分類可分為 . ( 3 ) 一 個(gè) 數(shù) 除 以 正 整 數(shù) b , 余 數(shù) 可 能為 ,所有

10、的整數(shù)按被b除所得的余數(shù)分類可分為 . 帶余數(shù)除法的應(yīng)用舉例帶余數(shù)除法的應(yīng)用舉例例例1 1 證明形如證明形如3n-13n-1的數(shù)不是平方數(shù)。的數(shù)不是平方數(shù)。2,3,03(3)31,03.aZaqrrqrnr 證明：，而例例 2 2 、 任 意 給 出 的、 任 意 給 出 的 5 5 個(gè) 整 數(shù) 中 ， 必 有個(gè) 整 數(shù) 中 ， 必 有 3 3 個(gè) 數(shù) 之個(gè) 數(shù) 之和被和被3 3整除。整除。5,1,5303,1,5iiiiia iaqrri證：設(shè)這 個(gè)數(shù)為，記，。分別考慮以下兩種情形,0120,1,23()33irrrrraaaqqq( 若在中數(shù) ， ，都出現(xiàn)，不妨設(shè)

11、， 此時(shí)可以被 整除 ),0120,123()33iiirrrrrrr raaaqqqr若在中數(shù) ， ，至少有一個(gè)不出現(xiàn)，這樣至少有3個(gè) 要取相同的值，不妨設(shè)(或 ）， 此時(shí)可以被 整除。311,21dadaa例 、設(shè)為奇數(shù)，證明：存在正整數(shù)使得0112 ,2 ,22 (0)ajaaja證：考慮下面的 個(gè)數(shù)：，顯然 不整除，2 (0)2,(0)jjjjjjaq arra由帶余除法，對(duì)每個(gè)，011, ,1aar rra因而 個(gè)余數(shù)僅可能取個(gè)值，因此其中必有兩個(gè)相等。0()222 (21)ikkiik ikirrikaa qq 設(shè)為 ， ，不妨設(shè)，因而有211k iadk

12、iad 則有，取，則 就滿足要求。0()222 (21)ikkiik ikirrikaa qq 設(shè)為 ， ，不妨設(shè)，因而有011, ,1aar rra因而 個(gè)余數(shù)僅可能取個(gè)值，因此其中必有兩個(gè)相等。例4例6第二節(jié)第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法最大公因數(shù)與輾轉(zhuǎn)相除法1212121212,(2),=1,nnnnna aan nda aaa aaa aaa aa1、定義設(shè)是個(gè)整數(shù)，若整數(shù) 是它們之中每一個(gè)的因數(shù)，那么d就叫作的一個(gè)公因數(shù)。所有公因數(shù)中最大的一個(gè)叫最大公因數(shù)，記作（），若（） ，則說(shuō)互質(zhì)或互素。2 2、任意整數(shù)的最大公因數(shù)可轉(zhuǎn)化為正整數(shù)來(lái)討論、任意整數(shù)的最大公因數(shù)可轉(zhuǎn)化為正整數(shù)來(lái)討論3

13、 3、下面先討論兩個(gè)非負(fù)整數(shù)的最大公因數(shù)、下面先討論兩個(gè)非負(fù)整數(shù)的最大公因數(shù)定理定理2 2、設(shè)、設(shè)b b是任一正整數(shù)，則（是任一正整數(shù)，則（i)0i)0與與b b的公因數(shù)就是的公因數(shù)就是b b的因數(shù)，反之，的因數(shù)，反之， b b的因數(shù)也就是的因數(shù)也就是0 0與與b b的公因數(shù)。的公因數(shù)。(ii)(0,b)=b(ii)(0,b)=b2.1(0, )bbb推論若 是任一非零整數(shù)，則4 4、定理、定理3 3 設(shè)設(shè)a,b,ca,b,c是三個(gè)不全為零的整數(shù)，且是三個(gè)不全為零的整數(shù)，且a=bq+ca=bq+c其中q是非零整數(shù)，則a,b與b,c有相同的公因數(shù)，因而(a,b)=(b,c)思考：1、d|a,d|

14、c時(shí)能否推出d|b? 5、下面要介紹一個(gè)計(jì)算最大公約數(shù)的算法下面要介紹一個(gè)計(jì)算最大公約數(shù)的算法輾轉(zhuǎn)輾轉(zhuǎn)相除法，又稱相除法，又稱EuclidEuclid算法。它是數(shù)論中的一個(gè)重要算法。它是數(shù)論中的一個(gè)重要方法，在其他數(shù)學(xué)分支中也有廣泛的應(yīng)用。方法，在其他數(shù)學(xué)分支中也有廣泛的應(yīng)用。定義定義 下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法。下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法。12221 0 brqrrr，111 0 babqrr，1 1 1 1 0 kkkkkkrr qrrr，,0a bb 設(shè)是整數(shù)，依次做帶余數(shù)除法211 0 nnnnnnrrqrrr，1 111+0nnnnnrr qrr,。4,( , )

15、nna ba brr定理若是任意兩個(gè)正整數(shù)，則，是上式中最后一個(gè)不等于零的余數(shù)。4.1,( , )a ba b推論的公因數(shù)與的因數(shù)相同。1859,1573,( 1859,1573)ab例1、求6 6、最大公因數(shù)的兩個(gè)性質(zhì)、最大公因數(shù)的兩個(gè)性質(zhì)5, ,( )(,)( , ),( ),1( , ) ( , )a bi mam bma b ma babiia baba ba b定理設(shè)是任意兩個(gè)不全為零的整數(shù)，是任一正整數(shù)，則 若 是的任一公因數(shù)，則，特別 對(duì)于兩個(gè)以上整數(shù)的最大公因數(shù)問(wèn)題，不妨設(shè)121222331,(,),(,),(,).nnnna aana addaddad是任意 個(gè)正整數(shù)，令于是

16、我們有2142143nnn例 、證明：若 是正整數(shù)，則是既約分?jǐn)?shù)。214,143)(71,143)nnnn證明：因?yàn)椋?71,72)(71,1)1nnn所以，命題得證。第三節(jié) 整除的進(jìn)一步性質(zhì)及最小公倍數(shù)0000( , ),ka baxbyxya bra b第二節(jié)習(xí)題第二題要求證明成立，其中的 和 與的關(guān)系如何？進(jìn)一步，輾轉(zhuǎn)相除法中任意 與的關(guān)系又如何？2.1,( , )a bstasbta b推論若是任意兩個(gè)不全為零的整數(shù)，則存在兩個(gè)整數(shù) ， 使得22172 65,2,5qr 3361 5 1,1,1qr 3(125,17)1r由定理得例例 用輾轉(zhuǎn)相除法求(125, 17)，以及x，y，使得

17、 125x 17y = (125, 17)。解 做輾轉(zhuǎn)相除法：111257 176,7,6qr01231,7,2 7 1 15,1 15722,PPPP 01230,1,2 102,1 2 13,QQQQ 3 1333( 1)3,( 1)22,xQyP 取125 3+1722 （-）=(125,17)=1則2, ,( , )1,)(, )( , ),a b ca cab cb ciiab cb cb c定理 、若是三個(gè)整數(shù)，且，則（i)與有相同的公因數(shù)，（上面假定了至少有一不為零。2.1( , )1,.a cc abc b推論、若，則1212121 22.2,)1nmnma aab bba a

18、a bbb推論、設(shè)及 ,是任意兩組整數(shù)，若前一組中任一整數(shù)與后一組中任一整數(shù)互質(zhì)，則(121212,(2), ,nnna aan ndna aaa aa定義設(shè)是個(gè)整數(shù)，若整數(shù) 是這 個(gè)數(shù)的倍數(shù)，則d就叫作的一個(gè)公倍數(shù)。所有公倍數(shù)中最小的一個(gè)叫最小公倍數(shù)，記作。12123,.nna aaaaa定理, ( ) ,.,( , )a ba ba bii a baba ba ba baba b定理4設(shè)是任意兩個(gè)正整數(shù)，則(i)的所有公倍數(shù)就是的所有倍數(shù)；的最小公倍數(shù)等于以它們的最大公因數(shù)除它們的乘積所得的商，即=特別地，當(dāng)（）=1，則= 對(duì)于兩個(gè)以上整數(shù)的最小公倍數(shù)問(wèn)題，不妨設(shè)121222331,.nn

19、nna aana ammammam是任意 個(gè)正整數(shù)，令于是我們有1212,.nnna aana aam定理5是 個(gè)正整數(shù)，則 注：多項(xiàng)式的帶余除法類似于整數(shù)的帶余除法第四節(jié) 質(zhì)（素）數(shù) 算術(shù)基本定理一、質(zhì)（素）數(shù)一、質(zhì)（素）數(shù)1、定義 一個(gè)大于1的整數(shù)，如果它的正因數(shù)只有1及它本身，就叫做質(zhì)數(shù)（或素?cái)?shù)）；否則就叫合數(shù)。2、與素?cái)?shù)相關(guān)的性質(zhì)定理111aaqaqa定理設(shè) 是任一大于 的整數(shù)，則 的除 外最小正因數(shù) 是一素?cái)?shù)，并且當(dāng) 是合數(shù)時(shí)，2=1paappaapp定理設(shè) 是一素?cái)?shù)， 是任一整數(shù)，則 能被 整除或 與 互質(zhì)，即（ ， ） 或 。1212.,.nnka aanpp a aapa推論2

20、1設(shè)是 個(gè)整數(shù)， 是素?cái)?shù).若，則 一定能整除某一1.aaaa定理若是整數(shù)，則 是素?cái)?shù)不大于的素?cái)?shù)都不能整除.aa充分性：設(shè)不大于的素?cái)?shù)都不能整除1app若 是合數(shù)，設(shè) 是除 外的最小正因數(shù)，則 是素?cái)?shù)。211apaapappa令,則，即，這樣就找到一個(gè)證：必要性顯然。apaa不大于的素?cái)?shù) ，它可以整除 ，矛盾， 是素?cái)?shù)。 對(duì)于一個(gè)給定的整數(shù)，我們根據(jù)上述定理不僅可以判別它是否是素?cái)?shù)，且還可以找出所有不大于它的素?cái)?shù),1,2,3,4,5,6,7,aZa aa的素?cái)?shù)倍數(shù)劃去后，剩下的數(shù)就是所有不大于把1劃去，剩下第一個(gè)數(shù)是2,2是素?cái)?shù)。從2起劃去它后面所有2的倍數(shù)，剩下的第一個(gè)數(shù)是3，它不是2的倍所

21、以它是素?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ù)就需要一百億年,令人吃驚的是,要檢驗(yàn)一個(gè)一百位數(shù),需要的時(shí)間就猛增到1036年.到了1980年,這種困難的情況得到了改觀,阿德曼(Adleman),魯梅利(Rumely),科恩(Cohen),和倫斯特拉(Lenstra)研究出一種非常復(fù)雜的過(guò)去,要檢驗(yàn)一個(gè)數(shù)是否是素?cái)?shù)，最簡(jiǎn)單方法是試除法， 檢驗(yàn)一個(gè)20位數(shù)只消10

22、秒鐘,對(duì)于一個(gè)50位數(shù)用15秒鐘, 100位數(shù)用40秒鐘,如果要他檢驗(yàn)一個(gè)1000位數(shù),只要用一個(gè)星期也就夠了.但是大部分的素性檢驗(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ù)中只有有限個(gè)質(zhì)數(shù)，設(shè)為1212,.11.kkp ppp ppNN 令，則1,1,2, .iNp

23、pp ik由定理 ， 有一素因數(shù) ，這里12,1kp p ppp Npp否則，因此，而與 是素?cái)?shù)矛盾。故.pk是上面 個(gè)素?cái)?shù)以外的素?cái)?shù)，因此定理獲證下面介紹與素?cái)?shù)有關(guān)的某些問(wèn)題1、費(fèi)馬數(shù)：費(fèi)馬在1640年設(shè)計(jì)了一個(gè)公式，給出一些素?cái)?shù)。221nnnF 費(fèi)馬堅(jiān)信對(duì)于所有自然數(shù) ，總能產(chǎn)生素?cái)?shù)。52521641 6700417F 然而他大錯(cuò)特錯(cuò)了！只有五個(gè)素?cái)?shù)被發(fā)現(xiàn)是遵從于這個(gè)公式的，它們是3,5,17,257和65537,分別對(duì)應(yīng)于n=0,1,2,3,42、費(fèi)馬數(shù)與尺規(guī)作圖的聯(lián)系：尺規(guī)作圖是指用沒(méi)有刻度的直尺和圓規(guī)作圖。尺規(guī)作圖 瑞士科學(xué)家歐拉于1732年舉出故費(fèi)馬的猜測(cè)不正確。規(guī)作圖使用的直尺和

24、圓規(guī)帶有想像性質(zhì)，跟現(xiàn)實(shí)中的并非完全相同：1、直尺必須沒(méi)有刻度，無(wú)限長(zhǎng)，且只能使用直尺的固定一側(cè)。只可以用它來(lái)將兩個(gè)點(diǎn)連在一起， 不可以在上畫刻度； 2、圓規(guī)可以開(kāi)至無(wú)限寬，但上面亦不能有刻度。它只可以拉開(kāi)成之前構(gòu)造過(guò)的長(zhǎng)度。 只準(zhǔn)許使用有限次，來(lái)解決不同的平面幾何作圖題。尺是起源于古希臘的數(shù)學(xué)課題。只使用圓規(guī)和直尺，并且221n1796年，19歲的高斯證明了：對(duì)于邊數(shù)是素?cái)?shù)的正多邊形，當(dāng)邊數(shù)是形如的費(fèi)馬數(shù)時(shí)，才能用尺規(guī)作圖，并且給出正17邊形的尺規(guī)作圖法。2knn正 邊形能尺規(guī)作圖為與不同費(fèi)馬素?cái)?shù)積的乘積。一般地，任意正n邊形有以下結(jié)論：3、梅森數(shù)梅森數(shù)(Mersenne number)是指

25、形如2p1的正整數(shù)， 其中指數(shù)p是素?cái)?shù)，常記為Mp 。若Mp是素?cái)?shù)，則稱為梅森素?cái)?shù)。早在公元前300多年，古希臘數(shù)學(xué)家歐幾里得就開(kāi)創(chuàng)了研究2P1的先河，他在名著幾何原本 第九章中論述完美數(shù)時(shí)指出：如果2P1是素?cái)?shù)， 則(2p1)2(p1)是完美數(shù)。 梅森在歐幾里得、費(fèi)馬等人的有關(guān)研究的基礎(chǔ)上 ，對(duì)2P1作了大量的計(jì)算、驗(yàn)證工作，并于1644年在他的 物理數(shù)學(xué)隨感一書中斷言：對(duì)于p=2，3，5，7，13，17，19，31，67，127，257時(shí)，2P1是素?cái)?shù) 而對(duì)于其他所有小于257的數(shù)時(shí)，2P1是合數(shù)。 前面的7個(gè)數(shù)屬于被證實(shí)的部分，是他整理前人的工作得到的；而后面的4個(gè)數(shù)屬于被猜測(cè)的部分。

26、值得提出的是：雖然梅森的斷言中包含著若干錯(cuò)誤， 但他的工作極大地激發(fā)了人們研究2P1型素?cái)?shù)的熱情， 在梅森素?cái)?shù)的基礎(chǔ)研究方面，法國(guó)數(shù)學(xué)家魯卡斯和美國(guó) 數(shù)學(xué)家雷默都做出了重要貢獻(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ù)是：30 402 457211121(1)21204723

27、 89.nnn 若是素?cái)?shù)，則 是素?cái)?shù).其逆命題不成立，例如關(guān)于梅森數(shù)有下列的一個(gè)命題：二、算術(shù)基本定理1、定理4 任一大于1的整數(shù)能表成素?cái)?shù)的乘積，即任一大于1的整數(shù)121212121212,(1),1,2,nnnmmmiiap ppppppppaq qqqqqqqqmnqp in其中 ， ，是素?cái)?shù)，并且若，其中 ， ， ，是素?cái)?shù)，則，。此為算術(shù)基本定理。2、正整數(shù)的標(biāo)準(zhǔn)分解式推論4.1 任一大于1的整數(shù)a能夠唯一地寫成1212,0,1,2, ,()kkiijap ppikpp ij其中12121212,0,1,2, ,0,1,2,kkkikiiap ppikaddp ppikdda則 的正因

28、數(shù) 可以表成的形式，而且當(dāng) 可以表成上述形式時(shí)， 是 的正因數(shù)。推論4.2 設(shè)a是任一大于1的整數(shù)，且推論4.3 設(shè)a,b是任意兩個(gè)正整數(shù)，且12121212,0,1,2, ,0,1,2, ,kkkikiap ppikbp ppik12121212( , ), , ,min(,),max(,)1,2, .kkkkiiiiiia bp ppa bp ppik 則其中， , ( , )aba ba b注：利用推論容易證明：定理5 設(shè)a是任一大于1的正整數(shù)1212,0,1,2,kkiap ppikaa是 的標(biāo)準(zhǔn)分解式，則 的正因數(shù)個(gè)數(shù)為121( )(1)(1)(1)(1)kkiiT a 111110

29、011( )1ikkkkikiiapS appp的所有正因數(shù)的和為1( )2( )T aaP aa的所有正因數(shù)的乘積為121212124.2,0,1,2, ,0,1,2,kkkikiiap ppikaddp ppik證明：由推論，的正因數(shù) 可以唯一地表成，1,2,1,2,1iiiiiiikaikad(1)于是可以通過(guò)依次確定 （）作出 的正因數(shù).因?yàn)?（）可以是0，1，2， ，這個(gè)數(shù)中的任意一個(gè)，即確定 的方法有種，所以 的不同正因數(shù) 的個(gè)數(shù)為：121( )(1)(1)(1)(1)kkiiT a 1212,001,2,(2)( )kiikd a dikaS adp pp的所有正因數(shù)的和為121

30、12211000kkkkppp1211111211211111111kikkiikipppppppp12( )12( ),1,2, ( ),T aiiT ad ddaad diT addda(3)若是 的所有正因數(shù)，令，則也是 的所有正因數(shù)，1122( )( )1( )( )2T aT aT aT ad dd dddaa（）（） （）12( )12( )( ),T aT aaP ad ddd dd故 的所有正因數(shù)的乘積為第五節(jié)第五節(jié) 函數(shù)函數(shù)x,x及其在數(shù)論中的一個(gè)應(yīng)用及其在數(shù)論中的一個(gè)應(yīng)用一、取整函數(shù)及性質(zhì)1、取整函數(shù)x的定義:函數(shù)x與x是對(duì)于一切實(shí)數(shù)都有定義的函數(shù)，函數(shù)x的值等于不大于x的

31、最大整數(shù)； 函數(shù)x的值是x-x.把x叫做x的整數(shù)部分，x叫做x的小數(shù)部分。23 3,4,0,1;3532, 0.14159, 20.414,551 0.141590.95840 例如：?jiǎn)栴}：這兩個(gè)函數(shù)的圖像如何？2、取整函數(shù)的簡(jiǎn)單性質(zhì)(1) xxx(2) 1,1 ,0 1xxxxxxx (3) ,nxnxn是整數(shù)(4) , + xyxyxyxy , + , xxxyyyxyxyxy證：0 + 2, + 01xyxy或 + + 1x yxyxyxyxy或 + x yxy( ) + xyx y 由此可得 + ()( )() + xyxyxyxyx yxy從而 1 xxZxxxZ(5) xZxxx

32、證：當(dāng)時(shí)，； 1,- 0, 1xZxxx 當(dāng)時(shí)，0-1( ) 1xxxxxx 1(9),mnn mZnn01mqnrrn證1,mrmrnqnnnnn(6)-1xx 小于 的最大整數(shù)是xx （7）不小于 的最小整數(shù)是 1xx （8）大于 的最小整數(shù)是(10),001a bZ baaaabbbbbbb 帶余數(shù)除法：，則，aaaaaabbbbbbb 證明：，(11),a bZabab 則不大于 而為 的倍數(shù)的正整數(shù)的個(gè)數(shù)是110,0ambmamb 例題11 2 2xRxxx 例 、證明：，有 ,111 2 222xxxxxxxxxx證：2 2 2 2 2 xxxxx；1 2 2xx則原命題等價(jià)于證1

33、110 , 1,02 122212 02xxxxx當(dāng)時(shí)，故111 1,1 1 ,12 222212 12xxxxx當(dāng)時(shí)，故2121 nnnnnn例 、設(shè) 是任一正整數(shù)， 是實(shí)數(shù)，證明：121( ) nfnnnn證明：令111+11nfnnnn則注：此為厄米特恒等式。 11 11nnnn 11( )nnfnn1,( )R ffn即對(duì)11,( )0,ffnn又因?yàn)楫?dāng)0時(shí)2,( )0fn所以當(dāng)0時(shí)，,( )0 xR f 因此，厄米特恒等式成立。121212123( )()( )0( )( )xn xxxyf x xxxixxxyf xMf nn 例 、平面上坐標(biāo)為整數(shù)的點(diǎn)稱為整點(diǎn)或格點(diǎn)，設(shè)是實(shí)數(shù)，是

34、非負(fù)連續(xù)函數(shù)，證明：區(qū)域：，上的整點(diǎn)的個(gè)數(shù)，這里 取整數(shù)值；1212,1( ),1( )1( )( )( )xn xxnyf nnxnxxnyf nyf nyf nMf n 證：區(qū)域上的整點(diǎn)都是在這樣的直線段上：， 是一滿足的整數(shù)，而直線段上的整點(diǎn)數(shù)就是滿足條件的整數(shù) 的個(gè)數(shù)，有個(gè)，則1212( ) ( )0 xn xii xxMf n 12121212121212121221 121= ( )( )( )( )( )0( )11 ( )0 xn xxn xxn xxn xxn xxn xxn xxnxxn xMf nf nf nMf nf nf nxxxxMf n 證：0022)1122qpxyiiipqpqpqxyqp