原根
阶
若 ，使 成立的最小的 ，称为 关于模 的阶，记为 。
若 ，则
由欧拉定理，设 ，则 当且仅当 ，特别地， 。
- 设 是素数， ，那么有且仅有 个关于模 的阶为 且两两互不同余的数。
- 设 ，则 关于模 两两互不同余。
- 设 是素数， ，则存在 个关于模 的阶为 且两两互不同余的数。
- 若 ，则
原根
，若 ，则称 为 的一个原根。
为 的一个原根当且仅当 构成模 的一个既约剩余系。
判断是否有原根
若 有原根，则 一定是下列形式： 。这里 为奇素数， 为正整数。
求所有原根
设 为 的一个原根，则集合 给出 的全部原根。因此，若 有原根，则 有 个关于模 两两互不同余的原根。
求一个原根
对 进行质因数分解得到不同的质因子 ，对于任意的 ，要判定 是否是模 的原根，只需要检验 这 个数中是否存在一个数在模 意义下与 同余。若存在，则 不是 的原根；若不存在，则 是 的原根。
另一种表达形式：
，设 是 的所有不同的素因数，则 是 的原根，当且仅当对任意 ，都有
证明
假设存在一个 使得 且 。
由裴蜀定理得，一定存在一组 满足 ；由欧拉定理/费马小定理得 ；故有：
又有 ，故 。
又 ，故 必至少整除 中的至少一个，设 ，则 。
故假设不成立。
用途
我们发现原根 拥有所有 FFT 所需的单位根 的性质，于是我们用 来代替 ，就能把复数对应到一个整数，在模 意义下进行快速变换了。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用