内容 第三章 · 幂剩余 · 32
术语线索
radix primitiva / basis / index
原根 / 基数 / 指标。
命题
A primitive root modulo p is a residue whose powers run through all nonzero residue classes.
模 p 的原根，是其幂能遍历全部非零剩余类的数。
读法 现代白话辅助
原根是第三章的枢纽。选定原根 g 后，每个非零剩余都可写成 g^k；这个 k 就是该剩余的指标，也就是今天说的离散对数。
分步证明Step-by-step proof
1 / 2找一个周期为 p-1 的数 g。
把每个非零剩余 a 写成 g^k，并把 k 记作 a 的指标。
小例 worked example
题
模 7 下，3 是否为原根？
解
3^1=3，3^2=2，3^3=6，3^4=4，3^5=5，3^6=1，遍历 1 到 6，所以 3 是原根。
我的笔记 自动保存