同余¶
两个整数 \(a,b\)，如果它们除以正整数 \(m\) 所得余数相同，则称 \(a,b\) 对于模 \(m\) 同余，记作
\[ a \equiv b \pmod{m} \]
同余是一种等价关系，满足自反性、对称性、传递性。
整除性¶
\[ a \equiv b \pmod{m} \Longleftrightarrow m \mid (a-b) \]
同余和 整除 可以相互转化。
基本运算¶
\[ \left.\begin{matrix} a \equiv b \pmod{m} \\ c \equiv d \pmod{m} \end{matrix}\right\} \Longrightarrow \left\{\begin{matrix} a \pm c \equiv b \pm d \pmod{m} \\ ac \equiv bd \pmod{m} \end{matrix}\right. \]
除法¶
\[ \left.\begin{matrix} ac \equiv bc \pmod{m} \\ \gcd(c, m) = 1 \end{matrix}\right\} \Longrightarrow a \equiv b \pmod{m} \]
其他性质¶
\[ \left.\begin{matrix} a \equiv b \pmod{m_1} \\ a \equiv b \pmod{m_2} \\ \vdots \\ a \equiv b \pmod{m_n} \end{matrix}\right\} \Longrightarrow a \equiv b \pmod{\operatorname{lcm}(m_1, m_2, \dots, m_n)} \]
最小公倍数（lcm）可以用 欧几里得算法 计算。
相关文章