作者jayfrog (寫不出coding)
看板Gossiping
標題Re: [問卦] 質數到底有什麼用？
時間Wed Mar 11 01:24:28 2015
聽說在睡前打一篇數學文有益睡眠，那今天就來談談一個很特別的function叫：
φ-function
φ-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。
為什麼要談到這個呢？
想必大家應該都有聽過費馬小定理吧，其實有一個定理長得跟費馬小定理很像，
叫做Euler-theorem。
費馬小定理是長成這樣：if p is a prime,then a^(p-1) ≡ 1 (mod p) as gcd(a,p)=1.
而Euler-theorem 則是這樣：if n>0 and gcd(a,n)=1, then a^(φ(n)) ≡1 (mod n)
是不是長得很像呢？
(注：在這先說明一下符號的意思好了，所謂的gcd(a,p) 就是指a跟p的最大公因數，
這個我想大家的問題應該不大。比較大的是應該是 a ≡ 1 (mod p) 這個符號。
上面的符號是說 a除以p會餘1的意思，用數學式寫的話就是這樣：a ÷ p = Q.....1
舉個例子大概是 37÷5=7....2，所以就可以寫成 37 ≡ 2 (mod 5) )
而眼尖的人應該發現了 如果p是質數的話，那φ(p)=p-1。
所以說Euler-theorem算是費馬小定理推廣。
而Euler-theorem的證明也沒有很難就是了。
若給一大於0的正整數n，由φ(n)的定義可得知，有φ(n)個比n小的正整數與n互質
令這些數為：a_1, a_2,...,a_φ(n)。
若給定一個a 並且 gcd (a,n)=1
那下列的結果： a*a_1 ≡ b_1 (mod n)
a*a_2 ≡ b_2 (mod n)
.
.
.
a*a_φ(n) ≡ b_φ(n) (mod n)
然後將上面的式子全部乘起來就會得到
a^(φ(n))(a_1*a_2*....*a_φ(n)) ≡ b_1*b_2*...*b_φ(n) (mod n)
因為比n小並且跟n互質的數是固定的，所以任給a_i 一定會跟某一個 b_j一樣
並且這些數都跟n互質，所以我們可以直接約掉。
之後就可以得到 a^(φ(n)) ≡ 1 (mod n) 這個結果了。
然後把n用質數代進去後，就可以證明費馬小定理了。
好了，希望大家能有一個好眠的日子，我們明天見(？
--
「台灣 + 中國 = 經濟肯定會成長。我發現了一個非常漂亮的證明，
但 4 年實在太短，沒有足夠的時間容我來證明它。」
轉自 <廢馬大定理>-民明書坊
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.199.231
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1426008272.A.65A.html
※ 編輯: jayfrog (118.160.199.231), 03/11/2015 01:26:39
→ krishuang: 又有好文可以看了 03/11 01:26
→ qq251988: 感謝助眠 03/11 01:26
推 azzc1031: 推 03/11 01:27
推 ggBird: 躺在床上看這篇，睡不著了 03/11 01:28
推 gy0178: 頭皮發麻 03/11 01:29
推 peterscaa: 糟糕 興致來了 03/11 01:30
推 jyekid: 廢小馬定理當初怎麼發現的 好屌 03/11 01:33
→ ma4wanderer: 你少說bj不會重複吧？ 03/11 01:36
其實要證明的是{a_1,a_2....,a_φ(n)}={b_1,b_2,....,b_φ(n)}
不過這個有一點麻煩就是了，所以就跳過了。
推 waloloo: 我睡著了 03/11 01:38
推 krishuang: 有mod n在不是嗎？ 03/11 01:39
→ ma4wanderer: 就不失一般性假設b1=b2 兩式相減就有矛盾了 03/11 01:41
任給a_i 一定會跟某一個 b_j一樣
其實這句話就直接說b_j不重復了，因為a_i不重復
但問題是這句話其實沒有那麼直觀就是了。
推 rainfarmer: 深夜好文 比仇肥宅文有深度多了 03/11 01:58
推 daniel54088: 嗯嗯跟我想的一樣 03/11 02:01
→ ma4wanderer: 我就是說那句 要用我那句去證... 03/11 02:22
→ ma4wanderer: 你說我那句是你那句的結果 根本因果倒置= = 03/11 02:22
任給a_i 一定會跟某一個 b_j一樣
這句話除了要證明 b_j不重復外，還要證明b_j落在這S={a_1,...,a_φ(n)}裡
而證明是 gcd(b_j,n)=gcd(a*a_j,n)=1 ，所以b_j 一定屬於S
又因為b_j們不重復，並且集合個數相同，
所以{a_1,a_2....,a_φ(n)}={b_1,b_2,....,b_φ(n)}
這樣就有辦法得到 任給一個a_i 一定會跟某一個 b_j一樣
如果要說明這句話是對的，大概還要寫一下上述的證明
當初在寫的時候覺得太麻煩，所以就跳過不寫(最後還是寫了…)
造成大家的困擾，請多多見諒！
※ 編輯: jayfrog (118.160.199.231), 03/11/2015 05:16:49