打英霸打到一半，突然斷線…只好上來八卦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個。
大概就是這樣…
如果是剛起床看到這篇又想睡的，不要罵我啊…
有機會的話，我們明天見(？