最后更新: 2023-10-24 14:05 ● 参与者查看: 188 次纠错分享评论参与项目

同余

同余是初等数论里的一个重要的概念，关于代数系统之间的同余，详见代数同余。

## 概念

若两个数 $a$ 与 $b$ 除以 $m$ 的余数相同，或说 $a-b$ 可被 $m$ 整除，则说 $a$ 与 $b$ 同余于 $m$ 或 $a$ 等于 $b$ 模 $m$ 。

一般将“ $a$ 与 $b$ 同余于 $m$ "记作 $a \equiv b \quad(\bmod m)$ 且有 $a \equiv b \quad(\bmod m) \Longleftrightarrow m \mid a-b$ ，而 $a \neq \equiv \quad(\bmod m) \Longleftrightarrow m \nmid a-b$

除整数集合外，所有整系数多项式所组成的集合，亦有类似整数的同余存在。

## 性质

- 同余是一个等价关系，是因为它有:

1. 自反性, $a \equiv a(\bmod m)$;
2. 对称性， $a \equiv b \quad(\bmod m) \Longleftrightarrow b \equiv a \quad(\bmod m)$;
3. 传递性: $a \equiv b \quad(\bmod m) \& b \equiv c \quad(\bmod m) \Longrightarrow a \equiv c(\bmod m)$.

- 同余式运算有像通常等式那样类似的加减乘运算:

1. 若 $a \equiv c \quad(\bmod m)$ 且 $b \equiv d \quad(\bmod m)$ ，则 $(a \pm b) \equiv(c \pm d) \quad(\bmod m)$ 且 $a b \equiv c d \quad(\bmod m)$ ；
2. 若 $a c \equiv b c \quad(\bmod m)$ 则 $a \equiv b \quad\left(\bmod \frac{m}{(c, m)}\right)$ ，特别地， $(c, m)=1$ ，则 $a \equiv b \quad(\bmod m)$ ；

- 若 $(a, m)=1$ ，则存在一数 $c$ ，使得 $c a \equiv 1 \quad(\bmod m)$ ；
- 若 $a \equiv b \quad(\bmod m)$ ，则 $\forall d: d \mid m, a \equiv b \quad(\bmod d)$ ；
- 若 $d>0$ ，则 $a \equiv b \quad(\bmod m) \Longleftrightarrow a d \equiv b d \quad(\bmod m d)$ ；
- 若 $a \equiv b \quad\left(\bmod m_i\right), 1 \leqslant i \leqslant n$ ，则 $a \equiv b \quad\left(\bmod \left[m_1, m_2, \cdots, m_n\right]\right)$ 。
-

## 推论

设 $f(x)$ 是整系数多项式，如果 $a \equiv b(\bmod m)$ ，则 $f(a) \equiv f(b) \quad(\bmod m)$ 。

上一篇：整除

下一篇：费马小定理

本文对您是否有用？有用 (0) 无用 (0)

0 条评论写评论

更多笔记

提交评论