单位根反演学习笔记

$m$ 次单位根 $\omega_m$：$\omega_m^m=1$ 且 $\forall 1\le i\le m$，$\omega_{m}^i$ 互不相同。

单位根反演：

$[m|x]=\frac{1}{m}\sum\limits_{i=1}^m\omega_m^{ix}\qquad(1)\\ [x\equiv r\pmod m]=\frac{1}{m}\sum\limits_{i=1}^m\omega_m^{i(x-r)}\qquad(2)$

证明：

由 $(1)$ 易得 $(2)$，下面证明 $(1)$。

显然若 $m|x$ 则相当于 $\frac{1}{m}\sum\limits_{i=1}^m 1^{\frac{ix}{m}}=1$。

若 $m\nmid x$，则相当于 $\frac{1}{m}\sum\limits_{i=1}^m(\omega_m^{x})^i$，此时 $\omega_m^x\not=1$，运用等比数列求和公式得 $\frac{1}{m}\times \frac{\omega_m^x-\omega_m^x\omega_m^{xm}}{1-\omega_m^x}=\frac{1}{m}\times \frac{\omega_m^x-\omega_m^x}{1-\omega_m^x}=0$。

例题：

$\begin{aligned} \sum\limits_{i=0}^n [i\equiv r\pmod m]\binom{n}{i}&=\frac{1}{m}\sum\limits_{i=0}^n \binom{n}{i}\sum\limits_{j=1}^m \omega_m^{j(i-r)}\\&=\frac{1}{m}\sum\limits_{j=1}^m\frac{1}{\omega_m^{jr}}\sum\limits_{i=0}^n\binom{n}{i}\omega_m^{ji}\\&=\frac{1}{m}\sum\limits_{j=1}^m\frac{1}{\omega_m^{jr}}(\omega_m^j+1)^n \end{aligned}$