[數論] 歐拉函數(Euler's Phi Function)

參考資料
EulerTheorem-Silverman http://palmer.wellesley.edu/~ivolic/pdf/Classes/USEM/EulerTheorem-Silverman.pdf

定義2 一個數論函數 $f(n)$, 若 $(m,n)=1$, 具有性質 $f(mn)=f(m)f(n)$, 則稱 $f(n)$ 為「積性函數(multiplicative function)」. 若不論有無 $(m,n)=1$, 上式都成立, 則稱 $f(n)$ 為「完全積性函數(complete multiplicative function)」.

例2 試證: $h_{\lambda }(n)=n^{\lambda }$($\lambda$為常數)是完全積性函數.
<pf> 設 $n=n_{1}n_{2}$, 無論 $n_{1}$ 與 $n_{2}$ 是否互質, 都有 $h_{\lambda }(n)=h_{\lambda }(n_{1}n_{2})=(n_{1}n_{2})^{\lambda }=(n_{1})^{\lambda }(n_{2})^{\lambda }=h_{\lambda }(n_{1})h_{\lambda }(n_{2})$. 由定義得知, $h(n)$ 是完全積性函數.

性質2 若積性函數 $f(n)$ 不恆等於 $0$, 則必有 $f(1)=1$.
<pf> 設 $f(n)\neq 0$. 因為 $f(n)$ 為積性函數, 所以有 $f(n)=f(n\cdot 1)=f(n)f(1)$, 從而 $f(1)=1$.

定義3 小於或等於正整數 $n$ 且與 $n$ 互質的正整數個數稱為 $n$ 的歐拉函數(Euler's function), 記為 $\varphi (n)$.

1. $\phi (1)=1$
2. 若 $n=p$ 是質數, 因為凡是小於 $p$ 的正整數均與 $p$ 互質, 故 $\varphi (p)=p-1$.
3. 若 $n=p^{k}$,$k\in \mathbb{N}$, 亦即 $n$ 是某個質數的次方. 凡是 $p$ 的倍數都不列入. 這些 $p$ 的倍數中, 最大的是 $p^{k}=p^{k-1}p$, 故總共有 $k-1$ 個 $p$ 的倍數.(例如要知道 $\varphi(27)$, 因為 $27=3^{3}$, 故有 $3$, $2\cdot 3$, $3\cdot 3...,$ $3^{2}\cdot 3$, 總共 $3^{2}$個 $3$ 的倍數.). 因此 $\phi (p^{k})=p^{k}-p^{k-1}=p^{k}(1-\frac{1}{p})$.
4. 對於一般正整數 $N$, 對 $n$ 做質因數分解, 得到 $N=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}$. 則 $\phi (N)=\phi (p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}})=\phi (p_{1}^{k_{1}})\phi (p_{2}^{k_{2}})...\phi (p_{n}^{k_{n}})$ (這裡用到了 Euler's function 是積性函數的性質, 證明在文末).

公式：$\phi (N)=N\cdot \left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )...\left ( 1-\frac{1}{p_{n}} \right )$

證明：Euler's function 是積性函數
<pf> If p and q are prime, then $\varphi (pq)=(pq-1)-(q-1)-(p-1)=pq-(p+q)+1=(p-1)(q-1)=\varphi (p)\phi (q)$.
$(q-1)$ 是 $p$ 的倍數的個數, $(p-1)$ 是 $q$ 的倍數的個數.

底下介紹一些歐拉函數的推廣.

Euler's theorem(當要對一個高次方的數取餘數)  http://en.wikipedia.org/wiki/Euler's_theorem
RSA加密演算法 http://en.wikipedia.org/wiki/Euler's_totient_function