题拍拍征解题[39]（已解决）

『28914143』已知 $p$ 和 $q$ 是两个不同素数，$\varphi(x)$ 表示不超过 $x$ 且与 $x$ 互素的正整数的个数．

1、求证：$\varphi(pq)=pq\left(1-\dfrac 1p\right)\left(1-\dfrac 1q\right)$．

2、$n$ 为 $m$ 个不同素数的乘积，且 $S=\displaystyle\sum_{\substack{xy\mid n,\\ x,y\in\mathbb N^{\ast}}}\varphi(x)\cdot y$，求 $\dfrac{S}n$．

2021年8月15日，by xixiggg．

1、不超过 $pq$ 且被 $1$ 整除的正整数共 $pq$ 个，不超过 $pq$ 且被 $p$ 整除的正整数共 $q$ 个，不超过 $pq$ 且被 $q$ 整除的正整数共 $p$ 个，不超过 $pq$ 且被 $pq$ 整除的正整数共 $1$ 个，故由客斥原理知，不超过 $pq$ 且与 $pq$ 互素的正整数共 $pq-q-p+1$ 个．因此 $$\varphi(pq)=pq\left(1-\dfrac 1 p\right)\left(1-\dfrac 1 q\right).$$

2、先证 $$\forall n\in \mathbb{N}^{\ast},\quad \sum\limits_{x\in \mathbf{N}^{\ast},x\mid n}\varphi(x)=n.$$ 事实上，有 $$\begin{split}\sum\limits_{\substack{x\in \mathbb {N} ^{\ast},\\ x\mid n}}\varphi(x)&=\sum\limits_{\substack{x\in \mathbb{N}^{\ast},\\ x\mid n}} \sum\limits_{\substack{0< t \leqslant x,\\ \gcd(t,x)=1}}1\\ &=\sum\limits_{\substack{x\in \mathbb{N}^{\ast},\\ x\mid n}}\sum\limits_{\substack{0< S \leqslant n,\\ \gcd (S,n)=\frac n x}}1\\ &=\sum\limits_{0 < S \leqslant n}\sum\limits_{\substack{x\in \mathbb{N}^{\ast},\\ x\mid n,\\ \frac n x=\gcd(S,n)}}1\\ &=\sum\limits_{0 < S \leqslant n}1\\ &=n,\end{split}$$ 其中用到了 $$\begin{cases} 0 < t \leqslant x,\\ \gcd(t,x)=1,\end{cases}\iff \begin{cases} 0<\dfrac n x\cdot t\leqslant n,\\ \gcd\left(\dfrac n x\cdot t,x\right)=\dfrac n x,\end{cases}$$ 于是 $$\begin{split}S&=\sum\limits_{\substack{xy\mid n,\\ x,y\in \mathbb{N}^{\ast}}}\varphi(x)\cdot y\\ &=\sum\limits_{\substack{y\in \mathbb{N}^{\ast},\\ y\mid n}}y\sum\limits_{\substack{x\in \mathbb{N}^{\ast},\\ x\mid \frac n y}}\varphi(x)\\ &=\sum\limits_{\substack{y\in \mathbb{N}^{\ast},\\ y\mid n}}y\cdot \dfrac n y\\ &=n\cdot \sum\limits_{\substack{y\in \mathbf{N}^{\ast},\\ y\mid n}}1\\ &=n\cdot 2^m,\end{split}$$ 从而 $\dfrac S n=2^m$．