内容 第三章 · 幂剩余 · 34
术语线索
congruentia x^n ≡ A / indices / conditio solvendi
纯幂同余 / 指标 / 可解条件。
命题
The congruence x^n ≡ A can be translated into a linear congruence for indices.
同余 xⁿ ≡ A 可以翻译成指标的一次同余。
读法 现代白话辅助
若 x=g^y、A=g^a，那么 x^n≡A 等价于 ny≡a (mod p-1)。于是第三章把高次同余的一类问题重新降回第二章的一次同余。
分步证明Step-by-step proof
1 / 2选定原根 g，把未知 x 写成 g^y。
比较指标，得到 ny ≡ ind(A) (mod p-1)。
小例 worked example
题
模 7 下解 x² ≡ 2。用原根 3：2=3²。
解
设 x=3^y，则 2y≡2 (mod 6)，所以 y≡1 或 4 (mod 6)。x≡3 或 4。
我的笔记 自动保存