内容 第三章 · 幂剩余 · 37
术语线索
radices primitivae determinare / divisores p-1
确定原根 / p-1 的因子。
命题
To test a primitive root, it is enough to check the proper divisors of p - 1.
检验一个数是否为原根，只需检查 p-1 的真因子对应的幂是否提前回到 1。
读法 现代白话辅助
若 g 的某个真因子指数 d 已经满足 g^d≡1，它的周期就不可能是 p-1。反过来，只要所有关键真因子都不过早回到 1，g 就是原根。
分步证明Step-by-step proof
1 / 2列出 p-1 的素因子 q。
检查 g^((p-1)/q) 是否都不等于 1。
小例 worked example
题
检验 2 是否为模 11 的原根。
解
p-1=10，素因子为 2、5。2^5=32≡10，不是 1；2^2=4，不是 1，所以 2 是原根。
我的笔记 自动保存