做具体数学习题看到的生草式子（

前置定义

$\varphi(n)$ ：$1\sim n$ 中与 $n$ 互质的数的个数，即 $\sum_{i=1}^n[\gcd(i,n)=1]$

$\pi(n)$ : $1\sim n$ 中的质数个数。

$\{x\}$ ：取 $x$ 的小数（分数）部分，即 $x\bmod 1$ .

$\lfloor x\rfloor,\lceil x\rceil $ ：下取整和上取整。

题目

当 $n$ 是正整数时，证明恒等式：
$$ \sum_{1\leq k<n}\Big\lfloor \frac{\varphi(k+1)}{k}\Big\rfloor =\sum_{1<m\leq n}\Big\lfloor \Big(\sum_{1\leq k<m}\lfloor (m/k)/\lceil m/k\rceil \rfloor\Big)^{-1}\Big\rfloor =n-1-\sum_{k=1}^n\Big\lceil \Big\{\frac{(k-1)!+1}{k}\Big\}\Big\rceil. $$
其实这个式子看上去有毒，但是显然得很（

引理

威尔逊定理：

$$ (n-1)!\equiv -1(\bmod n)\iff n>1,n\in primes $$

Proof

如果 $n>1$ 且并非质数，那么显然不成立；（证明的话，$n$ 不是质数，所以一定有一个 $\leq \sqrt n$ 的因子，这里取最小的不是 $1$ 的因子。如果 $<\sqrt n$ 显然可以用 $1\sim n-1$ 组合出 $n$ ，如果等于，那么对于 $\sqrt n>2$ ，$\sqrt n\cdot 2<n$ ，一定能取出另一个 $\sqrt n$ 因子；对于 $\sqrt n=2$ ，特殊处理即可。 ）

对于另一部分，考虑使用逆元来解决它。

显然，（在模意义下）如果数 $x$ 的逆元是 $y$ ，那么 $x,y$ 一定互为逆元。

所以唯一要做的就是确定哪些数的逆元是它本身，也就是求解同余方程：
$$ x^2\equiv 1(\bmod p) $$
当 $p>2$ 时，可以做如下变换：
$$ (x+1)(x-1)\equiv 0(\bmod p) $$
所以方程有且仅有两个根：$x=p-1,x=1$ .

而如果 $p=2$ ，那么显然有 $(p-1)!\equiv-1$ .

从而其他数都可以两两配对。因此，$(p-1)!\equiv 1\times (p-1)\equiv -1(\bmod p)$ .

证明

先把式子抄一遍：
$$ \sum_{1\leq k<n}\Big\lfloor \frac{\varphi(k+1)}{k}\Big\rfloor =\sum_{1<m\leq n}\Big\lfloor \Big(\sum_{1\leq k<m}\lfloor (m/k)/\lceil m/k\rceil \rfloor\Big)^{-1}\Big\rfloor =n-1-\sum_{k=1}^n\Big\lceil \Big\{\frac{(k-1)!+1}{k}\Big\}\Big\rceil. $$
考虑逐个击破，对于第一个式子，显然 $\varphi(k+1)$ 最大是 $k$ ，当且仅当 $k+1$ 是质数时第一个式子才为 $1$ ，那么就相当于 $\pi(n)$ .

对于第二个式子，中间那个 $\lfloor (m/k)/\lceil m/k\rceil \rfloor$ 只有在 $k|m$ 的时候为 $1$ ，其余为 $0$ ，那么前两个式子简化为：

$$ \pi(n) =\sum_{1<m\leq n}\Big\lfloor \Big(\sum_{1\leq k<m}[k|m]\Big)^{-1}\Big\rfloor $$

对于某个数的真因数（暂且这么叫吧，反正就是排除 $n$ ）倒数然后下取整，当且仅当个数为 $1$ 的时候才 $>0$ （ $=1$ ），也就是说 $m$ 必须是个质数。那么第二个式子就是 $\pi(n)$ ，等价了。

现在来看第三个式子。根据约定，$\{\}$ 是取分数部分，只有在 $(k-1)!\bmod k=-1$ 时为 $0$ .

这意味着什么呢，这说明 $k$ 为质数的时候这个式子为 $0$ .（根据引理可得）

否则，如果不是质数，那么小数上取整就是 $1$ . 整个式子就是 $n-1-\sum_{k=1}^n[\gcd(k,n)\neq 1]$ ，那么也就是 $1\sim n$ 中的质数个数，即 $\pi(n)$ .

Q.E.D.

是不是很生草