内容 第三章 · 幂剩余 · 35
术语线索
radices congruentiae / gcd(n, p-1)
同余根 / gcd(n,p-1)。
命题
The number of solutions of x^n ≡ A is governed by gcd(n, p - 1) and the index of A.
xⁿ ≡ A 的解数由 gcd(n,p-1) 以及 A 的指标决定。
读法 现代白话辅助
指标方程 ny≡a 的可解条件是 gcd(n,p-1) 整除 a；若可解，就有那么多个指标解。高斯由此把幂剩余的判定变成整数同余的判定。
分步证明Step-by-step proof
1 / 2令 d=gcd(n,p-1)。
线性同余 ny≡a 可解当且仅当 d | a；可解时有 d 个模 p-1 的解。
小例 worked example
题
模 13 下，x³≡A 的可解性要看什么？
解
p-1=12，gcd(3,12)=3。若 ind(A) 被 3 整除，则可解且有 3 个解；否则无解。
我的笔记 自动保存