同余式与同余类

作者: 洛玖言 | 来源:发表于2019-10-12 07:20 被阅读0次

第二章同余

同余式与同余类

模 $m$ 同余

设 $m$ 是非零整数， $a$ 和 $b$ 是整数. 如 $m|(a-b)$ ，则称 $a$ 和 $b$ 模 $m$ 同余 (或 $a$ 模同余于 $b\,$ )，记作
$a\equiv b\pmod{m}\tag{1}$

如果 $m\not|(a-b)$ ，则称 $a$ 和 $b$ 模 $m$ 不同余，记作
$a\not\equiv b\pmod{m}$
（1）式称为(模 $m$ 的) 同余式.

模 $m$ 的同余类

设 $m$ 是一个固定的正整数. 由于“模 $m$ 同余” 是整数集上的一个等价关系，由此可将整数按模 $m$ 是否同余分为若干个两两不相交的类，使得同一个类中的任意两个数模 $m$ 同余，而不同类中的两个数模 $m$ 不同余；每一个正阳的类称为 模 $m$ 的同余类. 我们将整数 $a$ 所属的模 $m$ 的同余类记作 $a\pmod{m}$ ，在不引起混淆时可简记为 $\bar{a}$ ，它由所有模 $m$ 同余于 $a$ 的整数组成，即
$\bar{a}=\{n|n\,\in\,\mathbb{Z},\,n\equiv a\pmod{m}\},$
$a$ 称为它的一个代表元. 易知，当 $a\equiv b\pmod{m}$ 时，有 $\bar{a}=\bar{b}$ ；否则 $\bar{a}$ 与 $\bar{b}$ 不相交(即没有公共元素)

由带余除法，任一整数，比与 $0,1,\cdots,m-1$ 中的一个模 $m$ 同余，而 $0,1,\cdots,m-1$ 彼此模 $m$ 不同余. 因此，模 $m$ 恰有 $m$ 个不同的同余类，它们是 $\bar{0},\bar{1},\cdots,\overline{m-1}$ . 我们用 $\mathbf{Z}_m$ 表示这个 $m$ 个类的集合. (一个类看作一个元素)

同余类

如果 $(a,m)=1$ ，则有同余类 $\bar{a}$ 中每个整数也均与 $m$ 互素，这样的同余类称为模 $m$ 的缩同余类，换句话说， $\bar{a}$ 是(模 $m$ ) 缩同余类指的是 $(a,m)=1$ .

欧拉函数

我们用 $\mathbf{Z}_m^*$ 表示模 $m$ 的缩同余类组成的集合，其元素个数记作 $\varphi(m)$ ，称为欧拉函数，这是初等数论中一个重要的函数. 显然， $\varphi(1)=1$ ，而对 $m>1，\,\varphi(m)\;\;$ 即为 $1,2,\cdots,m-1$ 中与 $m$ 互素的数的个数.

例如，若 $p$ 是素数，则模 $p$ 共有 $p-1$ 个缩同余类： $\bar{1},\bar{2},\cdots,\overline{p-1}$ ，从而 $\varphi(p)=p-1$

完全剩余系

$m$ 个整数 $c_1,\cdots,c_m$ 称为模 $m$ 的完全剩余系，简称为模 $m$ 的完系，是指 $c_1,\cdots,c_m$ 彼此模 $m$ 不同余. 数 $0,1,\cdots,m-1$ 则称为模 $m$ 的最小非负完系.

$\varphi(m)$ 个整数 $r_1,r_2,\cdots,r_{\varphi(m)}$ 称为 模 $m$ 的缩剩余系，简称为缩系，是指它们彼此模 $m$ 不同余，且均与 $m$ 互素. 不超过 $m$ 且与 $m$ 互素的 $\varphi(m)$ 个正整数则叫作模 $m$ 的最小正缩系

于是， $c_1,\cdots,c_{m}$ 为模 $m$ 的完系，等价于说 $\overline{c_1},\cdots,\overline{c_m}$ 恰好是模 $m$ 的全部 $m$ 个同余类；而 $r_1,\cdots,r_{\varphi(m)}$ 是模 $m$ 的缩系，则等价于说 $\overline{r_1},\cdots,\overline{r_{\varphi(m)}}$ 恰好是模 $m$ 的全部 $\varphi(m)$ 个缩同余类，因此，任意两个完(缩)系中的数，将其中一个的顺序适当调整，必然两两模 $m$ 同余.

模 $m$ 的逆

如 $(a,m)=1$ ，则存在 $x$ 使
$ax\equiv1\pmod{m}.$
我们将这样的 $x$ 称为 $a$ 对模 $m$ 的逆，记作 $a^{-1}\pmod{m}$ 或 $a^{-1}$ ，他们形成模 $m$ 的一个同余类（从而在模 $m$ 的意义下唯一）.特别地，有一个 $a^{-1}$ 满足 $1\leqslant a^{-1}<m$

定理

定理一

同余关系是等价关系，即有
(i) （自返性） $a\equiv a\pmod{m}$
(ii) （对称性）如果 $a\equiv b\pmod{m}$ ，则 $b\equiv a\pmod{m}$
(iii) （传递性）如果 $a\equiv b\pmod{m},\,b\equiv c\pmod{m}$ ，则 $a\equiv c\pmod{m}$

定理二

如果 $a\equiv b\pmod{m},\,c\equiv d\pmod{m}$ ，则
(i) $a\pm c\equiv b\pm d\pmod{m}$
(ii) $ac\equiv bd\pmod{m}$ .

定理三

设 $F(x_1,\cdots,x_n)$ 是 $n$ 元整数系数多项式. 如果 $a_i\equiv b_i\pmod{m}\;(1\leqslant i\leqslant n)$ ，则
$F(a_1,\cdots,a_n)\equiv F(b_1,\cdots,b_n)\pmod{m}$

定理四

若
$ac\equiv bc\pmod{m}.$
则 $a\equiv b \pmod{\dfrac{m}{(c,m)}}$ . 特别地，当 $(c,m)=1$ 时，我们有
$a\equiv b\pmod{m}.$

定理五

(i) 如果 $a\equiv b \pmod{m},\;d|m$ ，则 $a\equiv b\pmod{d}$
(ii) 如果 $a\equiv b\pmod{m},\;d\not =0$ ，则 $da\equiv db\pmod{dm}$ . 反之亦然
(iii) 如果 $a\equiv b\pmod{m_i}\;(q\leqslant i\leqslant n)$ ，则 $a\equiv b\pmod{[m_1,\cdots,m_n]}$ ，反之亦然

定理六

设 $(a,m)=1,\,$ $b$ 是任意整数.
(i) 如果 $a_1,\cdots,c_m$ 是模 $m$ 的完系，则 $ac_1+b,\cdots,ac_m+b$ 也是模 $m$ 的完系；
(ii) 如果 $r_1,\cdots,r_{\varphi(m)}$ 是模 $m$ 的缩系，则 $ar_1,\cdots,ar_{\varphi(m)}$ 也是模 $m 的缩系； (iii) 存在$ x $使$ ax\equiv b\pmod{m} $成立，所有这样的$ x $形成模$ m$ 的一个同余类

定理七

设 $(a,m)=(b,m)=1$ ，则
(i) $(ab)^{-1}\equiv a^{-1}\cdot b^{-1}\pmod{m}$ ;
(ii) $a^{-1}\equiv b^{-1}\pmod{m}$ 的充分必要条件是 $a\equiv b\pmod{m}$
(iii) 如果 $r_1,\cdots,r_{\varphi(m)}$ 是模 $m$ 的任一缩系，则它们的逆 $r_!^{-1},\cdots,r_{\varphi(m)}^{-1}$ 也是模 $m$ 的一个缩系.

同余式与同余类

第二章同余