正文

互質數是什么意思舉例說明(帶你了解互質數的定義是什么)

5424

任選兩個自然數,它們互質的概率是多少?它就是s = 2時歐拉乘積公式右邊的連乘的倒數,因此它等于s = 2時歐拉乘積公式左邊的連加的倒數,即1/ζ(2)。而ζ(2) = π^2/6,因此這個概率等于6/π^2 ≈ 60.79%。同樣的,三個自然數互質的概率是1/ζ(3) ≈ 83.19%,四個自然數互質的概率是1/ζ(4) ≈ 92.39%。

在上一期節目(文章見理解黎曼猜想(一)背景 | 袁嵐峰,視頻見
https://www.bilibili.com/video/av34580488)中,我們首先介紹了黎曼猜想的背景,即質數分布問題。然后指出了研究質數分布的基本工具,即歐拉乘積公式:

這個公式左邊的n指的是所有的自然數,1、2、3、4、5等等,右邊的p指的是所有的質數,2、3、5、7、11等等。公式兩端都出現的s是一個變量,當s > 1時歐拉乘積公式成立。

數學家經常用大寫的希臘字母Σ來表示求和,用大寫的希臘字母Π來表示連乘。用這種表達方式,我們可以把歐拉乘積公式簡寫成下面這樣:

然后,我們給出了歐拉乘積公式的證明。如果把n-s記作f(n),左邊就是無窮級數Σn?f(n)。對這個無窮級數乘以[1 – f(2)],就會消掉所有的f(2n)項。再乘以[1 – f(3)],就會消掉剩下的項中所有的f(3n)項。再乘以[1 – f(5)],就會消掉剩下的項中所有的f(5n)項。把這樣的操作重復無限多次,就會消掉所有的質數的倍數對應的項,也就是消掉所有的大于1的自然數對應的項,最后只剩下f(1)這一項,它等于1。把所有乘上去的[1 – f(2)] [1 – f(3)] [1 – f(5)]…等等移到右邊去,就是歐拉乘積公式的右邊Πp?[1 – f(p)]-1。這樣,我們就證明了歐拉乘積公式。

這其實就是當初歐拉的證明方法。它確實是一個非常巧妙的證明,堪稱人類智慧的偉大結晶,令人贊嘆不已。

歐拉

在上期節目的視頻中,我注意到一件有趣的事。當我開始講這個證明過程的時候,彈幕中充滿了“告辭”、“勸退”、“陣亡”、“我是誰,我在哪,我在干什么”之類自暴自棄的話。但隨著講解過程的深入,越來越多的彈幕變成了“懂了”、“妙啊”、“存活”、“說得很清楚啊”。最后當證出來的時候,更是充滿了一大片的“原來如此”、“太精彩了”、“恍然大悟”、“開心”等等。

真香

隔著屏幕都能感覺到同學們的“開心”,令我很欣慰。吶,做人呢,最重要就是開心!

做人最重要就是開心

理解數學有一種獨特的開心,是其他任何東西都不能代替的。就像我以前講藍眼睛島問題的十個層次從藍眼睛問題,看群眾理解能力的巨大差異 | 袁嵐峰,完全理解了的同學就會非常高興,因為他們從中學到的不止是這個問題本身的答案,還包括如何研究問題、如何獲得深入理解的思維方法。

在上期節目的開頭,我就講了兩個心理建設:一是打破跳蚤效應,勇敢地去面對數學;二是拿起紙筆,把瓜放下。任何同學如果真正按照這兩點去做,我相信你就一定能領略到數學的樂趣!

回到歐拉乘積公式,左邊的無窮級數Σn?n-s是一個以s為自變量的函數,可以記作ζ(s)(ζ是一個希臘字母,發音zeta)。現在我們把它稱為歐拉ζ函數,以后我們會看到它如何變成了黎曼ζ函數。通過研究ζ函數,我們就有可能對質數獲得深刻的了解。什么樣的了解呢?下面就來舉一個例子。

請問:任選兩個自然數,它們互質(coprime)的概率是多少?

首先來解釋一下,兩個自然數互質的意思,就是它們沒有共同的質因數,換句話說就是,它們的最大公約數是1。例如2和3互質,2和15互質,但15和21不互質,因為15和21都以3作為質因數。很快可以看出,任意兩個不同的質數是互質的,一個質數和一個不以它作為質因數的合數是互質的,1和任意自然數都是互質的。

了解了互質的定義之后,我們如何計算兩個自然數互質的概率呢?

可以這樣思考。首先,考慮兩個自然數有公約數2的概率。這等價于它們都可以表示成2n,而所有可以表示成2n的自然數在所有的自然數當中占據的比例是1/2。因此,任選一個自然數,它可以表示成2n的概率是1/2。而任選兩個自然數,它們都可以表示成2n的概率就是1/2的平方,這就是它們有公約數2的概率。那么作為跟這種情況互補的情況,兩個自然數沒有公約數2的概率,就是1-1/22。

然后,根據同樣的推理,兩個自然數沒有公約數3的概率,就是1-1/32。繼續下去,兩個自然數沒有公約數5的概率,就是1-1/52,如此等等。

最后,兩個自然數互質,就等價于它們的公約數既沒有2,也沒有3,也沒有5等等,沒有任何一個質數。因此,兩個自然數互質的概率等于上面各個概率乘起來,

這個表達式等于什么?仔細看一下,你就會發現,它就是s = 2的時候歐拉乘積公式右邊那個連乘的倒數!因此,它等于s = 2時歐拉乘積公式左邊那個連加的倒數,也就是1/ζ(2)。

真是妙啊!現在問題變成了,ζ(2)等于多少?根據定義,

也就是所有自然數的平方倒數的和。請問,它等于多少?

回答是π2/6,約等于1.6449。咦,在這里為什么會出現圓周率?這當然是有原因的啦。事實上這個等式又是歐拉證明的,這是歐拉的成名作之一。這個證明十分有趣,不過要用到微積分,許多同學們還沒有學過,而且這個證明不是我們當前必需的,所以在這里我們就不講了,有興趣的同學請自己查閱文獻。

歐拉

對于當前的目的,把ζ(2) = π2/6代進去,我們就知道了:兩個自然數互質的概率等于6/π2!數值計算一下,它約等于60.79%。

這個結論對不對呢?我們還可以用計算機來驗證一下。

我的朋友、風云學會會員陳經是計算機專家,他幫我寫了一個程序,在1到32768(即2的15次方)之間隨機取兩個自然數,看它們是否互質。在測試1千萬次后,發現兩個自然數互質的次數總共有6080726次。因此在這個測試中,兩個自然數互質的頻率是60.80726%。請看,它跟理論值60.79%是多么接近!

事實上,如果你學過數值分析,你就會知道這是一個相當粗糙的數值實驗。在你考慮全體自然數的性質的時候,32768這個取值上限實在是太小了,小得有點令人發笑。以后我們會講到一個例子,算到1千億億都不足以保證結果成立。我們重復一下,1千億億!這是一個令人驚掉下巴的例子。但在這里,令人吃驚的卻是,對32768這么小的樣本取樣,就足以得到十分接近理論值的結果。這說明,兩個自然數互質的概率這個問題,隨著取樣范圍的增大,收斂得是非常快的。

你看,我們是不是通過研究ζ函數,對質數的分布獲得了驚人的結果?

根據同樣的推理,我們很快會發現,任選s個自然數,它們互質的概率就是1/ζ(s)。在這里需要說明一下,三個或更多個自然數互質的意思,是所有這些數的整體的公約數只有1,而不是其中任何兩個自然數的公約數也只有1。例如考慮2、3、4這三個自然數,其中的兩個數2和4不互質,但這三個數的整體是互質的,這種情況我們把它算作三個數互質。

根據這個定義,你很容易看出,s越大,s個自然數互質的概率就越大。因為隨著s的增大,某個質數剛好是s個自然數的共同質因子的可能性,就越來越低了。

從ζ函數的角度來考察,也確實應該如此。當s > 1的時候,n-s是一個減函數,所以ζ(s) = Σn?n-s也是一個減函數。隨著s的增加,ζ(s)在減小,所以ζ(s)的倒數在增大,也就是說s個自然數互質的概率在增大。

好,現在讓我們把視線投向任意正整數s對應的ζ(s)。

在這里可以告訴大家,對于正的偶數s,ζ(s)是可以快速求出的,而且其中總是包含圓周率π的s次方。例如ζ(4),也就是所有自然數的四次方的倒數之和,它等于π4/90,約等于1.0823。由此可以算出,四個自然數互質的概率等于90/π4,約等于92.39%。

然而對于正的奇數s,ζ(s)的計算就會變得非常麻煩,很難有個簡單的表達式。例如對于ζ(3),也就是所有自然數的三次方的倒數之和,我們就只能說它約等于1.2021。你要是想把它精確地表示出來,就只有一些比較復雜的積分或者無窮級數或者連分數的表達形式。

無論如何,根據ζ(3) ≈ 1.2021,我們可以算出三個自然數互質的概率約等于83.19%。從兩個自然數互質的概率60.79%,到三個自然數互質的概率83.19%,到四個自然數互質的概率92.39%,我們看到它們確實是在上升的,符合預期。

隨著s趨于無窮大,ζ(s) = Σn?n-s當中只有第一項1不受影響,后面的項都迅速地趨近于0,所以ζ(s)會趨近于1。相應的,s個自然數互質的概率也確實會趨近于100%,這都是很容易理解的。

你也許會問:s只能取整數值嗎?當然不是,它完全可以取3/2(也就是1.5)或者1.6或者π等非整數的值。對于非整數的s,ζ(s)仍然是有明確定義的,只不過這時不能跟所謂“s個自然數互質的概率”聯系起來了。你可以計算ζ(3/2),它約等于2.6124,但你無法談論所謂“1.5個自然數”。

如果你對分數指數感到迷惑,請翻一下高中數學課本就知道了。這里可以提示一下,一個數的3/2次方,等于它的三次方的平方根。而一個數的π次方,就等于它的3次方、3.1次方、3.14次方、3.141次方、3.1415次方、3.14159次方等等這個數列的極限。

現在,我們對ζ函數增加了許多了解,明白了它跟質數有深刻的聯系,并且知道了它在若干個點上的取值。現在,你是不是對這個函數感到很親切,而不會感到恐懼了?

不過我們必須強調一下,到目前為止,所有的s都是大于1的。你也許會問,ζ(1)等于多少?也就是說,所有自然數的倒數和等于多少?在數學上,我們又把它稱為調和級數(harmonic series)。

現在,一個關鍵點來了:ζ(1)等于無窮大!也就是說,調和級數是發散的!

為什么會這樣?讓我們把ζ(1)的表達式寫出來,就能夠做下面的推理:

最后那個式子中,隨著項數的增加,會出現無窮多個1/2。無窮多個1/2加起來當然會大于任意的有限值,因此最后的式子是發散的。而ζ(1)比它還要大,所以當然也是發散的。

如果你覺得上面的表達方式不太嚴格,那么我們真正想表達的意思是:對于任意大的自然數k,都有下面的不等式。

實際上,調和級數雖然是發散的,但它發散得非常慢。把前面的10的43次方項加起來,都沒有超過100。10的43次方是多少?一億是10的8次方,所以10的43次方就是1千億億億億億。用物理世界舉個例子,整個宇宙的半徑大約是137億光年,量級是10的26次方米,一個原子核的半徑是10的-15次方米的量級,宇宙半徑除以原子核半徑也不過是10的41次方而已,還要再乘以100才能達到10的43次方。想想看,1千億億億億億個數加起來,都沒超過100!這是怎樣的一種增長速度啊!

為什么會這樣呢?原因又是歐拉告訴我們的。歐拉證明了,調和級數的增長速度,大致就是自然對數的增長速度。如果你沒學過自然對數,那么可以簡單解釋一下:常用對數(經常寫成lg)是以10為底的對數,而自然對數(經常寫成ln)是以e為底的對數,這里的e是一個常數,約等于2.71828。為什么要以這樣一個數為底?因為在數學上,lnx具有許多很好的性質,處理起來比lgx方便得多。其實在數學中,自然對數才是“常用”的,比所謂“常用對數”常用得多。

歐拉

更具體地說,歐拉證明了,調和級數的前n項之和約等于lnn,而隨著n的增大,它們的差值會趨近于一個常數γ:

這個常數叫什么名字呢?當然,又叫做歐拉常數(Euler’s constant)……咦,我為什么要說“又”呢?

歐拉

我們可以用兩個面積的差來形象地表現歐拉常數。一個面積是一系列的矩形之和,它們的寬度都是1,而高度從1到1/2,到1/3,到1/4,如此等等,一路下降。另一個面積是y = 1/x即倒數函數曲線下面的面積,即圖中的深紅色部分,數學家會告訴你,它就等于lnx。這兩個面積的差,就是圖中的藍色部分。

用面積表示歐拉常數

你會看到,在每一個矩形中,矩形的面積都大于倒數函數曲線下方的面積,但相差得越來越小。當x趨于無窮的時候,藍色部分的面積就趨于一個有限值,它等于歐拉常數。

了解了調和級數即ζ(1)的發散性質以后,讓我們回到歐拉乘積公式。在上一期中我們說過,歐拉乘積公式只在s > 1的時候成立。有同學問我,歐拉乘積公式的推導過程好像跟s完全沒有關系,那么它是不是對于任意的s都成立呢?回答是:不行,只有對大于1的s才成立。

這是因為我們的推導過程有一個前提,就是ζ(s)是一個有限值,或者說ζ(s)是收斂的。只有在這個前提下,才能把它當成一個正常的數進行種種操作,例如乘以1 – f(2),消去所有包含2n的項。但假如ζ(s)是發散的,那么這樣的操作就毫無意義,有可能導致各種各樣的錯誤。例如你經常聽說的所謂“全體自然數的和等于-1/12”,就是這樣的一個錯誤!

在歐拉那個時代,許多數學知識的基礎定義還不夠嚴格,數學家還經常搞一些有越界之嫌的操作,歐拉就搞了不少。而現代的數學家是非常注重嚴格性的,他們給你看的證明,一定都是保證了可靠性,每一步都有精確定義的。我雖然不是數學家,但我給你看的證明,也一定是保證了可靠性的。

既然ζ(1)是發散的,那么你很容易發現,當s 1的范圍內進行。從中我們確實能得到一些有趣的結論,例如s個自然數互質的概率等于1/ζ(s),但這些畢竟還是對質數分布的間接了解,直接的了解還很欠缺。

如何才能對質數的分布獲得更加深入的了解呢?

我們的大事件來了:你的好友黎曼已上線!歐拉ζ函數升級為黎曼ζ函數!

黎曼

更多袁嵐峰的文章:

中國科技實力正以多快的加速度逼近美國 | 袁嵐峰

紀念霍金:人是一根會思想的蘆葦 | 袁嵐峰

中國科技,別吹上天莫貶入地 | 袁嵐峰

中興、芯片和技術戰爭 | 科技袁人

科學讓人聽不懂嗎? | 袁嵐峰

從芯片到星辰大海 | 袁嵐峰

醫藥的邏輯 | 袁嵐峰

韓春雨撤稿一周年回顧 | 袁嵐峰

奇妙的數學:藍眼睛島和強弱共識 | 袁嵐峰

科大60周年校慶,星際迷航發來賀電 | 袁嵐峰

日本諾貝爾獎現在多于中國很正常,但未來屬于中國 | 袁嵐峰

永不消逝的信息:霍金的最后一篇論文 | 袁嵐峰

理解黎曼猜想(一)背景 | 袁嵐峰