“原根和单位根有相同的性质”这句话已经很清楚了吧=.=
具体来讲就是都满足
$$\omega ^k\begin{cases}=1&(k= 0\bmod n)\\\neq 1&(k\neq 0\bmod n)\end{cases}$$
于是可以推出
$$\dfrac 1n\sum_{k=0}^{n-1}\omega^{vk}=[v\bmod n=0]$$
by x义x @ 2019-12-12 14:33:01
@[基地A_I](/user/147511)
by x义x @ 2019-12-12 14:33:19
@[基地A_I](/user/147511) https://www.luogu.com.cn/blog/command-block/ntt-yu-duo-xiang-shi-quan-jia-tong
by pzc2004 @ 2019-12-12 14:47:58
在 FFT 中，单位根有如下四条性质：
1. $w_n^0,w_n^1,\dots,w_n^{n-1}$ 互不相同
对于原根有一个定理(不做证明)，即 $g^i \mod P$ 对于 $i \in (0,P)$ 结果两两不同。
2. $w_{2n}^{2k}=w_n^k$
$g^{\frac{P-1}{2n}*2k}=g^{\frac{P-1}{n}*k}$
3. $w_{n}^{k+\frac{n}{2}}=-w_n^k$
$g^{\frac{P-1}{n}*k}*g^{\frac{P-1}{2}}$
由性质 $1$ 得，$g^{\frac{P-1}{2}}\neq g^{P-1}$ ①
由 $g^{\frac{P-1}{2}}=\sqrt{g^{P-1}}=\sqrt{1}=1/-1$
由 ①，$g^{\frac{P-1}{2}}=-1$
故 $g^{\frac{P-1}{n}*k}*g^{\frac{P-1}{2}}=-g^{\frac{P-1}{n}*k}$
4. $1+w_n^k+\dots+(w_n^k)^{n-1}=0(k\neq 0)$
可以类似 $FFT$ 地推出。
于是我们就能使用 $g$ 代替 $w_n$ 了。
by Wen_kr @ 2019-12-12 15:50:24
@[Wen_kr](/user/25308) 感谢！
by 基地A_I @ 2019-12-12 19:16:17
讲的不错！竟然把我这一蒟蒻讲明白了qwq。所以说原根最难证明的地方就是性质1咯？（~~难怪机房大佬说原根不可证qwq~~）
by 基地A_I @ 2019-12-12 19:18:28
真的太感谢了！QwQ
by 基地A_I @ 2019-12-12 19:18:59