Cekavis's notes

恒等式

$$
[d|n]=\frac{1}{d} \sum_{i=0}^{d-1} \omega_d^{i\times n}
$$

其中 $\omega_d$ 是 $d$ 次单位根

• 当 $d|n$，右边和式中每一项都为 $1$

• 当 $d\nmid n$，容易得到右边为 $0$