几个数学定理

下面要介绍的数学定理，都很重要，不过也很简单。

欧几里德算法以及扩展欧几里德算法 ：

就是以前学过的辗转相除法，简而言之，a和b（a>b）的最大公约数，就是a模b的结果，和b求得的最大公约数（即gcd(a,b)=gcd(a mod b,b)），这个过程一直递归下去，直到a或b等于0，则非零的另一个数就是最大公约数。
而扩展欧几里德算法，则是说如果，对a，b以及二者的最大公约数，有ax+by=gcd(a,b)，这里x，y可能有若干对。扩展欧几里德算法常用来求解多项式的逆元，这个我们之后会提到。

欧拉定理

设一个函数f（欧拉函数），f(n)的结果为比n小的，与n互质的数的个数，则对任意一个整数a，若gcd(a,n)=1，有a^f(n) mod n=1.
证明：

设集合X={x1,x2,.......,xf(n)},为与n互质，比n小的数的集合，共f(n)个
而X'={a*x1 mod n,a*x2 mod n,........, a*xf(n) mod n} 共f(n)个
因为gcd(a,n)==1,
所以a*x 与n互质，
又因为X'元素都比n小
所以X=X'
所以集合X中元素的乘积模n 结果等于 X'中元素的乘积模n
提取出a的f(n)次方，两边消去X中元素的乘积
得出a^f(n) mod n=1

欧拉定理有一个很有用的用处是求逆元，a*a^(f(n)-1) mod n=1，可以改写为a*b mod n=1,所以a在模n的有限域的乘法逆元b就等于 a^(f(n)-1) mod n

费马小定理

对于一个素数p，有a^(p-1) mod p=1
费马小定理是欧拉定理的一个特例，证明不再重复

中国剩余定理

有方程组:
求X的值
解法:

其中，M为若干个mi的乘积，ti为M/mi在有限域mi上的乘法逆元
所以，这个问题就分解成了求若干个乘法逆元、求积、求和的问题，而最难的求乘法逆元的方法，就是上面提到的欧拉定理

单变量线性同余

有ax=b mod n，求x
解：

求出gcd(a,n)=d,若d可被b整除，则有d个解，否则无解
另a'=a/d,b'=b/d,n'=n/d
x'=(a')^-1 * b' mod n'(这里(a')^-1 表示a' 在模n'的有限域内的乘法逆元)
x0=x',xt=x0+n/d *t (mod n) t取值从0到d-1