關(guān)于最大素?cái)?shù)
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-01-19 09:02:53 閱讀次數(shù)：3234次
這些天很無(wú)聊的了解了1下幾個(gè)數(shù)學(xué)題
由對(duì)王垠的40行代碼引發(fā)，先是研究了尾遞歸，后又由于王垠的文章《談P=NP？》了解了1下現(xiàn)今數(shù)學(xué)的7大困難，因而又去查其中1個(gè)龐加萊料想的事情（龐加萊料想已解決，后有丘成桐事件），另外哥德巴赫料想的相干事情（陳景潤(rùn)的1+2，非7大困難），最后又回到P/NP問(wèn)題（7大困難之1），結(jié)果不謹(jǐn)慎又無(wú)聊的去查了1下最大素?cái)?shù)問(wèn)題，更無(wú)聊的是還隨著去證明了1下。。。跟我的編程工作毫無(wú)關(guān)系嘛。。。我發(fā)現(xiàn)我的思惟也太散了。。。
關(guān)于最大素?cái)?shù)問(wèn)題
是不是有最大素?cái)?shù)，下面是百度百科給出的證明進(jìn)程：
不存在最大質(zhì)數(shù)!
上小學(xué)的時(shí)候，我們就知道所有的自然數(shù)可以分為質(zhì)數(shù)（素?cái)?shù)）和合數(shù)兩類(lèi)，固然還特別規(guī)定了“1既不是質(zhì)數(shù)，也不是合 數(shù)”。100之內(nèi)的質(zhì)數(shù)，從小到大順次是：2、3、5、7、11、13、17、19、……、83、89、97。不用說(shuō)了，你1定會(huì)背下來(lái)。那末質(zhì)數(shù)的個(gè)數(shù) 是否是有限多的呢？
在解決這個(gè)問(wèn)題之前，我們先來(lái)看看另外一個(gè)問(wèn)題：怎樣判斷1個(gè)已知自然數(shù)是否是質(zhì)數(shù)。比如，143是否是質(zhì)數(shù)？
你1定會(huì)依照下面這個(gè)步驟去判斷： 先用最小的質(zhì)數(shù)2去除143，不能整除；再用3去試試，還是不行；再順次用5、7試試，還是不行；11呢？行！143=11×13，所以143不是質(zhì)數(shù)，而是合數(shù)。所以，判斷1個(gè)數(shù)是否是質(zhì)數(shù)，只需用比這個(gè)數(shù)小的所有質(zhì)數(shù)，順次去除它便可，如果都不能整除的話(huà)，這個(gè)數(shù)就1定是質(zhì)數(shù)；相反，只要這個(gè)數(shù)能夠被某1個(gè)質(zhì)數(shù)整除，這個(gè)數(shù)就1定是合數(shù)。這類(lèi)方法所根據(jù)的原理是：每個(gè)合數(shù)都可以表示成若干個(gè)質(zhì)數(shù)的乘積。不用說(shuō)，這叫做“分解質(zhì)因數(shù)”，也是小學(xué)數(shù)學(xué)的知識(shí)。
我們先假定質(zhì)數(shù)的個(gè)數(shù)是有限多的，那末必定存在1個(gè)“最大的質(zhì)數(shù)”，設(shè)這個(gè)“最大的質(zhì)數(shù)”為N。下面我們找出從1到N之間的所有質(zhì)數(shù)，把它們連乘起來(lái)，就是：
2×3×5×7×11×13×……×N
把這個(gè)連乘積再加上1，得到1個(gè)相當(dāng)大的數(shù)M：
M=2×3×5×7×11×13×……×N+1
那末這個(gè)M是質(zhì)數(shù)還是合數(shù)呢？ 乍1想，不難判斷，既然N是最大的質(zhì)數(shù)，而且M>N，那末M就應(yīng)當(dāng)是合數(shù)。既然M是合數(shù)，就能夠?qū)分解質(zhì)因數(shù)。可是試1下就會(huì)發(fā)現(xiàn)，我們用從1到N之間的任何1個(gè)質(zhì)數(shù)去除M，總是余1！這個(gè)現(xiàn)實(shí)，又表明M1定是質(zhì)數(shù)。
這個(gè)自相矛盾的結(jié)果，不過(guò)說(shuō)明： 最大的質(zhì)數(shù)是不存在的！如果有1個(gè)足夠大的質(zhì)數(shù)N，1定可以像上面那樣，找到1個(gè)比N更大的質(zhì)數(shù)M。既然不存在最大的質(zhì)數(shù)，就能夠推知自然數(shù)中的質(zhì)數(shù)應(yīng)當(dāng)有沒(méi)有限多個(gè)。
可同時(shí)百度百科有人給出了另外一個(gè)反例：
M=2×3×5×7×11×13×……×N+1,用從1到N之間的任何1個(gè)質(zhì)數(shù)去除M，總是余1！這個(gè)現(xiàn)實(shí)，又表明M1定是質(zhì)數(shù)。此結(jié)論大錯(cuò)特錯(cuò)，例如，2×3×5×7×11×13+1=30031=59×509，30031是個(gè)合數(shù)。
看到這個(gè)反例，我開(kāi)始懷疑以上證明的正確性，因而想了好久，終究想明白，該證明是正確的！
反例的毛病點(diǎn)在于他沒(méi)有除比30031小的所有素?cái)?shù)，僅除到13，而要證明1個(gè)素是不是素?cái)?shù)必須要除比他小的所有素?cái)?shù)均不能整除才可以證明該數(shù)是素?cái)?shù)。
關(guān)于快速證明1個(gè)數(shù)是不是素?cái)?shù)采取該數(shù)除以比他小的所有素?cái)?shù)便可快速判斷而無(wú)需除比他小的所有數(shù)，這個(gè)很好證明！每個(gè)合數(shù)必定可以表示成若干素?cái)?shù)的乘積，1樣很容易證明。這里不贅述。
我們之所以對(duì)以上證明進(jìn)程存在質(zhì)疑，主要來(lái)自于該證明的結(jié)論是N如果是最大素?cái)?shù)，那末M還是素?cái)?shù)。因而通過(guò)反例N=13，則M=30031，可30031是合數(shù)即M是合數(shù)，與上面的推論M是素?cái)?shù)矛盾了！！這是怎樣回事呢？是不是說(shuō)明這個(gè)推論是毛病的呢？經(jīng)過(guò)思考我們發(fā)現(xiàn)，證明中認(rèn)定M是素?cái)?shù)的條件是首先我們得認(rèn)定N是最大的素?cái)?shù)！！才推出M還是素?cái)?shù)，然后自相矛盾，便可反證N不是最大素?cái)?shù)。而反例中的條件條件即出錯(cuò)，N=13，明顯13不是最大素?cái)?shù)他就不可能成為N。
我們先不斟酌M和N誰(shuí)比較大，按證明即先認(rèn)定N為最大的素?cái)?shù)，那末可推出M一定為素?cái)?shù)這個(gè)結(jié)論。最后發(fā)現(xiàn)M>N，故N就不是最大素?cái)?shù)。
然后再來(lái)看反例：”M=2×3×5×7×11×13×……×N+1,用從1到N之間的任何1個(gè)質(zhì)數(shù)去除M，總是余1！這個(gè)現(xiàn)實(shí)，又表明M1定是質(zhì)數(shù)。此結(jié)論大錯(cuò)特錯(cuò)，例如，2×3×5×7×11×13+1=30031=59×509，30031是個(gè)合數(shù)。“，其實(shí)M除以1到N總余1表示M1定是素?cái)?shù)這個(gè)結(jié)論并沒(méi)有錯(cuò)，由于這個(gè)結(jié)論的條件條件是N是我們假定的最大素?cái)?shù)成立的條件，而不是指任意素?cái)?shù)，作者混淆概念，如例子將13=N，推出出30031為M，而M不是素?cái)?shù)所以顛覆結(jié)論，這條件條件就不正確了。
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
