同余类的运算

2019-10-16 本文已影响0人洛玖言

第二章同余

同余类的运算

加法零元

我们将模 $m$ 的同余类 $\overline{a+b}$ 称为同余类 $\bar{a}$ 与 $\bar{b}$ 之和，表示成
$\bar{a}+\bar{b}=\overline{a+b}$
如果我们在 $\bar{a}，\bar{b}$ 中分别取另外两个元素 $a',\,b'$ ，则 $a\equiv a'\pmod{m},\,b\equiv b'\pmod{m}$ ，从而
$a+b\equiv a'+b'\pmod{m}$

于是有 $\overline{a+b}\equiv \overline{a'+b'}$ . 这表明，同余类 $\overline{a+b}$ 与我们对 $\bar{a},\,\bar{b}$ 的代表元的选取无关，即上面定义的和 $\bar{a}+\bar{b}$ 是由同余类 $\bar{a},\,\bar{b}$ 唯一确定的.

满足结合律和交换律，又同余类 $\bar{0}$ 具有这样的性质：对任意 $\bar{a}\in Z_m,\,\bar{0}+\bar{a}=\bar{a}$ ，并且方程 $\bar{x}+\bar{a}=\bar{0}$ 在 $Z_m$ 有唯一的解
$\bar{x}=\overline{-a}$

我们通常将 $\bar{0}$ 称为 $Z_m$ 中的加法零元，而将 $\overline{-a}$ 称作 $\bar{a}$ 的加法逆元，并记作 $-\bar{a}$ . 于是对任意 $\bar{a},\,\bar{b}\in Z_m$ , 方程 $\bar{x}+\bar{a}=\bar{b}$ 有唯一的解
$\bar{x}=\bar{b}-\bar{a}$
所以， $Z_m$ 中可以作加法的逆运算——减法. 于是 $Z_m$ 对于加法形成一个群，叫做模m的加法群，这是由 $m$ 个元素构成的有限群

设 $\bar{a},\,\bar{b}\in Z_m$ ，我们将 $m$ 的同余类 $\overline{ab}$ 称为同余类 $\bar{a}$ 与 $\bar{b}$ 的积，表示成
$\bar{a}\cdot\bar{b}=\overline{ab}.$
与前面类似地， $\bar{a}\cdot\bar{b}$ 同样是唯一确定的.

满足结合律和交换律，并且乘法与加法还满足分配律，对于任意的 $\bar{a}\in Z_m,\,\bar{1}\cdot\bar{a}=\bar{a}$ . 我们因此将 $\bar{1}$ 称为 $Z_m$ 中的乘法单位. 代数学，满足上述（加、减、乘法）三种运算和运算律的集合叫做交换环，模 $m$ 的 $m$ 个同余类组成的集合，叫做模 $m$ 的同余类环

在 $Z_m$ 中，方程 $\bar{x}\cdot\bar{a}=\bar{1}$ 并非对每个 $\bar{a}\in Z_m\,(\bar{a}\not=\bar{0})$ 有解，即 $\bar{a}$ 在 $Z_m$ 中不一定总有乘法逆

比如，在 $Z_6$ 中就不存在 $\bar{x}$ ，使 $\bar{2}\cdot\bar{x}=\bar{1}$ ，意味着 $2x\equiv1\pmod{6}$ 显然不存在.

$Z_6$ 中的元素 $\bar{2}$ 没有逆的原因，在于它是 $Z_6$ 中的所谓零因子. 一般地， $Z_m$ 中的元素 $\bar{x}$ 称为 $Z_m$ 中的零因子，是指 $\bar{x}\not=\bar{0}$ ，但存在 $\bar{y}\in Z_m,\,y\not=0$ 使 $\bar{x}\cdot\bar{y}=\bar{0}$ . 同样的 $\bar{y}$ 也是 $Z_m$ 中的零因子.

如果 $\bar{x}$ 是 $Z_m$ 中的零因子，则 $\bar{x}$ 在 $Z_m$ 中便不可能有乘法逆. 因如果存在 $\bar{z}$ 使 $\bar{x}\cdot\bar{y}=\bar{1}$ ，又设 $\bar{y}\not=0$ 使 $\bar{x}\cdot\bar{y}=\bar{0}$ ，则产生
$\bar{y}=(\bar{x}\cdot\bar{z})\cdot\bar{y}=(\bar{x\cdot\bar{y}})\cdot\bar{z}=\bar{0}\cdot\bar{z}=\bar{0}$

模 $m$ 的 $\varphi(m)$ 个缩同余类构成的集合 $Z_m^{*}$ 形成交换的乘法群

首先，两个缩同余类之积仍是缩同余类，即 $Z_m^{*}$ 对乘法封闭. 又 $Z_m^{*}$ 是 $Z_m$ 的子集，所以 $Z_m^{*}$ 中乘法仍满足结合律和交换律；而同余类 $\bar{1}$ 显然是 $Z_m^{*}$ 中的乘法单位，所以对于每个 $\bar{a} \in Z_m^{*}$ ，方程 $\bar{x}\cdot\bar{a}=\bar{1}$ 有唯一的解

$\bar{x}=\overline{a^{-1}}$

称为 $\bar{a}$ 的乘法逆元，我们将 $\overline{a^{-1}}$ 记作 $\bar{a}^{-1}$ ，于是，对于任意 $\bar{a},\,\bar{b}\in Z_m^{*}$ ，方程 $\bar{a}\cdot\bar{x}=\bar{b}$ 有唯一的解
$\bar{x}=\bar{b}\cdot\bar{a}^{-1}\;$ （也可以成 $\dfrac{ \bar{ b }}{ \bar{ a }}$ ）

换句话说，只有模 $m$ 的缩同余类才可以作‘分母‘. 于是，在 $Z_m^{*}$ 中可以作除法运算. 特别当 $m$ 为素数 $p$ 时， $Z_p$ 中除 $\bar{0}$ 之外，其他 $p-1$ 个同余类均是缩同余类，因此其中可以作加减乘除四则运算（当然 $\bar{0}$ 不能作为分母），这样的集合叫做域. 现在我们对于每个素数 $p$ ，给出了由模 $p$ 的 $p$ 个同余类构成的有限域.

Wilson 定理

设 $p$ 是素数，则
$(p-1)!\equiv -1\pmod{p}$

$p=2$ 时结论显然成立. 设 $p\geqslant3$ ，由于对模 $p$ 的任一缩同余类 $\bar{a}$ ，存在唯一的逆 $\bar{a}^{-1}$ ，满足
$\bar{a}\cdot\bar{a}^{-1}=\bar{1}$

而 $\bar{a}=\bar{a}^{-1}$ 等价于 $\bar{a}^2=\bar{1}$ ，即 $\bar{a}=\bar{1}$ 或 $\bar{a}=\overline{p-1}$ . 于是 $p-3$ 个同余类 $\bar{2},\bar{3},\cdots,\overline{p-2}$ 可按互逆配成 $\dfrac{p-3}{2}$ 个对. 因此