之前《数论基础》 一文介绍了欧拉函数，并且给出了欧拉函数的乘积公式，但是并没有给出推导过程。本文主要讲解如何一步一步推导出欧拉函数的乘积公式。

在推导之前，我们先来回顾一下欧拉函数的乘积公式。对于正整数 ，设其质因数分解为如下形式：

则 可通过如下乘积公式计算：

推导这个公式，需要用到欧拉函数的几个性质。

性质1：如果整数 ， 互质，那么 。

证明：

首先我们构造两个集合。

其中集合 里面的元素是一个二元组。例如 ，，那么集合 和 分别是：

取 中的任一元素 ，分别除以 和 求余数：

小知识："" 表示 除以 求余数。例如 。

由于 ，因此有 ，以及 。由此可以得到 ，以及 。如果把 和 组成一个二元组 ，那么这个二元组是集合 中的一个元素。

因此由集合 中任一元素 通过上述方式生成的二元组 是集合 中的一个元素。

下面我们需要证明两点：

  1. 集合 中的每个元素，都对应着 中的不同的元素。
  2. 集合 中的每个元素，在 中都有对应的元素。

先来证明第 1 点，假设集合 两个不同的元素 、 对应着集合 中的同一个二元组 。那么有

根据同余性质有：，以及 。 又因为 ，所以有：。

根据集合 的定义，其中所有的元素都小于 。因此只有当 时，才能满足 。这与 的假设相矛盾。

因此可以证明: 集合 中的每个元素，都对应着 中的不同的元素。

下面我们来证明第 2 点。

任取集合 中的一个元素 。找到一个数 , 模 与 同余，模 与 同余。写成同余方程组如下所示。

由于 ，根据中国剩余定理，该方程组有解，且在小于 的范围内只有一个解。由于 ， ，根据同余关系有 ， ，因此有 。因此方程的解 一定是集合 中的一个元素。

因此可以证明: 集合 中的每个元素，在 中都有对应的元素。

通过上述证明，可以知道集合 与集合 的元素个数相同。根据上诉集合的定义，集合 的元素个数为 ，集合 的元素个数为 。因此我们就证明了 。

通过这个性质可以看出欧拉函数是一个乘性函数（Multiplicative Function）。可以扩展这个性质到更一般的场景，假设有 个两两互质的数：，那么有。

性质2：设 是质数，则 。

证明：

小于等于 且与 不互质的数一定是 的倍数，他们是

一共有 个。因此小于 且与 互质的数的个数，也就是 。

根据前面这两个性质，我们就可以推导欧拉函数的乘积公式了。假设整数 的质因数分解为如下形式

根据上面两个性质可得

由此我们得到了欧拉函数的乘积公式。为了计算方便，我们通常使用下列两种形式的乘积公式：

或者

可以看出，要计算 的值，必须对 做质因数分解。当 含有特别大的质因数时，分解 将会十分困难，此时求解 也会十分困难。RSA 密码正是利用了 的这一性质，从而十分安全。

参考文献
[1] Multiplicative Function：https://en.wikipedia.org/wiki/Multiplicative_function
[2] 数论概论（原书第4版），约瑟夫H.西尔弗曼: https://book.douban.com/subject/26863822/