任意兩正整數互質的概率

2021-02-23 愛數學之家

今天看到一道比較有意思的題目，給大家分享一下.

題目：從全體正整數中隨機選出兩個正整數，則下面哪種情況的可能性更大一些？

A．這兩個正整數互質（沒有大於 1 的公約數）
B．這兩個正整數不互質（有大於 1 的公約數）
C．上述兩種情況的出現概率相同

答案：

這個問題的說法很不嚴謹。我們給出一個更加嚴謹的敘述方法。讓我們用 PN 來表示，從 1 到 N 中隨機取出兩個正整數，它們互質的概率是多少。我們的問題就是，當 N 趨於無窮時， PN 的值究竟是大於 1/2 ，等於 1/2 ，還是小於 1/2 。

這是一個非常非常經典的問題。下面是最常見的一種解法。假設我們從全體正整數中隨機選出了兩個正整數 a 、 b 。其中， a 能被 2 整除的概率是 1/2 ， b 能被 2 整除的概率是 1/2 。因而，它們都能被 2 整除的概率就是 1 / 22 。反過來，它們不都能被 2 整除的概率就是 1 – 1 / 22 。類似地，它們不都能被 3 整除的概率就是 1 – 1 / 32 ，它們不都能被 5 整除的概率就是 1 – 1 / 52 ……於是，它們互質的概率就是：

(1 – 1 / 22) · (1 – 1 / 32) · (1 – 1 / 52) · (1 – 1 / 72) …

注意，這裡用到了一個假設：如果 p 和 q 是兩個質數，那麼能否被 p 整除和能否被 q 整除，這是互相獨立的。事實上也確實如此：一個數能被 p 整除的概率是 1 / p ，一個數能被 q 整除的概率是 1 / q ；一個數能同時被兩個質數 p 和 q 整除，若且唯若它能被 p · q 整除，其概率是 1 / (p · q)。

為了求出上面這個式子的值，我們考慮它的倒數。1 – 1 / 22 的倒數是 1 / (1 – 1 / 22) ，而由無窮等比級數的求和公式，它又可以被我們寫成 1 + 1 / 22 + 1 / 24 + 1 / 26 + … 。類似地，其他幾項也都變成了 1 + 1 / 32 + 1 / 34 + 1 / 36 + … ，1 + 1 / 52 + 1 / 54 + 1 / 56 + … ，等等。現在，想像一下，如果把所有的括號全都展開，把所有的項全都乘開來，會得到什麼？我們會既無遺漏又無重複地得到所有的 1 / n2 ！

  (1 + 1 / 22 + 1 / 24 + 1 / 26 + … ) · (1 + 1 / 32 + 1 / 34 + 1 / 36 + … )
  · (1 + 1 / 52 + 1 / 54 + 1 / 56 + … ) · …
= 1 + 1 / 22 + 1 / 32 + 1 / 42 + 1 / 52 + …

比方說， 40 = 2 × 2 × 2 × 5 ，那麼等式右邊的 1 / 402 這一項，就是由等式左邊的第一個括號裡的 1 / 26 ，乘以第二個括號裡的 1 ，乘以第三個括號裡的 1 / 52 ，乘以其餘所有括號裡的 1 得到的。

1 + 1 / 22 + 1 / 32 + 1 / 42 + 1 / 52 + … 究竟等於多少呢？我們來證明，它小於 2 。這是因為：

  1 + 1 / 22 + 1 / 32 + 1 / 42 + 1 / 52 + …
< 1 + 1 / (1 × 2) + 1 / (2 × 3) + 1 / (3 × 4) + 1 / (4 × 5) + …
= 1 + 1 – 1/2 + 1/2 – 1/3 + 1/3 – 1/4 + 1/4 – 1/5 + …
= 2

別忘了， 1 + 1 / 22 + 1 / 32 + 1 / 42 + 1 / 52 + … 是我們把所求的概率值取了倒數後的結果。因此，我們所求的概率值就應該大於 1/2 了。也就是說，這道題目的正確答案是 A 。

可以證明， 1 + 1 / 22 + 1 / 32 + 1 / 42 + 1 / 52 + … 實際上等於 π2 / 6 。因此，任意兩個正整數互質的概率就是 6 / π2 ≈ 0.608 。神奇的數學常數 π 經常會出現在一些與圓形八竿子打不著的地方，比如我們之前提過的 Buffon 投針問題。而大家剛才看到互質概率問題，才是我覺得最為經典的例子之一。

*本文摘自matrix67.

----

歡迎關注愛數學之家

相關焦點

  • 理解黎曼猜想(二)兩個自然數互質的概率是多少? | 袁嵐峰
    而ζ(2) = π^2/6，因此這個概率等於6/π^2 ≈ 60.79%。同樣的，三個自然數互質的概率是1/ζ(3) ≈ 83.19%，四個自然數互質的概率是1/ζ(4) ≈ 92.39%。很快可以看出，任意兩個不同的質數是互質的，一個質數和一個不以它作為質因數的合數是互質的，1和任意自然數都是互質的。了解了互質的定義之後，我們如何計算兩個自然數互質的概率呢？可以這樣思考。首先，考慮兩個自然數有公約數2的概率。這等價於它們都可以表示成2n，而所有可以表示成2n的自然數在所有的自然數當中佔據的比例是1/2。
  • 長沙小升初數學必背基礎知識:互質數
    【對於多個數來看（教材定義）】 若干個最大公因數只有1的正整數，叫做互質數。 　　表達及運用注意 　　（1）這裡所說的「兩個數」是指除0外的所有自然數。 　 　　（2）「公因數只有 1」，不能誤說成「沒有公因數。」
  • 石家莊小學1-6年級數學基礎概念:互質數
    石家莊小學1-6年級數學基礎概念：互質數 　　什麼叫互質數？ 　　定義及定理：對於兩個數來看 ，公因數只有1的兩個數，叫做互質數。對於多個數來看（教材定義） 若干個最大公因數只有1的正整數，叫做互質數。
  • 互質的秘密
    互質是正整數間的關係，兩個數互質意味著這兩個數沒有1以外的公因數，比如3和4、11和15、41和43等。今天我們舉個例子，研究一下互質在現實生活中的作用。為了讓齒輪系統穩定耐用，相互嚙合的大齒輪、小齒輪的齒數最好要互質。有人會有這樣的問題，如果不互質，齒輪就不轉了？轉肯定是可以轉，只是更容易出問題，特別是齒輪材質不均勻的時候。我們舉個例子。
  • 正整數的性質 C7,D1
    設 n 為大於 2 的正整數,證明:在 1,2,…,n 中,與 n 互質的數的立方和能被 n 整除.解: 設 a<n,且 (a,n)=1,則 n-a<n,且 (n-a,n)=1.而且 a=n-a,導出 a=n/2,僅在n為偶數時發生,而這時 a 與 n 不互質.
  • 小學1-6年級數學基礎概念:公約數、公倍數、互質數
    小學1-6年級數學基礎概念：公約數、公倍數、互質數 　　什麼叫公約數？ 　　公約數，亦稱「公因數」。它是幾個整數同時均能整除的整數。如果一個整數同時是幾個整數的約數，稱這個整數為它們的「公約數」；公約數中最大的稱為最大公約數。
  • 正整數的性質 C6
    若一個質數的各位數碼經任意排列後仍然是質數,則稱它是一個絕對質數 例如:2,3,5,7,11,13(31),17(71),37(73),79(97),113(131,311),199(919,991),337(373,733),…都是絕對質數.
  • 五年級數學下冊,質數與互質數兩個概念分不清,影響後面的學習
    二、互質數，即兩個或多個整數的公因數只有1的非零自然數。公因數只有1的兩個非零自然數，叫做互質數。a.判斷兩個數是不是為互質數，只要判斷她們是不是只有1這一個公因數就行了。b.1和任何一個非零的自然數都是互質數。c.2和任意奇數，都是互質數。d.任意兩個相鄰的非零自然數都是互質數。e.
  • 正整數的性質 A6
    因為 a 為整數,所以 a=2.於是 x=1250×(208-71×2)=82500.所以,小明家原來的電話號碼為 282500.26. 求證:對 i=1,2,3,均有無窮多個正整數 n,使得n,n+2,n+28中恰有 i 個可表示為三個正整數的立方和.
  • 正整數的性質 D6
    如果正整數 a、b、c 滿足 c²=a²+b².證明:數 c²+ab 和 c²-ab 都可以表示為兩個正整數的平方和.解: 巧妙運用下述命題:如果正整數 x 可表示為兩個正整數的平方和,則 2x 也可表示為兩個整數的平方和.事實上,設x=u²+v²,這裡 x、u、v 都是正整數.
  • 正整數的性質 C3
    證明:毎一個大於 11 的整數都是兩個合數的和.解: 設 n 是大於 11 的整數.若 n 為正整數,n+3 與 n+7 都是質數.求 n 除以 3 所得的餘數.解: 我們知道,n 除以 3 所得的餘數只可能為 0、1、2 三種.若餘數為 0,即 n=3k (k 是一個非負整數,下同),則 n+3=3k+3=3(k+1),所以 3|n+3.
  • 正整數的性質 D4
    設 p 是質數,且 p4 的全部正約數之和是一個平方數,求 p.解: 因為 p 是質數,所以 p4 有 5 個正約數1、p、p²、p³、p4.)²<(2n)²<(2p²+p+2)²由於 2p²+p,2n, 2p²+p+2 均為正整數.
  • 「EJU數學A」整數的性質2
    EJU數學A-整數的性質上期回顧：（1）平方根是自然數的條件。（2）因數的個數，因數的總和。（3）最大公因數，最小公倍數，互質。（000……這樣連續的0有多少個）（2）互質的證明。（2）互質的證明。基礎題：證明：對於兩個自然數a，b來說，[如果a與b互質]，那麼[a+b與ab互質]Point：直接證明比較難以證明時，善用反證法。
  • 正整數的性質 A2
    6.求證:3n+1 (n 為正整數)能被 2 或 2² 整除,但不能被 2 的更高次冪整除.解: 按模 2 分類.若 n=2k 為偶數,k 為正整數,則 3n+1=32k+1=(3k)²+1.7.設 p 是質數,證明:滿足 a²=pb² 的正整數 a、b 不存在.解: 用反證法.假定存在正整數 a、b,使得 a²=pb².令 (a,b)=d,a=a1d,b=b1d,則 (a1,b1)=1.
  • Python如何判斷一個正整數是否是素數?
    於是，我們可以通過枚舉小於該數，並且大於1的整數，來判斷該數是否是素數。假設有一個正整數a，則其可以被寫成任意兩個正整數之積，即a = p * q。假設p < q，那么正整數p和q都是a的約數。注意到，如果我們知道p是a的約數，那麼可以通過q = a / p快速求得另外一個約數q。同樣的道理，如果某個數p不是a的約數，那麼q也不是a的約數。
  • 正整數的性質 D7
    —個正整數若能表示為兩個正整數的平方差,稱為「智慧數」,比如 16=5²-3²,16 就是一個「智慧數」,從 1 開始數起,第 2008 個「智慧數」是哪個數?解: 1 不是「智慧數」,大於 1 的奇正整數2k+1=(k+1)²-k²(k=1,2,3,…),都是「智慧數」.
  • 如何快速地判斷一個整數是不是質數,這種簡便方法必須掌握
    正整數則可根據因數個數來劃分，可分為1、質數與合數。我們說如果一個正整數只有1和它本身是兩個正因數，那麼這樣的數就稱之為質數。質數也叫做素數，可以說它是數字的根源。如果沒有質數，或許就沒有數論什麼事了。如果用字母表示：a=1×a。(a為大於1的自然數）。