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

同余

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

同余的定义:
$$
\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中多少也了解到
$$
\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：
$$
\begin{array}{l}
整数a,b对模m同余的充要条件是m\mid a-b，即a=b+mt，t∈Z
\end{array}
$$

命题2：命题2得到的就是同余的加减运算
$$
\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得到的是同余的乘法运算
$$
\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：
$$
\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：
$$
\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：
$$
\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：
$$
\begin{array}{l}
若a\equiv b~(~mod~m),d\mid m且d>0,则a \equiv b(mod~d)
\end{array}
$$
命题8：
$$
\begin{array}{l}
若a\equiv b~(~mod~m),则(a,m)=(b,m)\因而若d能整除m及a，b二数之一,则d必能整除a,b中的另一个
\end{array}
$$
定理2：
$$
\begin{array}{l}
若A_{\alpha_1}···A
\end{array}
$$

剩余类及完全剩余系

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

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

定义2：

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

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

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

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

定理1：

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

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

定理2：

设$m\in Z+,(a,m)=1,b\in Z$，若x通过模m的一个完全剩余系，则$ax+b$也通过模m的完全剩余系。也就是说若$x_0,x_1,…,x_{m-1}$是模m的完全剩余系，则$ax_0+b,ax_1+b,…,ax_{m-1}+b$也是模m的完全剩余系

定理3：

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

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

既约剩余系与欧拉函数

欧拉函数的定义：

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

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

既约剩余系的定义：

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

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

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

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

命题1：

设$n\in Z$，则$(1,n)=1$，$(n-1,n)=1$

命题2：

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

  1. $\phi(n)=1$，当且仅当$n=1,2$
  2. $\phi(n)≥2$，当且仅当$n≥3$
  3. 欧拉函数$\phi(n)$不是单调函数
  4. 若p是素数，则$\phi(p)=p-1$
  5. 若p是素数，则$\phi(p^n)=p^n-p^{n-1}$
  6. 设$a=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}$，则$\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^{\phi(m)}\equiv1~(~mod~m)$

推理1(费马小定理)：

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

RSA体制