定义

称 $g$ 为 $p$ 的原根，当且仅当 $g$ 在 $\;p$ 意义下的阶为 $φ(p)\varphi(p)$ （这里的 $φ(p)\varphi(p)$ 是欧拉函数）。

p.s. 若 $g, p$ 互质， $n$ 是满足 $gn≡1modmg^n\equiv 1\mod m$ 的最小正整数，称 $n$ 为 $g$ 模 $p$ 的阶。

性质

根据定义，有

$∀i,j∈[0,φ(p)−1],i≠j,gi≢gjmodp\forall i,j\in[0,\varphi(p)-1],i\neq j,g^i\not\equiv g^j\mod p$

证明很显然，可以用反证法：

若 $g$ 是 $p$ 的原根，且 $∃i,j∈[0,φ(p)−1],i≠j,gi≡gjmodp\exist i,j\in[0,\varphi(p)-1],i\neq j,g^i\equiv g^j\mod p$

那么 $g∣i−j∣≡1modpg^{|i-j|}\equiv 1\mod p$

因为 $i,j∈[0,φ(p)−1],i≠ji,j\in[0,\varphi(p)-1],i\neq j$

所以 $0<∣i−j∣<φ(p)−10<|i-j|<\varphi(p)-1$

由性质可知 $g$ 不是 $p$ 的原根。

做法：

还是利用原根的定义。

将欧拉函数质因数分解 $φ(p)=∏piki\varphi(p)=\prod p_i^{k_i}$

若一个数 $g$ 满足 $∀i,gφ(p)pi≠1modp\forall i,g^{\frac{\varphi(p)}{p_i}}\neq 1\mod p$ ，那么他是 $p$ 的一个原根。

证明：

证明用到裴蜀定理。

假设存在一个 $k<φ(p)k<\varphi(p)$ 使得 $gk≡1(modp)g^k\equiv 1(mod\;p)$

根据裴蜀定理，一定存在一组 $a, b$ 满足 $a⋅k−b⋅φ(p)=gcd(k,φ(p))a\cdot k-b\cdot\varphi(p)=gcd(k, \varphi(p))$

所以 $gk≡ggcd(k,φ(p))+b⋅φ(p)≡ggcd(k,φ(p))≡1(modp)g^k\equiv g^{gcd(k, \varphi(p))+b\cdot\varphi(p)}\equiv g^{gcd(k,\varphi(p))}\equiv 1(mod \; p)$

因为 $k<φ(p)k<\varphi(p)$ 所以 $gcd(k,φ(p))<φ(p)gcd(k,\varphi(p))<\varphi(p)$

又因为 $gcd(k,φ(p))∣φ(p)gcd(k,\varphi(p))|\varphi(p)$

所以一定存在一个 $gφ(p)pi≡1(modp)g^{\frac{\varphi(p)}{p_i}}\equiv 1(mod\; p)$ ，通过检验这些数就可以知道一个数是不是原根了。

指标函数 $I (x)$ 定义如下：

$gI(x)≡xmodpg^{I(x)}\equiv x\mod p$

可以对比一下连续的对数：

$a^{\log_ax}=x$

可以发现两者非常相似。 $I (x)$ 也就是离散对数。与一般意义下的对数性质也非常相似，可以在取模意义下把乘法变成加法，把乘方变成乘法。

详情请见 [SDOI2015]序列统计。

NTT 用原根来代替实数中使用的单位根 $ω\omega$ 。

设 $g$ 是质数 $p$ 的原根，再设 $ωn=g(p−1)/n\omega_n=g^{(p-1)/n}$ （ $p$ 满足 $n ∣ p - 1$ ）。

$ωnn≡1(modp)\omega_n^{n}\equiv 1(mod\; p)$
$ωn0,ωn1,…,ωnn−1\omega_n^0,\omega_n^{1},\dots,\omega_n^{n-1}$ 在 $modpmod\; p$ 意义下互不相同
$ωnk≡−ωnk+n/2\omega_n^k\equiv -\omega_n^{k+n/2}$ 即 $ωnn/2≡−1(modp)\omega_n^{n/2}\equiv-1(mod\; p)$