歐拉函數(shù)的定義:E(k)=([1,n-1]中與n互質(zhì)的整數(shù)個數(shù)).
???
???? 由于隨意正整數(shù)都能夠唯一表示成例如以下形式:
???????????????????? k=p1^a1*p2^a2*……*pi^ai;(即分解質(zhì)因數(shù)形式)
??? 能夠推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
?????????????? =k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
?????????????? =k*(1-1/p1)*(1-1/p2)....(1-1/pk)
???? ps：在程序中利用歐拉函數(shù)例如以下性質(zhì)，能夠高速求出歐拉函數(shù)的值(a為N的質(zhì)因素)
若(N%a==0 && (N/a)%a==0) 則有:E(N)=E(N/a)*a;

若(N%a==0 && (N/a)%a!=0) 則有:E(N)=E(N/a)*(a-1);

http://hi.baidu.com/ldante/blog/item/996b0ea131a7a58f46106443.html

第一次寫歐拉函數(shù)的題，琢磨的半天，最后還是僅僅能依照最開始的想法寫......
歐拉函數(shù)PHI(n)表示的是比n小，而且與n互質(zhì)的正整數(shù)的個數(shù)(包含1)。比方：
PHI(1) = 1; PHI(2) = 1; PHI(3) = 2; PHI(4) = 2; ... PHI(9) = 6; ...

要計算一個正整數(shù)n的歐拉函數(shù)的方法例如以下：
1. 將n表示成素數(shù)的乘積: n = p1 ^ k1 * p2 ^ k2 * ... * pn ^ kn（這里p1, p2, ..., pn是素數(shù)）
2. PHI(n) = (p1 ^ k1 - p1 ^ (k1 - 1)) * (p2 ^ k2 - p2 ^ (k2 - 1)) * ... * (pn ^ kn - pn ^ (kn - 1))
????????????? = Mult { pi ^ ki - pi ^ (ki -1) }

證明步驟例如以下：
1. easy想到：當n為素數(shù)時，PHI(n) = n - 1。由于每一個比n小的正整數(shù)都和n互素。當n為素數(shù)p的k次方時，PHI(n) = p ^ k - p ^ (k - 1)。由于在1到n之間的正整數(shù)僅僅有p的倍數(shù)和n不互素，這種數(shù)有(p ^ k / p)個。
2. 假設(shè)m和n互素，即GCD(m, n) = 1，那么PHI(m * n) = PHI(m) * PHI(n)。用中國剩余定理能夠證明，證明的思路是建立這樣一種一一相應(yīng)的關(guān)系(a, b) <-> x，當中正整數(shù)a小于m而且gcd(a, m) = 1，正整數(shù)b小于n而且gcd(b, n) = 1，正整數(shù)x小于m*n而且gcd(m*n, x) = 1。證明步驟例如以下：
??? 1)依據(jù)中國剩余定理，假設(shè)m和n互素，那么關(guān)于未知量x的方程組x % m = a, x % n = b(0 <= a < m, 0 <= b < n)，當0 <= x < m * n時存在而且僅存在一個解。easy證明，假設(shè)兩個這種方程組有同樣的m, n可是a, b不同，那么他們的解x一定不同。
??? 2)首先用反正法證明：gcd(m, a) = 1且gcd(n, b) = 1是gcd(m*n, x) = 1的必要條件：如果gcd(a, m) = k > 1，由此可得：a = a' * k; m = m' * k => x = k' * m + a = k' * k * m' + k * a' = k * (k' * m' + a'); 所以gcd(x, m) = k > 1。同理可證，如果gcd(b, n) > 1， 那么gcd(x, n) > 1。所以x和m * n互素的必要條件是a和m互訴且b和n互素。
??? 3)接下來我們證明充分性：由x % m = a 能夠得到x = k * m + a；由歐幾里德算法求最大公約數(shù)的過程（就不證明了，呵呵，還得想）能夠知道gcd(x, m) = gcd(m, a) = 1；同理可得，假設(shè)gcd(n, b) = 1那么gcd(x, n) = 1。接下來非常easy得到：gcd(m*n, x) = 1。從而證明了充分性。
??? 4)上面三步的結(jié)論表明，數(shù)對(a, b)是能夠和x建立起一一相應(yīng)的關(guān)系的，所以有多少個不同的(a, b)，就有多少個不同的x。
3.將n分解成素數(shù)乘積后，顯然對于隨意的i, j(i != j)都滿足 pi ^ ki和pj ^ kj是互素的，于是能夠的到上面的公式。

跟據(jù)上面的公式，能夠得到關(guān)于歐拉函數(shù)的遞推關(guān)系：
如果素數(shù)p能整除n，那么
假設(shè)p還能整除n / p, PHI(n) = PHI(n / p) * p;
假設(shè)p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);