原根
阶
若 ，使 成立的最小的 ，称为 关于模 的阶，记为 。
若 ，则
由欧拉定理，设 ，则 当且仅当 ，特别地， 。
- 设 是素数， ，那么有且仅有 个关于模 的阶为 且两两互不同余的数。
- 设 ，则 关于模 两两互不同余。
- 设 是素数， ，则存在 个关于模 的阶为 且两两互不同余的数。
- 若 ，则
原根
，若 ，则称 为 的一个原根。
为 的一个原根当且仅当 构成模 的一个既约剩余系。
判断是否有原根
若 有原根，则 一定是下列形式： 。这里 为奇素数， 为正整数。
求一个原根
，设 是 的所有不同的素因数，则 是 的原根，当且仅当对任意 ，都有 。
证明
假设存在一个 使得 且 。
由裴蜀定理得，一定存在一组 满足 ；由欧拉定理/费马小定理得 ；故有：
又有 ，故 。
又 ，故 必至少整除 中的至少一个，设 ，则 。
故假设不成立。
求所有原根
设 为 的一个原根，则集合 给出 的全部原根。因此，若 有原根，则 有 个关于模 两两互不同余的原根。
一个数的最小原根
若一个数 存在原根，可以证明 的最小原根在 级别。
这个结论意味着，我们求所有的原根时，枚举最小原根花费的时间一般都是可以接受的。
用途
我们发现原根 拥有所有 DFT 所需的单位根 的性质，于是我们用 来代替 ，理论上就能把复数对应到一个整数，在模 意义下进行快速变换了。
但实际上由于快速傅里叶变换（FFT）实现的多项式乘法的过程中要求序列长度是 的幂次，因此这里模数 还需要保证 的标准分解式中素因子 的幂次足够大，参见 快速数论变换 。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用