同余
| 同余 | |
|---|---|
| 术语名称 | 同余 |
| 英语名称 | congruence |
| 模数 | |
|---|---|
| 术语名称 | 模数 |
| 英语名称 | modulus |
| 别名 | 模 |
| 取余 | |
|---|---|
| 术语名称 | 取余 |
| 英语名称 | modulo |
| 同余式 | |
|---|---|
| 术语名称 | 同余式 |
| 英语名称 | congruence |
同余(congruence)指两数被同一数除后所得余数相同。
定义
| 同余 | |
|---|---|
| 关系名称 | 同余 |
| 关系符号 | [math]\displaystyle{ \equiv\pmod n }[/math] |
| Latex | \equiv\pmod n
|
| 关系对象 | 整数 |
| 关系元数 | 2 |
| 全集 | [math]\displaystyle{ \mathbb{Z}\times\mathbb{Z} }[/math] |
对整数 [math]\displaystyle{ a, b }[/math] 和正整数 [math]\displaystyle{ n }[/math] ，若 [math]\displaystyle{ a, b }[/math] 被 [math]\displaystyle{ n }[/math] 除后余数相同，则称整数 [math]\displaystyle{ a, b }[/math] 模 [math]\displaystyle{ n }[/math] 同余(are congruent modulo [math]\displaystyle{ n }[/math]) 或关于模（数） [math]\displaystyle{ n }[/math] /对模（数） [math]\displaystyle{ n }[/math] /在模（数） [math]\displaystyle{ n }[/math] 下同余(are congruent under modulus [math]\displaystyle{ n }[/math]）—— ，记作 [math]\displaystyle{ a\equiv b\pmod n }[/math] ，其中正整数 [math]\displaystyle{ n }[/math] 称为模/模数(modulus)。
不满足同余关系的情况，称为整数 [math]\displaystyle{ a, b }[/math] 模 [math]\displaystyle{ n }[/math] 不同余(are incongruent modulo [math]\displaystyle{ n }[/math]) ，记作 [math]\displaystyle{ a\not\equiv b\pmod n }[/math] 。
以上形如 [math]\displaystyle{ a\equiv b\pmod n }[/math] 的式子称为同余式(congruence)。
与整除的关系
由定义可知，
[math]\displaystyle{ \begin{align*} a \equiv 0 \pmod n &\leftrightarrow n \mid a \\ a \equiv b \pmod n &\leftrightarrow n \mid a - b \end{align*} }[/math]
等价关系
由于建立在余数是否相等上，同余显然是一种等价关系，满足自反、对称、传递的性质。
性质
对整数的加法、乘法、乘方运算，同余关系都保持原运算关系不变，即若 [math]\displaystyle{ a\equiv b \pmod n, c\equiv d \pmod n }[/math] ，则有：
- 保持加法： [math]\displaystyle{ a + c \equiv b + d \pmod n }[/math]
- 保持乘法： [math]\displaystyle{ a c \equiv b d \pmod n }[/math]
- 保持数乘： [math]\displaystyle{ k a \equiv k b \pmod n, k\in\mathbb{Z} }[/math]
- 保持乘方： [math]\displaystyle{ a^m \equiv b^m \pmod n, m\in\mathbb{N}_+ }[/math]
对应地，加法的消去律成立。
但是乘的消去律不成立，也仅在一定条件下被保持：
- [math]\displaystyle{ ab \equiv ac \pmod n \land \operatorname{gcd}(a, n)=1 \rightarrow b\equiv c \pmod n }[/math]