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

即 费马小定理 。