取模 & 同余

取模

定义

对于 $a,b\in\mathbb{Z}$，满足 $b>0$，则存在唯一的整数 $q,r$，满足 $a=b\times q+r\,(0\le r

称 $q$ 为商、$r$ 为余数。余数用 $a\bmod b$ 表示，在 $\text{C++}$ 中表示为 a % b。

性质

• $(a+b)\bmod m=(a\bmod m+b\bmod m)\bmod m$。

• $(a-b)\bmod m=(a\bmod m-b\bmod m)\bmod m$。

  需要注意的是，$a\bmod m$ 可能小于 $b\bmod m$，那么结果在 $\text{C++}$ 中计算的结果将是负数。

  但是在数学中，负数取模的结果仍然是非负数，故在 $\text{C++}$ 中一般将其写作 (a % m - b % m + m) % m。

• $(a\times b)\bmod m=(a\bmod m\times b\bmod m)\bmod m$。

PS：注意，$(a\div b)\bmod m=\big((a\bmod m)\div(b\bmod m)\big)\bmod m$ 这个等式不一定成立！

反例：$a=12,b=3,m=6$，$(a\div b)\bmod m=4$，而
$$ \begin{aligned} \big((a\bmod m)\div(b\bmod m)\big)\bmod m&=(0\div 3)\bmod 6\\ &=0 \end{aligned} $$
$0\not=4$，故上述等式不一定成立。

---

如果想在模意义下实现除法，请参见 乘法逆元。

同余

定义

若 $x,y\in\mathbb{Z}$ 除以 $m$ 的余数相同，则称 $x,y$ 模 $m$ 同余，记为 $x\equiv y\pmod m$。

性质

• 反身性：$x\equiv x\pmod m$。
• 对称性：$x\equiv y\pmod m$，则 $y\equiv x\pmod m$。
• 传递性：如果 $x\equiv y\pmod m$，$y\equiv z\pmod m$，则 $x\equiv z\pmod m$。
• 同加减性：如果 $x\equiv y\pmod m$，则 $x\pm z\equiv y\pm z\pmod m$。
• 同乘性：如果 $x\equiv y\pmod m$，则 $x\times z\equiv y\times z\pmod m$。
• 同幂性：如果 $x\equiv y\pmod m$，则 $x^z\equiv y^z\pmod m$。

此外，还有一个十分重要的性质：
$$ x\equiv y\pmod m \Leftrightarrow m\mid (x-y) $$