作者jayfrog (寫不出coding)
看板Gossiping
標題Re: [問卦] 質數到底有什麼用？
時間Thu Mar 12 05:51:07 2015
打英霸打到一半，突然斷線…只好上來八卦PO PO 廢文 洗洗睡了
前情提要：
: φ-function 的定義方式很特別：給一個整數n>0，而所謂的φ(n)是指比n小並跟與n
: 互質的數的個數。
: 相信應該有人看不太懂這個定義，來個例子應該可以讓大家比較好了解。
: 例：φ(30)=8。寫成這樣有沒有比較好懂呢？(誤
: 比30小並且跟30互質的正整數分別有：1,7,11,13,17,19,23,29 剛好是8個數
: 所以φ(30)=8。
: 我們再來看下一個例子：φ(9)=6。
: 因為比9小並且跟9互質的正整數分別是：1,2,4,5,7,8 剛好是6個數，所以φ(9)=6。
如果今天突然有人拿槍叫你算φ(360)時，你會怎麼算呢？
http://blog.udn.com/TatumSpace/21430104 像這篇一樣…
如果單從定義來看的話，就是在1~360裡找出跟360互質的數，那就是答案了…
但，這會不會太慢了啊…
台灣的數學教育最喜歡的就是教公式了，而剛好φ(n)也有公式，
那就是 如果n=p_1^(k_1)*p_2^(k_2)*....*p_r^(k_r) ,where p_i is a prime for all i
那φ(n)=n*(1-(1/p_1))*(1-(1/p_2))*...*(1-(1/p_r))
看起來好像很可怕，但是如果知道這個公式是怎麼來的就應該還好。
一開始就直接找φ(n)的公式好像有一點太難了，那我們就從簡單一點開始吧
那就先算一下φ(p^k)的值，而這裡的p是個質數。
那φ(p^k)到底是多少呢？
因為p是個質數，所以比p^k小又跟p^k"不"互質的數，只有
p, 2p, 3p, 4p,...., p^k，而剛好p^k=p^(k-1)*p, 所以可以知道比p^k小又不跟p^k互質
的數有p^(k-1)個。很容易的，就可以得知跟比p^k小又跟p^k互質的數有p^k-p^(k-1)個
也因此φ(p^k)=p^k-p^(k-1)=p^k(1-(1/p))
為什麼會想先算φ(p^k)呢？
那是因為在數學上有一個很有用的東西叫質因數分解。
你任給一個整數n，我們都可以把他寫成n=p_1^(k_1)*p_2^(k_2)*....*p_r^(k_r)
where p_i is a prime for all i 這個型式。
那我們有了φ(p^k)的值後，我們只要再證明φ(mn)=φ(m)φ(n) ,where gcd(m,n)=1.
就可以很輕易的導出前面式子了。
那要怎麼樣才能得到φ(mn)=φ(m)φ(n)這個結果呢？我們先看個圖吧。
第一行 第二行 第三行 ..... 第m行
1 2 3 ..... m
m+1 m+2 m+3 ..... 2m
.
.
.
(n-1)m+1 (n-1)m+2 (n-1)m+3 ..... nm
這是將mn個數字擺成成m*n的方格狀。
從這個圖很容易可以知道j跟m不互質的話，那第j行所有的數都跟m不互質。
為什麼會這樣呢？因為第j行所有的數，都可以寫成km+j的型式。
那 km+j ≡ j (mod m) 的原因，所以我們可以得到這樣的結果。
所以說，如果gcd(j,m)=1，那些比mn小又跟mn互質的數，一定藏在第j行裡。
而從φ-function的定義來看，我們知道會有φ(m)行的數是跟m互質的。
那先把第j行所有的數字抓出來看好了。
j, m+j, 2m+j,...,(n-1)m+j
這些是第j行所有數字長的樣子，而這裡很明顯有n個數字。
因為這些數很明顯跟m是互質的，所以如果從這些數中找到跟mn互質的話，
那就只要考慮這些數跟n會不會互質？
在這裡我們先考慮 如果 km+j ≡ tm+j (mod n) 這件事。
如果還記得mod的定義的話，我們就可以把式子簡化成 km ≡ tm (mod n)這個樣子
又因為m跟n互質，所以我們可以再把式子簡化成 k ≡ t (mod n)。
所以跟如果k跟t都比n小的話，那k跟t一定是同一個數字。
也因此我們可以知道第j行的所有數字 mod n 都是不同的結果，
又因為他們只有n個數字，所以這些結果就剛好是0, 1, 2, 3, ..., n-1
而在這些數字中跟n互質的數有φ(n)個。
因此從上面就可以知道比mn小且跟mn互質的數會有φ(m)φ(n)個。
因為我們有這個跟上面φ(p^k)的結果，我們就可以將兩個合併。
因此 如果n=p_1^(k_1)*p_2^(k_2)*....*p_r^(k_r) ,where p_i is a prime for all i
那φ(n)=n*(1-(1/p_1))*(1-(1/p_2))*...*(1-(1/p_r))
那就讓我們回到最一開始要算的φ(360)吧
因為360=2^3*3^2*5，所以φ(360)=360*(1-1/2)*(1-1/3)*(1-1/5)=96
其實，這個公式也有一個比較直覺的說法。
一樣拿360來說好了。因為360有2這個因數，所以只要是2的倍數就不要，那就剩180個。
360也有3這個因數，因此在只要是3的倍數也不要，那大概會佔總數2/3個，所以剩120個
同理，360也有5這個因數，也不要5的倍數，那也是佔總數的4/5個，所以就是96個。
大概就是這樣…
如果是剛起床看到這篇又想睡的，不要罵我啊…
有機會的話，我們明天見(？
--
「台灣 + 中國 = 經濟肯定會成長。我發現了一個非常漂亮的證明，
但 4 年實在太短，沒有足夠的時間容我來證明它。」
轉自 <廢馬大定理>-民明書坊
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.169.38.128
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1426110671.A.71F.html
推 aynmeow: ヽ( ・∀・)ノ快推 我是真的看不懂 03/12 05:53
推 Hateson: 恩恩 跟我想得差不多 03/12 05:55
推 TreeYellow: 哩洗勒公........蝦毀？ 03/12 05:56
推 netstat: 所以求出小於自己且互質的數字有幾個要做啥 03/12 05:57
推 SamuelLuo: 看不懂內文，卻完全懂廢馬大定理XDDDDDD 03/12 05:58
推 jackboy772: 嗯嗯 跟我想得一樣 03/12 05:59
推 shlee: 蛤？ 看不懂啦幹... 03/12 06:01
推 kyle1341: 講中文好嗎 03/12 06:05
→ HELLDIVER: 突然有頭痛der感覺 03/12 06:08
→ jojoStar: 我會把他的槍搶過來 比較有用 03/12 06:13
推 feit: 喔 對啊 我也是這麼想的 03/12 06:16
推 harry2258: 離散有教的樣子 03/12 06:37
噓 cpper: 所以質數有什麼用? 03/12 06:44
推 wolver: 我會先想要怎麼奪槍反殺…… 03/12 07:08
噓 Zerachiel: 如果花那麼多字還講不出有用在哪, 不但廢文加沒用 03/12 07:09
推 kisho1106: 我有點暈(扶額) 03/12 07:25
噓 f26805234: 講簡單一點好嗎？pp而且質數你還是沒說有什麼用阿 03/12 07:31
推 redsa12: 很棒的分享 台灣就是太多只在乎東西有沒有用的人了 03/12 07:33
推 vespar: 你還是說中文吧… 03/12 07:41
推 alladult: 質數有什麼用就像打籃球有什麼用一樣 03/12 08:03
推 wl00725348: 裡了一大早的專業什麼啦 剛睡醒完全看不下去== 03/12 08:08
推 baby850811: xDD 質數可以運用到生活的哪個地方R ? 03/12 08:12
推 reich3: 寫這麼多公式,其實可以用數字舉例 03/12 08:18
推 slycsboy: 你是來騙P幣的吧 03/12 08:25
推 gn00063172: 要看這能幹嘛，可以去看前面阿。都快要成為完整一章了 03/12 08:28
噓 synke7123: 還是不懂質數有啥用 03/12 08:33
→ kevin82: 可用laplace解否?? 03/12 08:42
推 holyspectral: 好睏啊、你害我....zzzz 03/12 08:54
推 qtgary: 嗯…跟我想的一樣…zzzzz 03/12 09:03
推 asdiy: 就單維的空間相減 03/12 09:36
推 summerleaves: 跟我想得差不多。 樓下快推啊 03/12 10:10
推 erodora: 目光不要太短淺 這明明超有用 許多加密解密都是利用質數 03/12 10:30
推 mmes: 嗯嗯 差不多就醬 03/12 10:32
推 Hatred: 推 03/12 17:33