素數(shù)與公因數(shù)
1、素數(shù) 我們知道,大于1,并且除1和它本身外沒有其他因數(shù)的自然數(shù)叫素數(shù)(或質(zhì)數(shù))
2是最小的素數(shù),除2以外,所有的偶數(shù)都不是素數(shù).
按順序,下列為一個小素數(shù)序列:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,…
不是素數(shù)的整數(shù)a>1稱為合數(shù).例如,因為有3|39,所以39是合數(shù).整數(shù)1被稱為基數(shù),它既不是質(zhì)數(shù)也不是合數(shù).類似地,整數(shù)0和所有負(fù)整數(shù)既不是素數(shù)也不是合數(shù).
關(guān)于素數(shù),有如下重要結(jié)論：
①素數(shù)有無窮個.
證明：假設(shè)素數(shù)只有有限的n個,從小到大依次排列為p1,p2,...,pn,則 x = (p1·p2·...·pn)+1 顯然是不能被p1,p2,...,pn中的任何一個素數(shù)整除的,因此x也是一個素數(shù),這和只有n個素數(shù)矛盾,所以素數(shù)是無限多的.
這個證明的最早來自亞里士多德,非常漂亮,是反證法的經(jīng)典應(yīng)用,這個證明被歐拉稱為“直接來自上帝的證明”,歷代的數(shù)學(xué)家也對其評價很高.
但是,千萬不可認(rèn)為,形如p1·p2·...·pn+1（其中p1,p2,...,pn均為素數(shù)）的數(shù)就一定是素數(shù)!第八屆全國青少年信息學(xué)奧林匹克聯(lián)賽（NOIP2002)提高組初賽試題第三題第2小題,寫程序運行結(jié)果,程序要找的就是形如p1·p2·...·pn+1（其中p1,p2,...,pn均為素數(shù)）的數(shù)中第一個是合數(shù)的整數(shù).
2*3+1=7 是素數(shù)
2*3*5+1=31 是素數(shù)
2*3*5*7+1=211 是素數(shù)
2*3*5*7*11+1=2311 是素數(shù)
2*3*5*7*11*13+1=30031 不是素數(shù),因為30031=59*509
引用內(nèi)容
華東師范大學(xué)版的數(shù)學(xué)9年級教材P94有這樣一個命題：
從素數(shù)2開始,排在前面的任意多個素數(shù)的乘積加1一定也是素數(shù).
這個結(jié)論就是錯誤的.
雖然最大的素數(shù)是不存在的,但是人們卻對探知最大的素數(shù)樂此不疲.
213466917-1
這是到目前為止人類所發(fā)現(xiàn)的最大素數(shù),它是由Michael在2001年12月7日發(fā)現(xiàn)的,這是一個梅森素數(shù),有4,053,946位數(shù)字.
所謂梅森素數(shù),是以17世紀(jì)法國修道士M.梅森的名字命名的.梅森在1644年出版的著作《物理數(shù)學(xué)隨感》的序言中宣稱,對于n=2,3,5,7,13,17,19,31,67,127,257,數(shù)Mn=2n-1是素數(shù),而對于其他所有小于257的數(shù)n,Mn是合數(shù).但是,這里出現(xiàn)了5個錯誤,M67,M257不是素數(shù),而M61,M89,M107是素數(shù).顯然,要使Mn是素數(shù),n本身必須是素數(shù),但是反過來,n是素數(shù),Mn卻不一定是素數(shù),例如雖然11是素數(shù),可是M11=2047=23X89是合數(shù).
現(xiàn)在尋找很大的梅森素數(shù)時,已經(jīng)完全依賴于計算機了,可以想象,離開了計算機,我們?nèi)祟悓淙胍环N怎樣的地步.當(dāng)D.H.萊默博士這位曾經(jīng)在梅森素數(shù)上花費了許多時光的老學(xué)者,親眼看到了計算機在短短的48秒鐘內(nèi)做完了他20年前花費了700多小時才完成的艱辛勞動,最后證明2257-1是一個合數(shù)時,他是多么地感慨萬端哪.
時至今日,人類只找到39個梅森素數(shù).前18個梅森素數(shù)是n=2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217時的Mn=2n-1.下表列出了從1961年以來所發(fā)現(xiàn)的全部梅森素數(shù).
------------------------------------------------------------------------------
素數(shù)是無限的,歐幾里得在《幾何原本》里面已經(jīng)給出了證明,現(xiàn)在已經(jīng)有很多種證明方法了.這里我收集一兩個.
證法一：
（一）學(xué)過初中的同學(xué)都知道n!與n!+1互質(zhì).故n!與1、2、3、…..n-1、n互質(zhì)那么n!+1有2種可能（1）n!+1為素數(shù).(2)n!+1為合數(shù)
（1）設(shè)a=n!+1為素數(shù) 集合A={x|0