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

同余

  • 整除和带余除法可以说是数论的基础。而同余则就是数论的重点中的重点。

同余的定义:

给定一个正整数，把它叫做模.如果用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：命题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}

命题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}

剩余类及完全剩余系

定义1(剩余类和完全剩余系)：

定理1中的K0,K1,...,Km−1K_0,K_1,...,K_{m-1}叫做模m的剩余类，一个剩余类中任一数叫做它同类的数的剩余，若a0,a1,...,am−1a_0,a_1,...,a_{m-1}是m个整数，并且其中任何两个数都不在同一个剩余类中，则a0,a1,...,am−1a_0,a_1,...,a_{m-1}叫做模m的一个完全剩余系

定义2：

0,1,...,m-1这m个整数叫做模m的最小非负完全剩余系。

当m是偶数时−m2,...,−1,0,1,...,m2−1-\frac{m}{2},...,-1,0,1,...,\frac{m}{2}-1或者是−m2+1,....,−1,0,1,.....,m−12-\frac{m}{2}+1,....,-1,0,1,.....,\frac{m-1}{2}叫做模m的绝对最小完全剩余系。

当m是奇数时−m−12,...,−1,0,1,...,m−12-\frac{m-1}{2},...,-1,0,1,...,\frac{m-1}{2}叫做模m的绝对最小剩余系

注解：这里的最小表示间隔最小，绝对表示的值最小

定理1：

设m∈Z+m\in Z_+，则全部整数可以分成m个集合，记作K0,K1,...,Km−1K_0,K_1,...,K_{m-1}，其中Kr(r=0,1,,...,m−1)K_r(r=0,1,,...,m-1)是由一切形如qm+r,q∈Zqm+r,q\in Z的整数组成的，这些集合具有下列性质

  1. 每一个整数必须包含而且仅在上述的一个集合里面
  2. 两个整数同在一个集合的充要条件是这两个整数对模m同余

定理2：

设m∈Z+,(a,m)=1,b∈Zm\in Z+,(a,m)=1,b\in Z，若x通过模m的一个完全剩余系，则ax+bax+b也通过模m的完全剩余系。也就是说若x0,x1,...,xm−1x_0,x_1,...,x_{m-1}是模m的完全剩余系，则ax0+b,ax1+b,...,axm−1+bax_0+b,ax_1+b,...,ax_{m-1}+b也是模m的完全剩余系

定理3：

若m，n是互素的两个正整数，而x，y分别通过模m，n的完全剩余系，则nx+mynx+my通过mn的完全剩余系。

注解：nxi+myr,i∈{0,1,...,m−1},r∈{0,1,...,n−1}nx_{i}+my_{r},i\in\{0,1,...,m-1\},r\in\{0,1,...,n-1\}，只有每个都计算后它的个数才会是mn。

既约剩余系与欧拉函数

欧拉函数的定义：

设n∈Z+n\in Z_+，在0、1、2、...、n-1中与n互素的数的个数叫做n的欧拉函数，记作ϕ(n)\phi(n)

注意：欧拉函数是Z+→Z+Z_+\rightarrow Z_+的函数，前面是该函数的定义域，后面称为陪域。

既约剩余系的定义：

如果一个模m的剩余类里面的数与m互素，就把它叫做一个与模m互素的剩余类，在与模m互素的全部剩余类中，从每一个各任取一数所作成的数的集合，叫做m的一个既约剩余系

例子1：对于m=10来说，1、3、7、9是与10互素的，所以10的一个既约剩余系其实就是集合{1,3,7,9}\{1,3,7,9\}

例子2：对于m=11来说，1~10都是与11互素的，所以11的一个既约剩余系其实就是集合{1,2,3,4,5,6,7,8,9,10}\{1,2,3,4,5,6,7,8,9,10\}

  • 欧拉函数有以下几个运算性质：

命题1：

设n∈Zn\in Z，则(1,n)=1(1,n)=1，(n−1,n)=1(n-1,n)=1

命题2：

设ϕ(n)\phi(n)是欧拉函数，则有如下性质：

  1. ϕ(n)=1\phi(n)=1，当且仅当n=1,2n=1,2
  2. ϕ(n)≥2\phi(n)≥2，当且仅当n≥3n≥3
  3. 欧拉函数ϕ(n)\phi(n)不是单调函数
  4. 若p是素数，则ϕ(p)=p−1\phi(p)=p-1
  5. 若p是素数，则ϕ(pn)=pn−pn−1\phi(p^n)=p^n-p^{n-1}
  6. 设a=p1α1p2α2...pkαka=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}，则ϕ(a)=a(1−1p1)(1−1p2)...(1−1pk)\phi(a)=a(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})

欧拉定理、费马定理及其对循环小数的应用

定理1(欧拉定理)：

设m是大于1的整数，(a,m)=1,则aϕ(m)≡1 ( mod m)a^{\phi(m)}\equiv1~(~mod~m)

推理1(费马小定理)：

若p是素数，则ap=a mod( p)a^{p}=a~mod(~p)，或者ap−1≡1 mod( p)a^{p-1}\equiv1~mod(~p)

RSA体制