題記

“所以，這就是數(shù)學(xué)：她賦予自己的發(fā)現(xiàn)以生命；她令思維活躍，精神升華；她燭照我們的內(nèi)心，消除了我們與生俱有的蒙昧與無知?！?/p>

——（5世紀(jì)希臘評注家）普羅克洛斯

上圖是《孫子算經(jīng)》序言

上一篇文章是《從2520的秘密說起》，這次我們接著話題繼續(xù)談?wù)勛畲蠊s數(shù)和最小公倍數(shù)。

話說寫完上一篇文章后，女兒放學(xué)回家了。我考了她從2到11各數(shù)的倍數(shù)有何特征，意料之外的是女兒對答如流，完整正確。再考她2到10的最小公倍數(shù)問題，她說簡單，很快在紙上演算，用短除法得出答案:2520。厲害了，看來是勤于思考的結(jié)果，付出必有收獲，念念不忘，必有回響。士別三日，當(dāng)刮目相看。

上圖是短除法計算2至10的最小公倍數(shù)

先看一下這個題目：某個3位數(shù)的數(shù)字，用2除，余1,用3除，還余1,用4除，也余1；用5除，也余1；用6除，還余1；用7除，還是余1。

這個數(shù)是多少呢？這個數(shù)肯定是500以上的數(shù)字。

［答案］用從2到7的哪個數(shù)除，都可以除得盡的數(shù)是：

2×3×4×5×6×7=5040，

這個數(shù)是2到7的公倍數(shù)，但不是最小公倍數(shù)。上面的算式有2個合數(shù)：4和6，還能再分解質(zhì)因數(shù)，所以要求的最小公倍數(shù)是：

2×2×3×5×7=420。

因此，給421加上1得出421,則用2到7之間的任何數(shù)去除，都是余1。

審題，還有一個條件是500以上的3位數(shù)，所以，正確答案是：

420×2+1=841

華杉說：‘’君子無所不用其極，做任何事，都有很簡單的辦法，為什么不行呢，因為你做不徹底。我們講“凡事徹底”，成功不是做不平凡的事，而是把平凡的事做徹底。

凡事徹底就是要把平凡的小事做徹底，做到極致。做到凡事徹底就是天下的王道?！?/p>

那么，我們就對這個問題來個徹底解剖。

2的最小倍數(shù)是2，

2、3的最小公倍數(shù)是6，

2、3、4的最小公倍數(shù)是12（2×2×3），

2、3、4、5的最小公倍數(shù)是60（2×2×3×5），

2、3、4、5、6的最小公倍數(shù)是60（2×2×3×5），

2、3、4、5、6、7的最小公倍數(shù)是60×7=420（2×2×3×5×7），

2、3、4、5、6、7、8的最小公倍數(shù)是420×2=840（2×2×2×3×5×7），

2、3、4、5、6、7、8、9的最小公倍數(shù)是840×3=2520（2×2×2×3×3×5×7），

考察2520，發(fā)現(xiàn)它包含的質(zhì)因數(shù)里有2和5，所以肯定是10的倍數(shù)。

求最小公倍數(shù)和最大公約數(shù)有三種方法：分解質(zhì)因數(shù)法、短除法和輾轉(zhuǎn)相除法。

下面談?wù)動枚坛ㄇ笞钚」稊?shù)和最大公約數(shù)。短除法求最大約數(shù)，先用這幾個數(shù)的公約數(shù)連續(xù)去除，一直除到所有的商互質(zhì)為止，然后把所有的除數(shù)連乘起來，所得的積就是這幾個數(shù)的最大公約數(shù)。短除法求最小公倍數(shù)，先用這幾個數(shù)的公約數(shù)去除每一個數(shù)，再用部分?jǐn)?shù)的公約數(shù)去除，并把不能整除的數(shù)移下來，一直除到所有的商中每兩個數(shù)都是互質(zhì)的為止，然后把所有的除數(shù)和商連乘起來，所得的積就是這幾個數(shù)的最小公倍數(shù)。

請看圖，L形線段的左側(cè)是除數(shù)，下面的是商，左側(cè)的除數(shù)也是因數(shù)。把下面的商和左側(cè)的因數(shù)連乘，就求出了最小公倍數(shù)。

上圖是短除法示意圖

補充一個技巧：求n個數(shù)的最小公倍數(shù)，我們只需要把最大的那個數(shù)擴大若干整數(shù)倍（從1開始）如果這個數(shù)能夠同時整除其他的數(shù)，那么這個數(shù)就是這n個數(shù)的最小公倍數(shù)。

例如：求4,6,8的最小公倍數(shù)

將8擴大若干整數(shù)倍（從1開始）

8×1=8， 8能整除4，但是不能整除6，所以8不是

8×2=16 16能整除4，但是不能整除6，所以16不是

8×3=24 24能整除4，也能整除6，所以他們的最小公倍數(shù)就是24

為什么說要從1開始乘呢？比如，求2,4,8的最小公倍數(shù)：

8×1=8， 8能整除4，也能整除2，所以8就是2,4,8的最小公倍數(shù)，此時你如果從2開始乘，就會把他們的最小公倍數(shù)算大了。

求60、28、35的最小公倍數(shù)，如果你在考場上用短除法去求，我想很多人不但會很慢，而且還容易出錯，那么可以換個思路，將最大的數(shù)60擴大若干整數(shù)倍。很明顯，28、35都能被7整除，那么我們直接給60×7=420，420恰好能整除28、35，所以420就是他們的最小公倍數(shù)，怎么樣？是不是很快？

再說說輾轉(zhuǎn)相除法。

在數(shù)學(xué)中，輾轉(zhuǎn)相除法，又稱歐幾里得算法，是求最大公約數(shù)的算法。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。歐幾里得的《幾何原本》大約是在公元前300年，所以輾轉(zhuǎn)相除法是現(xiàn)有算法中歷史最悠久的。

輾轉(zhuǎn)相除法計算的是兩個自然數(shù)a和b的最大公約數(shù)g，意思是能夠同時整除a和b的自然數(shù)中最大的一個。兩個數(shù)的最大公約數(shù)通常寫成GCD(a, b)。例如，計算a=1071和b=462的最大公約數(shù)的過程如下：從1071中不斷減去462直到小于462（可以減2次，即商q0 = 2），余數(shù)是147：

1071 = 2 × 462 + 147

然后從462中不斷減去147直到小于147（可以減3次，即q1 = 3），余數(shù)是21：

462 = 3 × 147 + 21

再從147中不斷減去21直到小于21（可以減7次，即q2 = 7），沒有余數(shù)：

147 = 7 × 21 + 0

此時，余數(shù)是0，所以1071和462的最大公約數(shù)是21，這和用質(zhì)因數(shù)分解得出的結(jié)果相同。

上圖是輾轉(zhuǎn)相除法的演示動畫

輾轉(zhuǎn)相除法的演示動畫：兩條線段分別表示252和105，其中每一段表示21。如動畫所示，只要輾轉(zhuǎn)地從大數(shù)中減去小數(shù)，直到其中一段的長度為0，此時剩下的一條線段的長度就是252和105的最大公約數(shù)。

上圖解釋了公約數(shù)的意義

有數(shù)無形不直觀，有形無數(shù)不精確。數(shù)形結(jié)合更完美。如上圖所示，一個24×60的長方形正好被十個12×12的方格填滿，其中12是24和60的最大公約數(shù)。一般地，當(dāng)且僅當(dāng)c是a和b的公約數(shù)時，a×b尺寸的長方形可被邊長c的正方形正好填滿。

保羅·裘唐諾所著的小說《質(zhì)數(shù)的孤獨》（The Solitude of Prime Numbers）里，質(zhì)數(shù)被用來比喻寂寞與孤獨，被描述成整數(shù)之間的“局外人”。那么，孤獨的質(zhì)數(shù)，以及最大公約數(shù)和最小公倍數(shù)，它們有什么用呢？

請看古典名題：河婦蕩杯。（選自《孫子算經(jīng)》17卷下）

今有婦人河上蕩杯，津吏問曰：“杯何以多？”婦人曰：“家有客?！苯蚶粼唬骸翱蛶缀危俊眿D人曰：“二人共飯，三人共羹，四人共肉，凡用杯六十五，不知客幾何？”

譯文：有一個婦女在河邊洗碗。管理渡口的官吏問她：“怎么有這么多碗？”婦女回答說：“我家里來客人了?！?官吏問：“有幾個客人？”婦女回答：“每兩人共吃一碗飯，三人共喝一碗湯，四人共吃一碗肉，總共用了六十五只碗。我也不清楚到底有多少客人?！?/p>

此題《孫子算經(jīng)》中的解法是這樣記載的：“置六十五只杯,以一十二乘之,得七百八十,以一十三除之,即得?！苯忸}思路：每個客人使用的碗數(shù)為1/2+1/3+1/4=13/12 總用碗數(shù)除以13/12即得人數(shù)：

65÷（1/2+1/3+1/4）=65÷13/12=60（人）

12是2、3、4的最小公倍數(shù)，每12位客人要用13只碗。假設(shè)12位客人坐一桌，那么共有5桌客人，5×12=60（人），每桌用13只碗，5×13=65（只）碗，驗算無誤。

類似的，有道小學(xué)奧數(shù)題：某學(xué)校五年級一班周末會餐，每人一個飯碗，每兩人一個菜碗，每三人一個湯碗，每四人一個肉碗，合計用了100個碗，問五年級一班有多少同學(xué)會餐？

同樣的解題思路：12是2、3、4的最小公倍數(shù)，每12位客人要用多少碗呢？12+6+4+3=25，假設(shè)12位同學(xué)坐一桌，那么共有4桌，每桌用25只碗，4×25=100,4桌同學(xué)人數(shù)是4×12=48（人）。

答：五年級一班有48人會餐。這道奧數(shù)題隱含了對“河婦蕩杯”的兩人共用一個飯碗的吐槽。

再來看這道題：三女歸寧。（選自《孫子算經(jīng)》35卷下）

今有三女，長女五日一歸，中女四日一歸，少女三日一歸，問三女幾何日相會？

題意是一家有三個女兒平時分別回娘家，大女兒5天回一次，二女兒4天回一次，小女兒3天回一次。問這三個女兒何時在娘家相會？

解答：這是一個求最小公倍數(shù)問題。5、4、3的最小公倍數(shù)是60，故答案是三女每60天相會一次。

看完這些題目，大家是否覺得整數(shù)分解很簡單，難度太低了。告訴你一個好消息和一個壞消息：好消息是你在生活和工作中遇到的題目都不是很難，壞消息是難的題目你一千年也做不出來。問問密碼學(xué)家，他會告訴你大整數(shù)分解非常困難。

RSA加密演算法是一種非對稱加密演算法。在公開密鑰加密和電子商業(yè)中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當(dāng)時他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。

對極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。

2002年，RSA-158被成功因數(shù)分解。

RSA-158表示如下：

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609

727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×

11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年12月12日，編號為RSA-768（768 bits, 232 digits）數(shù)也被成功分解。這一事件威脅了現(xiàn)通行的1024-bit密鑰的安全性，普遍認(rèn)為用戶應(yīng)盡快升級到2048-bit或以上。

RSA-768表示如下：

123018668453011775513049495838496272077285356959533479219732245215172640050726

365751874520219978646938995647494277406384592519255732630345373154826850791702

6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891

2431388982883793878002287614711652531743087737814467999489×

3674604366679959042824463379962795263227915816434308764267

6032283815739666511279233373417143396810270092798736308917

大家都知道林肯的葛底斯堡演講，僅10句話3分鐘272單詞，卻是英語演講的最高典范！今天講一個故事，一塊黑板和一言不發(fā)的學(xué)術(shù)報告的故事。（天地有大美而不言，天何言哉，天何言哉！）

2^67-1=193707721*761838257287 你可以用電腦計算器驗算一下. 1903年,在紐約的一次數(shù)學(xué)報告會上,數(shù)學(xué)家科勒上了講臺，他沒有說一句話，只是用粉筆在黑板上寫了兩數(shù)的演算結(jié)果，一個是2的67次方－1，另一個是193707721×761838257287，兩個算式的結(jié)果完全相同,這時,全場爆發(fā)出經(jīng)久不息的掌聲.這是為什么呢? 因為科勒解決了兩百年來一直沒弄清的問題,即2是67次方－1是不是質(zhì)數(shù)?現(xiàn)在既然它等于兩個數(shù)的乘積,可以分解成兩個因數(shù),因此證明了2是67次方－1不是質(zhì)數(shù),而是合數(shù)?？评罩蛔隽艘粋€簡短的無聲的報告,可這是他花了3年中全部星期天的時間,才得出的結(jié)論.在這簡單算式中所蘊含的勇氣,毅力和努力，卻別具魅力。正如高斯所說：給我最大快樂的，不是已懂得知識，而是不斷的學(xué)習(xí)；不是已有的東西，而是不斷的獲??；不是已達(dá)到的高度，而是繼續(xù)不斷的攀登。這就是科勒教授征服第9個梅森數(shù)的原動力。

01

02

03

04

05

摘自《不知道的世界，數(shù)學(xué)卷》小學(xué)2000年左右看過的一本科普書，此書后來經(jīng)過數(shù)版修訂，圖是剛才看到Kindle上有賣最新修訂版，遂截圖。以上圖片來自知乎網(wǎng)友。

科勒的論文下載地址 ?科勒教授論文下載地址

https://projecteuclid.org/download/pdf_1/euclid.bams/1183417760

上面的鏈接是英文，英語差和數(shù)學(xué)差的學(xué)渣千萬不要手賤去點，點進(jìn)去你也看不懂。

花絮和彩蛋

擦黑板表白公式

music video動圖

來自K.will（金亨秀）—《I need you》的MV，大約1分55秒左右出現(xiàn)。視頻地址

http://v.youku.com/v_show/id_XMzUyMjk3MjE2.html?x&sharefrom=android

一無所有.mp3? 5:32.298

來自百科漫談

崔健《一無所有》歌詞：

我曾經(jīng)問個不休

你何時跟我走

可你卻總是笑我

一無所有

我要給你我的追求

還有我的自由

可你卻總是笑我

一無所有

噢……你何時跟我走

噢……你何時跟我走

腳下的地在走

身邊的水在流

可你卻總是笑我

一無所有

為何你總笑個沒夠

為何我總要追求

難道在你面前

我永遠(yuǎn)是一無所有

噢……你何時跟我走

噢……你何時跟我走

腳下的地在走

身邊的水在流

告訴你我等了很久

告訴你我最后的要求

我要抓起你的雙手

你這就跟我走

這時你的手在顫抖

這時你的淚在流

莫非你是在告訴我

你愛我一無所有

噢……你這就跟我走

噢……你這就跟我走

噢……你這就跟我走

我現(xiàn)在在今日頭條更新，歡迎關(guān)注我的頭條號 百科漫談

我的頭條號ID是 ?1635049648381960

歡迎訪問我的頭條號！