内容 第三章 · 幂剩余 · 28
术语线索
progressio geometrica / periodus residuorum
几何级数 / 剩余周期。
命题
If a is coprime to p, the residues of 1, a, a², ... modulo p eventually return to 1 and then repeat periodically.
若 a 与 p 互素，1,a,a²,... 模 p 的剩余终会回到 1，并从此周期重复。
读法 现代白话辅助
高斯从有限性出发：模 p 的非零剩余只有 p-1 个，幂却无限多，必然重复。一旦某两个幂重复，约去较小幂就得到某个正幂等于 1。
分步证明Step-by-step proof
1 / 2非零剩余只有 p-1 个。
若 a^m ≡ a^n 且 m>n，因 a^n 可约去，得到 a^(m-n) ≡ 1。
小例 worked example
题
求 2 的幂模 7 的周期。
解
2,4,8≡1，所以周期为 3：2,4,1,2,4,1,...。
我的笔记 自动保存