聽說在睡前打一篇數學文有益睡眠，那今天就來談談一個很特別的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用質數代進去後，就可以證明費馬小定理了。
好了，希望大家能有一個好眠的日子，我們明天見(？