整數(shù)的因子分解

1、第一章 整數(shù)的因子分解整除的概念 帶余數(shù)除法最大公因數(shù)與輾轉(zhuǎn)相除法整除的進一步性質(zhì)質(zhì)數(shù)（素數(shù)） 算術基本定理取整函數(shù)及其在數(shù)論中的一個應用第一章 整數(shù)的因子分解$1 整除的概念 帶余數(shù)除法2、整除的基本定理定理1（傳遞性）：ab，bc ac 定理2：若a，b都是m的倍數(shù)，則ab都是m的倍數(shù)3、帶余數(shù)除法帶余除法的應用舉例例1 證明形如3n-1的數(shù)不是平方數(shù)。例2、任意給出的5個整數(shù)中，必有3個數(shù)之和被3整除。$2 最大公因數(shù)與輾轉(zhuǎn)相除法2、任意整數(shù)的最大公因數(shù)可轉(zhuǎn)化為正整數(shù)來討論3、下面先討論兩個非負整數(shù)的最大公因數(shù)定理2 設b是任一正整數(shù)，則(i)0與b的公因數(shù)就是b的因數(shù)，反之， b的因數(shù)

2、也 就是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、計算最大公約數(shù)的算法輾轉(zhuǎn)相除法， 又稱Euclid算法。它是數(shù)論中的一個重要 方法，在其他數(shù)學分支中也有廣泛的應用。定義 下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法。說明：（1）利用輾轉(zhuǎn)相除法可以求兩個整數(shù)的最大公因數(shù)解：因為735000=2389483+18156， 238948=1815613+2920 18156=29206+636 2920=6364+376 636=3761+260 376=2601+

3、116 260=1162+28 116=284+4 28=47所以（735000，238948）=4.例1：求（735000，238948）.例2：求（2605，-5125）.解：因為5125=26051+2520， 2605=25201+85 2520=8529+55 85=551+30 55=301+25 30=251+5 25=55所以（2605，-5125）=5.6、最大公因數(shù)的兩個性質(zhì) 對于兩個以上整數(shù)的最大公因數(shù)問題，不妨設例3：求（2605，3245，7250）.解：先求2065和3245的最大公因數(shù)。 因為3245=26051+1180， 2605=11801+885 1180

4、=8851+295 885=2953 所以（2605，3245）=295. 再求295與7250的最大公因數(shù)。 7250=29524+170， 295=1701+125 170=1251+45 125=452+35 45=351+10 35=103+5 10=52所以（2605，3245，7250）= （295，7250）=5. 本節(jié)最后介紹另外一種求兩個整數(shù)最大公因數(shù)的方法，先給出下面幾個結果： 即當a與b是正整數(shù)時，只要使用被2除的除法運算和減法運算就可以計算出(a,b)例1、求（12345,678）解： （12345,678）=（12345，339）=（12006,339）=（6003,

5、339）=（5664,339）=（177,339）=（177,162）=（177，81）=（96,81）=（3,81）=3所以，命題得證。$3 整除的進一步性質(zhì)及最小公倍數(shù)例 用輾轉(zhuǎn)相除法求(125, 17)，以及x，y，使得 125x 17y = (125, 17)。解 做輾轉(zhuǎn)相除法：則 對于兩個以上整數(shù)的最小公倍數(shù)問題，不妨設注：多項式的帶余除法類似于整數(shù)的帶余除法$4 質(zhì)（素）數(shù) 算術基本定理一、質(zhì)（素）數(shù)1、定義 一個大于1的整數(shù)，如果它的正因數(shù)只有1及它本身，就叫做質(zhì)數(shù)（或素數(shù)）；否則就叫合數(shù)。2、與素數(shù)相關的性質(zhì)定理證：必要性顯然。 對于一個給定的整數(shù)，我們根據(jù)上述定理不僅可以判別

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

7、,阿德曼(Adleman),魯梅利(Rumely),科恩(Cohen),和倫斯特拉(Lenstra)研究出一種非常復雜的技巧,現(xiàn)在以他們的名字的首字母命名的ARCL檢驗法。 檢驗一個20位數(shù)只消10秒鐘,對于一個50位數(shù)用15秒鐘, 100位數(shù)用40秒鐘，如果要他檢驗一個1000位數(shù)，只要用一個星期也就夠了。 但是大部分的素性檢驗法都不能分解出因數(shù)來，只能回答一個數(shù)是否是素數(shù).定理3、素數(shù)的個數(shù)是無窮的。注：2000多年前，古希臘數(shù)學家歐幾里得（前330-前275），著有幾何原本，他在此書中率先證明了素數(shù)的無限性，這個證明一直被當作數(shù)學證明的典范，受到歷代數(shù)學家的推崇，因為這一定理及其證明既簡

8、潔、優(yōu)美而不失深刻。其證明思路如下：證明: 假設正整數(shù)中只有有限個質(zhì)數(shù)，設為定理3、素數(shù)的個數(shù)是無窮的。關于素數(shù)的個數(shù)，有著名的素數(shù)定理：下面列舉的數(shù)字也可以說明定理的真實性。素數(shù)定理是古典素數(shù)分布的理論核心，這個定理大約是在1798年高斯與勒讓德作為猜想提出的。之后許多學者都做過深入的研究，但都沒有成功。1896年，法國數(shù)學家哈達馬及比利時數(shù)學家德.瓦利-普斯因同時獨立地證明了它，他們是用黎曼zata函數(shù)獲得解決的。1949年，挪威數(shù)學家賽爾伯格與匈牙利數(shù)學家愛爾特希第一次給出不用很多函數(shù)論知識，也可以說是一個初等的證明。他們的證明是依靠一個不等式，但是這個所謂的初等證明也是非常復雜的。19

9、50年，賽爾伯格還因為這個證明獲得了菲爾茨獎。二、算術基本定理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ù) 然而他大錯特錯了！只有五個素數(shù)被發(fā)現(xiàn)是遵從于這個公式的，它們是3,5,17,257和65537,分別對應于n=0,1,2,3,4。 瑞士科學家歐拉于1732年舉出現(xiàn)已證明： n=520，22，23，36，38，73等的Fn皆非素數(shù)。 故費馬的猜測不正確。1

10、、費馬數(shù)：與素數(shù)有關的某些問題尺規(guī)作圖是起源于古希臘的數(shù)學課題。尺規(guī)作圖是指用沒有刻度的直尺和圓規(guī)作圖。 只使用圓規(guī)和直尺，并且只準許使用有限次，來解決不同的平面幾何作圖題。尺規(guī)作圖使用的直尺和圓規(guī)帶有想像性質(zhì)，跟現(xiàn)實中的并非完全相同：1、直尺必須沒有刻度，無限長，且只能使用直尺的固定一側(cè)。只可以用它來將兩個點連在一起，不可以在上畫刻度； 2、圓規(guī)可以開至無限寬，但上面亦不能有刻度。它只可以拉開成之前構造過的長度。2、費馬數(shù)與尺規(guī)作圖的聯(lián)系：一般地，任意正n邊形有以下結論：3、梅森數(shù)梅森數(shù)(Mersenne number)是指形如2p1的正整數(shù)， 其中指數(shù)p是素數(shù)，常記為Mp 。若Mp是素數(shù)，

11、則稱為梅森素數(shù)。早在公元前300多年，古希臘數(shù)學家歐幾里得就開創(chuàng)了研究2p1的先河，他在名著幾何原本 第九章中論述完美數(shù)時指出：如果2P1是素數(shù)， 則(2p1)2p-1是完美數(shù)。 梅森在歐幾里得、費馬等人的有關研究的基礎上 ，對2p1作了大量的計算、驗證工作，并于1644年在他的 物理數(shù)學隨感一書中斷言：對于p=2，3，5，7，13，17，19，31，67，127，257時，2P1是素數(shù) 而對于其他所有小于257的數(shù)時，2P1是合數(shù)。 前面的7個數(shù)屬于被證實的部分，是他整理前人的工作得到的；而后面的4個數(shù)屬于被猜測的部分。 值得提出的是：雖然梅森的斷言中包含著若干錯誤， 但他的工作極大地激發(fā)了

12、人們研究2P1型素數(shù)的熱情， 在梅森素數(shù)的基礎研究方面，法國數(shù)學家魯卡斯和美國 數(shù)學家雷默都做出了重要貢獻；以他們命名的“魯卡斯-雷默方法”是目前已知的檢測梅森素數(shù)素性的最佳方法。 此外，中國數(shù)學家和語言學家周海中給出了梅森素數(shù)分布的精確表達式，為人們尋找梅森素數(shù)提供了方便；這一研究成果被國際上命名為“周氏猜測”。GIMPS ：1995年程序設計師喬治沃特曼(George Woltman) 編制了一個梅森素數(shù)尋找程序并把它放在網(wǎng)頁上供數(shù)學愛好者免費使用：“互聯(lián)網(wǎng)梅森素數(shù)大搜索”計劃(GIMPS，the Great Internet Mersenne Prime Search)。EFF：1999

13、年3月，在互聯(lián)網(wǎng)上活動的一個協(xié)會“電子邊界基金”(EFF，Electronic Frontier Foundation)宣布了由一位匿名者資助的為尋找巨大素數(shù)而設立的獎金。它規(guī)定向第一個找到超過一百萬位的素數(shù)的個人或機構頒發(fā)五萬美元的獎金，超過一千萬位，十萬美元；超過一億位，十五萬美元；超過十億位，二十五萬美元。 2005年，美國數(shù)學家和領導的科研小組CMSU小組發(fā)現(xiàn)了第43個梅森素數(shù)，該素數(shù)有9 152 052位數(shù)：2006年9月4日，CMSU小組再次取得新的成功，一個新的更大的素數(shù)即第44個梅森素數(shù)又被這兩人發(fā)現(xiàn)，這個素數(shù)是2-1,它有位，比前面他們發(fā)現(xiàn)的第43個梅森素數(shù)多了650000位

14、。 2008年8月23日，加州大學洛杉磯分校的電腦發(fā)現(xiàn)第四十五已知梅森素數(shù)，2-1，一個龐大的12,978,189位數(shù)字！這個素數(shù)獲得資格，由EFF的十萬美元獎金發(fā)現(xiàn)第一個千萬位數(shù)的素數(shù)。僅僅相隔兩個星期，2008年9月6日，第46個梅森素數(shù)，2-1，11,185,272位數(shù)，由Hans-MichaelElvenich發(fā)現(xiàn)，在Langenfeld，德國科隆附近！這是自Colquitt和Welsh在1988年發(fā)現(xiàn)2110503-1以來首次梅森素數(shù)不按順序被發(fā)現(xiàn)。 時至今日止，人們已經(jīng)發(fā)現(xiàn)了47個梅森素數(shù)，并且確定M位于梅森素數(shù)序列中的第40位。關于梅森數(shù)有下列的一個命題：第五節(jié) 函數(shù)x,x及其在數(shù)論中的一個應用一、取整函數(shù)及性質(zhì)1、取整函數(shù)x的定義:函數(shù)x與x是對于一切實數(shù)都有定義的