单位根反演

[ n ∣ k ] = 1 n ∑ i = 0 n − 1 ω n k i [n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega^{ki}_n [n∣k]=n1​i=0∑n−1​ωnki​

证明

当 n ∣ k n|k n∣k时，设 k = n p k=np k=np，则
1 n ∑ i = 0 n − 1 ω n n p i    m o d    n = 1 n ∑ i = 0 n − 1 ω n 0 = 1 \frac{1}{n}\sum_{i=0}^{n-1}\omega^{npi\;mod\;n}_n=\frac{1}{n}\sum_{i=0}^{n-1}\omega^0_n=1 n1​i=0∑n−1​ωnnpimodn​=n1​i=0∑n−1​ωn0​=1
当 n ∤ k n\nmid k n∤k，根据等比数列求和公式，则
1 n ∑ i = 0 n − 1 ω n k i = 1 n ω n 0 ( 1 − ω n k n ) 1 − ω n k = 0 \frac{1}{n}\sum_{i=0}^{n-1}\omega^{ki}_n=\frac{1}{n}\frac{\omega^0_n(1-\omega^{kn}_n)}{1-\omega^k_n}=0 n1​i=0∑n−1​ωnki​=n1​1−ωnk​ωn0​(1−ωnkn​)​=0

原根

可以用原根代替单位根，因为单位根所具有的性质，原根也有。
设 g g g是素数 p p p的原根，则令 g n = g p − 1 n g_n=g^{\frac{p-1}{n}} gn​=gnp−1​，那么有 g n i = g i ( p − 1 ) n g^i_n=g^{\frac{i(p-1)}{n}} gni​=gni(p−1)​，就用 g n i g^i_n gni​代替 ω n i \omega^i_n ωni​

例题

LJJ 学二项式定理