同余的基本性质
一、定义
设整数 \(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++，规定在整数除法中：
- 当除数为 \(0\) 时，行为未定义；
- 否则
(a / b) * b + a % b的运算结果与a相等。
也就是说，取模运算的符号取决于除法如何取整；而除法如何取整，这是实现定义的（由编译器决定）。
从 C99 和 C++11 标准版本起，规定 商向零取整（舍弃小数部分）；
取模的符号即与被除数相同。从此以下运算结果保证为真：
5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;参考文献：
