同余与模运算

基于循环表盘的周期跳转，理解同余等价类与模算术性质

📖 数论基石：同余式与模算术

在数论及程序设计中，当处理极大数值时，通常会在模 $m$ 的意义下进行运算。模运算 (Modulo Operation) 是指两数相除所得的余数，而同余 (Congruence) 描述了余数相同的数之间的关系：

📐 同余等价类与定义

若整数 $a$ 和 $b$ 除以正整数 $m$ 的余数相同，则称 $a$ 与 $b$ 模 $m$ 同余，记作：

$a \equiv b \pmod m \iff m \mid (a - b)$

等价类集合：所有与 $a$ 模 $m$ 同余的整数构成一个集合，称为模 $m$ 的一个同余等价类：

$[a]_m = \{ \ldots, a-2m, a-m, a, a+m, a+2m, \ldots \}$

📐 模运算的代数分配性质

模运算具有完美的加、减、乘分配律。这允许我们在中间步骤取模，以防止整数溢出：

  • 加法：$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
  • 减法：$(a - b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$ （防止产生负数余数）
  • 乘法：$(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$
  • 除法：不满足直接分配率，必须使用模逆元（后面章节重点讲解）。
选择模数 $m$ 及输入 $a, b$，然后点击“模加演示”或“模乘演示”观察时钟环表盘的流动轨迹。
等价关系表达式 5 ≡ 12 ≡ 19 (mod 7)
模加结果 (a+b) mod m 2
模乘结果 (a*b) mod m 6
a 的等价类 (前5项) {5, 12, 19, 26, 33}
⏰ 模同余环表盘 (Residue Class Ring Clock)
起点 0
当前位置
跳转过程路径
最终目标余数
// 模加运算
long long modAdd(long long a, long long b, long long m) {
    return (a % m + b % m) % m;
}

// 模减运算 (包含负数保护)
long long modSub(long long a, long long b, long long m) {
    return (a % m - b % m + m) % m;
}

// 模乘运算
long long modMul(long long a, long long b, long long m) {
    return (a % m) * (b % m) % m;
}
📋 模同余运算历史步骤