同余
\({\Huge\equiv}\)是同余符号
\[a \equiv b \pmod{n}
\]
读作：\(a\)与\(b\)模\(n\)同余
定义：\(a\)除以\(n\)的余数等于\(b\)除以\(n\)的余数。
例
\[10 \equiv 6 \pmod{2}
\]
\(\because\)
\[10 \% 2 = 0
\\
6 \% 2 = 0
\\
\because 0 = 0
\\
\therefore 10 \equiv 6 \pmod{2}
\]
定义与性质
同余定义
设 \( \(m \in \mathbb{Z}^+\) \)，( \(a, b \in \mathbb{Z}\))
\[a \equiv b \pmod{m} \iff m \mid (a - b)
\]
基本性质体系
1. 等价关系
-
自反性：
-
\[a \equiv a \pmod{m} \]
-
对称性：
-
\[a \equiv b \pmod{m} \Rightarrow b \equiv a \pmod{m} \]
-
传递性：
-
\[a \equiv b \pmod{m} \land b \equiv c \pmod{m} \Rightarrow a \equiv c \pmod{m} \]
2. 算术运算封闭性
若 \( 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} \)
- \( k \times a \equiv k \times b \pmod{m} \)（\( k \in \mathbb{Z} \)）
- \( a^n \equiv b^n \pmod{m} \)（\( n \in \mathbb{Z}^+ \)）
3. 模数变换
- 缩放：\( a \equiv b \pmod{m} \Rightarrow ak \equiv bk \pmod{mk} \)
- 约简：\( a \equiv b \pmod{m} \land d \mid m \Rightarrow a \equiv b \pmod{d} \)
- 合并：\( a \equiv b \pmod{m_1} \land a \equiv b \pmod{m_2} \Rightarrow a \equiv b \pmod{\text{lcm}(m_1,m_2)} \)
4. 消去律
\[ ac \equiv bc \pmod{m} \Rightarrow a \equiv b \pmod{\frac{m}{\gcd(c,m)}} \]
特例：当 \( \gcd(c,m) = 1 \) 时，可直接消去 \( c \)
5. 多项式保持
\[ a \equiv b \pmod{m} \Rightarrow P(a) \equiv P(b) \pmod{m} \]
（\( P(x) \) 为整系数多项式）
6. 结构性质
- 最大公约数保持：\( a \equiv b \pmod{m} \Rightarrow \gcd(a,m) = \gcd(b,m) \)
- 等价类划分：模 \( m \) 将整数划分为 \( m \) 个剩余类
- 幂的周期性：当 \( \gcd(a,m) = 1 \) 时，\( a^n \bmod m \) 具有周期性