算法数学知识需用定理

费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，即a和b两个数互质，则有a^(p-1)≡1(mod p)。

---

裴蜀定理

裴蜀定理(或贝祖定理)得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程(称为裴蜀等式)：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.

---

 算数基本定理

算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。最早证明是由欧几里得给出的，由陈述证明。此定理可推广至更一般的交换代数和代数数论。

---

容斥定理

在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

两个集合的容斥关系公式：A∪B =|A∪B| = |A|+|B| - |A∩B |

三个集合的容斥关系公式：|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|

四个集合的容斥关系公式：A∪B∪C∪D=A+B+C+D - A∩B - B∩C  -  C∩A -  A∩D  -  B∩D  -  C∩D + A∩B∩C + A∩B∩D  + A∩C∩D  + B∩C∩D  -  A∩B∩C∩D 

n个集合的容斥关系公式：

---

中国剩余定理

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：

有解的判定条件，并用 构造法给出了在有解情况下解的具体形式。中国剩余定理说明：假设 整数m1,m2, ... ,mn 两两互质，则对任意的整数：a1,a2, ... ,an，方程组

有解，并且通解可以用如下方式构造得到：设

设

---

初等变换

线性方程组

所谓一般线性方程组，是指形式为：

的方程组，其中，

初等变换

一般采用消元法来解线性方程组，而消元法实际上是反复对方程进行变换，而所做的变换也只是以下三种基本的变换所构成：

(1)用一非零的数乘以某一方程

(2)把一个方程的倍数加到另一个方程

(3)互换两个方程的位置

于是，将变换(1)、(2)、(3)称为线性方程组的初等变换。

矩阵的初等变换又分为矩阵的初等行变换和矩阵的初等列变换。矩阵的初等行变换和初等列变换统称为初等变换。另外： 分块矩阵也可以定义初等变换。

定义：如果B可以由A经过一系列初等变换得到，则称矩阵A与B称为等价  。

初等行变换

定义：所谓数域P上矩阵的初等行变换是指下列3种变换：

1)以P中一个非零的数乘矩阵的某一行

2)把矩阵的某一行的c倍加到另一行，这里c是P中的任意一个数

3)互换矩阵中两行的位置

一般来说，一个矩阵经过初等行变换后就变成了另一个矩阵，当矩阵A经过初等行变换变成矩阵B时，一般写作

可以证明：任意一个矩阵经过一系列初等行变换总能变成 阶梯型矩阵。

初等列变换

同样地，定义初等列变换，即：

1)以P中一个非零的数乘矩阵的某一列

2)把矩阵的某一列的c倍加到另一列，这里c是P中的任意一个数

3)互换矩阵中两列的位置

初等矩阵

定义：由单位矩阵E经过一次初等变换得到的矩阵称为初等矩阵引理：

对一个

---

 欧拉函数

欧拉函数通式：

(其中p1, p2……pn为x的所有 质因数 ，x是不为0的整数)

定义 φ(1)=1(和1互质的数(小于等于1)就是1本身)。

注意：每种质因数只有一个。

若n是质数p的k次幂，，因为除了p的倍数外，其他数都跟n互质。

比如12=2*2*3那么φ(12)=φ(4*3)=φ(2^2*3^1)=(2^2-2^1)*(3^1-3^0)=4

设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值

φ：N→N，n→φ(n)称为欧拉函数。

欧拉函数是 积性函数——若m,n互质，

, 证明与上述类似。

若n为质数则