pku題目：
?? http://acm.pku.edu.cn/JudgeOnline/problem?id=2407
?
參考網站：

　http://www.cnblogs.com/softbird/archive/2005/12/01/288649.html

　http://www.wikilib.com/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

在 數論 ，對正 整數 n，歐拉函數\varphi(n)是少于或等于n的數中與n 互質 的數的數目。此 函數 以其首名研究者 歐拉 命名，它又稱為Euler's totient function、 φ 函數、歐拉商數等。

例如\varphi(8)=4，因為1,3,5,7均和8互質。

從歐拉函數引伸出來在 環論 方面的事實和 拉格朗日定理 構成了 歐拉定理 的證明。

φ函數的值

\varphi(1)=1（唯一和1互質的數就是1本身）。

若n是 質數 p的k次 冪 ，\varphi(n)=p^a-p^{a-1}=(p-1)p^{k-1}，因為除了p的 倍數 外，其他數都跟n互質。

歐拉函數是 積性函數 ——若m,n互質，\varphi(mn)=\varphi(m)\varphi(n)。證明：設A, B, C是跟m, n, mn互質的數的集，據 中國剩余定理 ，A \times B和C可建立 一一對應 的關系。因此\varphi(n)的值使用 算術基本定理 便知，

若n = \prod_{p\mid n} p^{\alpha_p}，
則\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac{1}{p}\right)。

例如\varphi(72)=\varphi(2^3\times3^2)=2^{3-1}(2-1)\times3^{2-1}(3-1)=2^2\times1\times3\times2=24

與歐拉定理、費馬小定理的關系

對任何兩個互質的正整數a, m，m\ge2，有

a^{\varphi(m)} \equiv 1 \pmod m

即 歐拉定理


當m是質數p時，此式則為：

a^{p-1} \equiv 1 \pmod p

即 費馬小定理 。