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

　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

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

例如\varphi(8)=4，因?yàn)?,3,5,7均和8互質(zhì)。

從歐拉函數(shù)引伸出來(lái)在 環(huán)論 方面的事實(shí)和 拉格朗日定理 構(gòu)成了 歐拉定理 的證明。

φ函數(shù)的值

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

若n是 質(zhì)數(shù) p的k次 冪 ，\varphi(n)=p^a-p^{a-1}=(p-1)p^{k-1}，因?yàn)槌?i>p的 倍數(shù) 外，其他數(shù)都跟n互質(zhì)。

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

若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

與歐拉定理、費(fèi)馬小定理的關(guān)系

對(duì)任何兩個(gè)互質(zhì)的正整數(shù)a, m，m\ge2，有

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

即 歐拉定理


當(dāng)m是質(zhì)數(shù)p時(shí)，此式則為：

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

即 費(fèi)馬小定理 。