打英霸打到一半，突然断线…只好上来八卦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个。
大概就是这样…
如果是刚起床看到这篇又想睡的，不要骂我啊…
有机会的话，我们明天见(？