• 数学虽然有点枯燥，但是算法考到最后还是数学，计算机学到最后还是考验逻辑，没有逻辑、算法和数据结构的支撑学计算机是走不远的。

同余

同余的定义

  • 整除和带余除法可以说是数论的基础。而同余则就是数论的重点中的重点。
  • 这里就先介绍一下同余的概念。

同余的定义:

给定一个正整数，把它叫做模.如果用m去除任意两个整数a,b所得的余数相同,则称a,b模m同余，记作a≡b(mod m).如果余数不同，则称a,b对模m不同余,记作a≢b(mod m)\begin{array}{l} \text{给定一个正整数，把它叫做模.}\\如果用m去除任意两个整数a,b所得的余数相同, 则称a,b模m同余，记作a\equiv b(mod ~m).\\ 如果余数不同，则称a,b对模m不同余,记作a\not\equiv b(mod~m) \end{array}

练习1

  • 从这个练习中可以看到同余的几个运算性质，接下来会介绍。

image-20241212161937459

image-20241212162902758

同余的基本性质

  • 接下来要介绍一下，一些简单的同余性质。并介绍一个定理（同余定义的另一种形式），最后再导出同余的运算法则（可以抽象成群）
  • 接下来介绍一个命题和一个定理。

命题1：命题1在前面的练习1中多少也了解到

整数对模m的同余关系是一个等价关系，即(1)a≡a(mod m)   (自反性)(2)若a≡b(mod m),则b≡a(mod m)   (对称性)(3)若a≡b(mod m),b≡c(mod m),则a≡c(mod m)   (传递性)\begin{array}{l} 整数对模m的同余关系是一个等价关系，即\\ (1)a\equiv a(mod~m)~~~(自反性)\\ (2)若a\equiv b(mod~m),则b\equiv a(mod~m)~~~(对称性)\\ (3)若a\equiv b(mod~m),b\equiv c(mod~m),则a\equiv c(mod~m)~~~(传递性) \end{array}

定理1：

整数a,b对模m同余的充要条件是m∣a−b，即a=b+mt，t∈Z\begin{array}{l} 整数a,b对模m同余的充要条件是m\mid a-b，即a=b+mt，t∈Z \end{array}

  • 由命题1和定理1就能推导出同余的运算法则，进而导出命题2、命题3

命题2：命题2得到的就是同余的加减运算

(1)若a1≡b1(mod m),a2≡b2(mod m),则a1+a2≡b1+b2(mod m);(2)若a+b≡c(mod m),则a≡c−b(mod m)\begin{array}{l} (1)若a_1\equiv b_1(mod~m),a_2\equiv b_2(mod~m),则a_1+a_2\equiv b_1+b_2(mod~m);\\ (2)若a+b\equiv c(mod~m),则a\equiv c-b(mod~m) \end{array}

命题3：命题3得到的是同余的乘法运算

若a1≡b1(mod m),a2≡b2(mod m)，则a1a2≡b1b2(mod m)特别地：(1)若a≡b(mod m),则ak≡bk(mod m)(2)若a≡b(mod m),则an≡bn(mod m)\begin{array}{l} 若a_1\equiv b_1(mod~m),a_2\equiv b_2(mod~m)，则a_1a_2\equiv b_1b_2(mod~m)\\ 特别地：\\ (1)若a\equiv b(mod~m),则ak\equiv bk(mod~m)\\ (2)若a\equiv b(mod~m),则a^n\equiv b^n(mod~m) \end{array}

命题4：

若a≡b (mod n)且a=a1d,b=b1d,(d,m)=1,则a1≡b (mod m)\begin{array}{l} 若a\equiv b~(mod~n)且a=a_1d,b=b_1d,(d,m)=1,则a_1\equiv b_~(mod~m) \end{array}

命题5：

(1)若a≡b (mod m),k＞0,则ak≡bk (mod mk)(2)若a≡b (mod m),d是a,b及m的任意正公因数,则ad≡bd (mod md)\begin{array}{l} (1)若a\equiv b~(mod~m),k＞0,则ak \equiv bk ~(mod ~mk)\\ (2)若a \equiv b~(mod~m),d是a,b及m的任意正公因数,则\frac{a}{d} \equiv \frac{b}{d}~(mod~\frac{m}{d}) \end{array}

命题6：

若a≡b (mod mi),i=1,2,3,⋅⋅⋅,k则a≡b(mod [m1,m2,m3,⋅⋅⋅,mk])\begin{array}{l} 若a \equiv b~(mod~m_i),i=1,2,3,···,k则a\equiv b(mod~[m_1,m_2,m_3,···,m_k]) \end{array}

命题7：

若a≡b ( mod m),d∣m且d>0,则a≡b(mod d)\begin{array}{l} 若a\equiv b~(~mod~m),d\mid m且d>0,则a \equiv b(mod~d) \end{array}

命题8：

若a≡b ( mod m),则(a,m)=(b,m)因而若d能整除m及a，b二数之一,则d必能整除a,b中的另一个\begin{array}{l} 若a\equiv b~(~mod~m),则(a,m)=(b,m)\\因而若d能整除m及a，b二数之一,则d必能整除a,b中的另一个 \end{array}

定理2：

若Aα1⋅⋅⋅A\begin{array}{l} 若A_{\alpha_1}···A \end{array}

剩余类及完全剩余系