欧拉函数性质证明问询：素数q整除/不整除m时φ(qm)的表达式

嘿，我来帮你把这个推导捋顺！你已经摸到门道了，只差把两种情况的核心差异拆解清楚～

先明确欧拉函数的核心定义：如果正整数$m$的素因数分解是 $m = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$，那么
$$\phi(m) = m \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$

接下来分两种情况逐一证明：

情况1：素数$q$整除$m$ #

因为$q$是整除$m$的素数，所以$q$肯定已经在$m$的素因数集合${p_1,p_2,\dots,p_k}$里了。此时$qm$的素因数分解只是把$m$中$q$的指数加1，其他素因数完全不变——比如假设$q=p_1$，那$qm = p_1^{e_1+1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$。

代入欧拉函数公式：
$$\phi(qm) = qm \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$
注意这里的乘积项和$\phi(m)$里的乘积完全一致，因为$qm$的素因数和$m$没有新增。而$\phi(m) = m \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$，替换后直接得到：
$$\phi(qm) = q \times \left(m \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)\right) = q\phi(m)$$

情况2：素数$q$不整除$m$ #

这时候$q$不在$m$的素因数集合里，所以$qm$的素因数分解是在$m$的素因数基础上新增了$q$，也就是$qm = q^1 \times p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$。

代入欧拉函数公式时，乘积项就要多乘一个$(1-\frac{1}{q})$：
$$\phi(qm) = qm \times \left(1 - \frac{1}{q}\right) \times \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$
先计算前面的系数：$q \times (1-\frac{1}{q}) = q - 1$，剩下的部分$m \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$就是$\phi(m)$，替换后得到：
$$\phi(qm) = (q-1) \times \left(m \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)\right) = (q-1)\phi(m)$$

你之前的推导其实已经摸到了第二种情况的开头，只是没明确区分“$q$是否在$m$的素因数里”这个关键前提，把这点拎出来，整个推导就顺畅啦！

内容的提问来源于stack exchange，提问作者PhysicsMathsLove