####引言#### 欧拉函数接触过一些次，但一直都没怎么弄清楚，偶然的机会又碰到，自己在纸上推导了一下，在此记录一下推导的结果。

欧拉函数通常写成 φ(m) 的形式，表示 [1, m] 中与 m 互素的数的个数。如果 m 本身为素数，那么求解比较简单，φ(m)的值为 m - 1。但对于 m 不为素数的情况就稍微复杂一点了。欧拉函数的求值在网上能搜到很多，求解也不复杂，这里再重述主要是还原一下推导过程，作为一个记录，以便以后回顾。

好吧，东扯和西拉到此为止，说具体的。对于一个数 m 我们首先将其进行因式分解。因式分解也是一个难题，目前没有十分高效的算法对其进行求解，否则很多以大数分解为困难问题的加密算法也就要被攻破了。

####分解#### 这里对因式分解暂不作讨论，我们假设已经对数 m 进行了因式分解。将数 m 可以分解为两个数 p 和 q 的乘积，且 p 和 q 是互素的（当然 p 和 q肯定都不为 1，否则另一个数就为 m 了，这样的分解就失去了意义。）如果 m 已经被因式分解，那么很容易得到 p 和 q 。根据算术基本定理 m 可以被分解 m = p1^e1 * p2^e2 * … * pn^en 的形式。那么随机去一个数 i (1 <= i < n)，令 p = p1^e1 * … * pi^ei，令 q = pi+1^(ei+1) * … * pn^en ，即为符合要求的 p 和 q。

####推导#### 得到了 p 和 q 之后，我们的思路就是希望从 φ(p) 和 φ(q) 构造得到 φ(m)， 这样求解 φ(m) 的问题就可以化解为更小的问题，用递归或者分治的方法去求解。

φ(m) 要求解的就是 [1, m]中与 m 互素的个数，那么我们可以将 [1, m] 中与 m 有公因子的数的个数求出来，然后在拿 m 减去这个值就是 φ(m) 的值了。而 [1, m] 中的数与 m 的公因子要么是 p 的因子，或者是 q 的因子。

其中是 p 的因子的个数为 (p - φ(p)) * q， 因为 p - φ(p) 是[1, p] 中与 p 不互素的数的个数，那么对于 [1, p]中任何一个与 p 不互素的数乘上 [1, q]中的任何一个数，它都与 m 至少有一个因子，且这个因子也是 p 的因子。 而且这个数肯定在 [1, m]之间。同理，(q - φ(q)) * p 是 [1, m] 中与 m 不互素且有公因子是 q 的因子的数的个数。

我们知道 [1, m] 中任何一个数与 m 的因子只有可能是 p 或者 q 的因子，但至此我们已经将 [1, m] 中所有含有 p 或者 q 的因子的数都找出来了。但还有一个问题需要考虑，那就是 (q - φ(q)) * p 中一些数既含有 p 的因子又含有 q 的因子， 同理 (p - φ(p)) * q 中也包含了既有 p 的因子又含有 q 的因子的数， 这样就产生了重复的包含，因此要减去[1, m] 中既有 p 的因子又有 q 的因子的数的个数，即 (p - φ(p)) * (q - φ(q))。

####结论#### 至此已经找出了[1, m] 中所有不与 m 互素的数的个数即为 (p - φ(p)) * q + (q - φ(q)) * p - (p - φ(p)) * (q - φ(q))，这样 φ(m) = p * q - (p - φ(p)) * q - (q - φ(q)) * p + (p - φ(p)) * (q - φ(q))。进行变换 φ(m) = (p - (p - φ(p))) * (q - (q - φ(q)))。即 φ(m) = φ(p) * φ(q)。

有了前面推导的公式 φ(m) = φ(p) * φ(q) 作基础之后，再考虑前面 m 的展开公式 m = p1^e1 * p2^e2 * … * pn^en 则 φ(m) = φ(p1^e1) * φ(p2^e2) * … φ(pn^en) 。而对于 φ(pi^ei)的值我们很好求解，即为 pi^(ei-1) * (pi - 1)。这样如果我们对 m 进行了因式分解之后，就能很容易的求解出他的欧拉函数了。