同余的基本性质

一、定义

设整数 $m \ne 0$ 。若 $m \mid (a - b)$ ，则称 $m$ 为模数（模），

$a$ 同余于 $b$ 模 $m$ ，$b$ 是 $a$ 对模 $m$ 的剩余，记作 $a \equiv b \pmod{m}$ 。

否则 $a$ 不同余 $b$ 模 $m$ ，$b$ 不是 $a$ 对模 $m$ 的剩余，记作 $a \not\equiv b \pmod{m}$ 。

这样的等式称为模 $m$ 的同余式，简称同余式。

根据整除的性质，上述同余式也等价于 $a \equiv b \pmod{(-m)}$

故未特别注明的情况，默认模数为正整数。

---

二、性质

• 同余是等价关系，即同余具有

  • 自反性：$a\equiv a\pmod m$
  • 对称性：若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$
  • 传递性：若 $a\equiv b\pmod m,b\equiv c\pmod m$，则 $a\equiv c\pmod m$

• 线性运算：若 $a,b,c,d\in\mathbb{Z},m\in\mathbb{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$ 则有：

  • $a\pm c\equiv b\pm d\pmod m$
  • $a\times c\equiv b\times d\pmod m$

• 设 $f(x)=\sum_{i=0}^n a_ix^i$ 和 $g(x)=\sum_{i=0}^n b_ix^i$ 是两个整系数多项式，$m\in\mathbb{N}^*$，

  则对任意整数 $x$ 均有 $f(x)\equiv g(x)\pmod m$

  进而若 $a_i\equiv b_i\pmod m,~0\leq i\leq n$，那么若 $s\equiv t\pmod m$，则 $f(s)\equiv g(t)\pmod m$。

• 若 $a,b\in\mathbb{Z},\,k,m\in\mathbb{N}^*,a\equiv b\pmod m$ ，则 $ak\equiv bk\pmod{mk}$。

• 若 $a,b\in\mathbb{Z},\,d,m\in\mathbb{N}^*,d\mid a,d\mid b,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)$。

• 若 $a,b\in\mathbb{Z},\,d,m\in\mathbb{N}^*,d\mid m$，则当 $a\equiv b\pmod m$ 成立时，有 $a\equiv b\pmod d$。

• 若 $a,b\in\mathbb{Z},\,d,m\in\mathbb{N}^*$，则当 $a\equiv b\pmod m$ 成立时，有 $(a,m)=(b,m)$。

  若 $d$ 能整除 $m$ 及 $a,b$ 中的一个，则 $d$ 必定能整除 $a,b$ 中的另一个。

还有性质是乘法逆元。本文不涉及该部分。

---

三、C/C++ 的整数除法和取模运算

在 C/C++ 中，整数除法和取模运算，与数学上习惯的取模和除法不一致。

对于所有标准版本的 C/C++，规定在整数除法中：

1. 当除数为 $0$ 时，行为未定义；
2. 否则 (a / b) * b + a % b 的运算结果与 a 相等。

也就是说，取模运算的符号取决于除法如何取整；而除法如何取整，这是实现定义的（由编译器决定）。

从 C99 和 C++11 标准版本起，规定 商向零取整（舍弃小数部分）；

取模的符号即与被除数相同。从此以下运算结果保证为真：

5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;

---

参考文献：

[1] https://oi-wiki.org/math/number-theory/basic/