原根计算器 — 求模n的最小原根
我们的原根计算器求模n的最小原根——一个整数g，其幂g¹、g²、g³……在重复之前会遍历模n的每一个单位。它首先检查原根是否存在（原根仅存在于n = 1、2、4、pᵏ或2pᵏ，其中p为奇素数），然后使用欧拉函数及其素因数分解，高效地测试每个候选值。
快速解答
原根g mod n通过其幂生成模n的每个单位。在下方输入n以找到最小的原根，并自动检查是否存在任何原根。
输入n，然后点击计算。
如何使用 原根计算器 — 求mod n的生成元
- 1
输入一个正整数n（最多1,000,000）。
- 2
点击'计算'求模n的最小原根（如果存在）。
- 3
查看验证中使用的φ(n)和φ(n)的素因数。
为什么使用 原根计算器 — 求mod n的生成元？
模n的原根是与n互质的整数在乘法下所构成群的生成元：其连续的幂恰好在φ(n)步内产生模n的每个单位各一次，然后循环回到1。并非每个n都有原根——原根仅存在于n = 1、2、4、奇素数幂pᵏ，或奇素数幂的两倍2pᵏ，这是数论中的一个经典结果。本计算器首先检查该条件，然后通过对φ(n)的每个素因数q测试g^(φ(n)/q) mod n来高效验证每个候选g——当且仅当所有这些测试都不等于1时，g才是原根。