听说在睡前打一篇数学文有益睡眠，那今天就来谈谈一个很特别的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用质数代进去后，就可以证明费马小定理了。
好了，希望大家能有一个好眠的日子，我们明天见(？