数论实验 / FR030

余数轮盘

所有余数构成环；只有可逆的余数进入单位群。一个数的幂，能走遍哪里？

搜索

先看全体余数

模 m 的余数轮盘圆上每个点表示一个余数。绿色表示单位。预测后显示从 1 开始的幂轨道。

单位 非单位 已揭示的幂轨道

预测 → 验证 → 换参

a 是模 m 的原根吗？

先判断 a 是否为单位，再判断它的幂能否遍历全部单位。图中此时只显示余数与单位。

从余数环到原根

  1. 完全剩余系。本实验限定整数模数 2 ≤ m ≤ 120。整数 x、y 同余当且仅当 m 整除 x − y。每个整数恰落在 0, 1, …, m − 1 中的一类。每类各取一个代表就得到完全剩余系，例如 qm, qm + 1, …, qm + m − 1；它们不要求与 m 互素。
  2. 环与单位群。加法和乘法先计算再取余，结果不依赖代表元。单位是满足 gcd(a,m)=1 的余数：贝祖等式给出其乘法逆元；若存在逆元，公因子必整除 1。单位的个数记作 φ(m)，它们在乘法下构成群。0 不属于单位群。
  3. 乘法阶。仅当 gcd(a,m)=1 时，ordm(a) 定义为使 aᵈ ≡ 1 (mod m) 的最小正整数 d。若两个幂相等，可乘逆元约去较低次幂，所以轨道从 1 开始循环，无前段。不同的前 d 个幂构成子群，其陪集将单位群等分，故 d 整除 φ(m)，并有 aφ(m) ≡ 1。
  4. 原根。单位 a 是原根，当且仅当 ordm(a)=φ(m)，也即其幂走遍所有单位。原根不会生成非单位，也不会生成 0。并非每个模数都有原根。对于 m ≥ 2，存在原根恰在 m=2、4、pʳ、2pʳ（p 为奇素数，r ≥ 1）时成立；这是一般存在性定理，此处不证明。本轮盘通过逐个单位穷举幂轨道判定，不依赖该定理。
  5. 非单位的幂。仍能计算 aᵏ，但此处不称其循环长度为“乘法阶”。本实验采用环中零次幂（空乘积）的约定 a⁰=1，包括 a=0。有限余数状态必重复，可能先有前段，再进入周期。轮盘将首次重复的箭头也画出，明确标出前段长度与周期长度。

探索提示：分别试奇素数、奇素数的平方、2 的幂以及含不同奇素因子的合数。改变 q 检查代表元，改变 b 检查环运算；改变 m 或 a 后请重新预测。