1、数论李子星 同余 欧拉函数 与欧拉定理，费马小定理 中国剩余定理同余 定义： 如果 a%m=b%m，那么就称 a与 b同余 a=a%m， b=b%m 结论： 同余是等价关系（自反，对称，传递性） (a+b)%m = (a+b)%m (a-b)%m = (a-b)%m (a*b)%m = (a*b)%m (a/b)%m 不一定等于 (a/b)%m，即便满足 b|a的条件 这就出现了一个问题：若我们知道 a能整除 b，又能够很容易得得到 a%m和 b%m的结果，但 a和 b都太大了以至于 a/b算起来代价太高， (a/b)%m怎么算。商的模与乘法逆元 定义： 若 (b*b)%m=1， b就称为 b
2、对于模 m的乘法逆元。 结论： 对于 b和 m， b对于模 m的乘法逆元不一定存在。 若 (b,m)=1，则 b一定存在乘法逆元，否则一定不存在。 若 b|a，且 (b,m)=1，则 (a/b)%m的结果可以利用 b的乘法逆元 b来求： (a/b)%m=(a*b)%m。 证明：设 a=b*k，则有 (a/b)%m = k%m = (k*1)%m = (k*(b*b)%m = (k*b*b)%m = (a*b)%m 若 a对于模 k存在乘法逆元 a，则对于任意的 b和 c有：商的模与乘法逆元 于是，我们有了一个比较好用的结论了： 如果我们知道 a/b的结果是一个整数，而且 b与 m互质，那么计算
3、 (a/b)%m时可以避免掉做大数的除法，通过一些小于 m的数的四则运算就可以得到结果。 关键是要得到 b对于模 m的乘法逆元。 而乘法逆元的计算可以用扩展欧几里得算法求得。一元线性同余方程形如 （或者形如 (a*x)%m=b，其中a,m,b为已知量）的方程被称为一元线性同余方程。例如乘法逆元满足的条件 (b*b)%m=1就是一个一元 线性同余方程 。若 x满足 (a*x)%m=b则一定存在整数 k使得x*a+k*m=b（一）一元线性同余方程 (a*x)%m=b有解当且仅当(a,m)|b成立。（二）若 x是一元线性同余方程 (a*x)%m=b的解，则x+m/(a,m)和 x-m/(a,m)都是
4、解。即其解可以表示为：x+k*m/(a,m)，其中 k为任意整数。扩展欧几里德辗转相除法对于 x*a+y*b=(a,b)，若已知 a,b则可以用下面的算法求得 x和 yfunction extend_gcd(a,b:int; var x,y:int): int / x*a+y*b=(a,b) var x1,y1: intif (ab) then result:=extend_gcd(b,a,y,x)else if (a=0) thenresult:=bx:=0 y:=1elseresult:=extend_gcd(b%a,a,lx,ly)x:=ly-lx*b/a y:=lx令 b=a*k+t则
5、t*lx+a*ly=d=a*x+b*y=a*x+a*k*y+t*y=t*y+a*(x+k*y)故y=lxx+k*y=lyx=ly-lx*k=ly-lx*b/a商的模与乘法逆元 但是这有个比较讨厌的条件就是： b必须与 m互质。 如果这个条件不满足，之前的问题还能漂亮的解决么？商的模与乘法逆元若 b|a，且 ，那么若，则有 。于是就又回到了一元线性同余方程上面来了。我们已经知道这个同余方程有解当且仅当(b,m)|a成立，且当此成立时一定有无穷多个以 m/(b,m)为公差的解，且给出一个解就能够得到所有的解，而要得到一个解只需要用扩展欧几里德辗转相除法就行。商的模与乘法逆元于是 (b,m)即便大于 1，也同样可以解决问题。扩展一下乘法逆元的概念，定义：若 (x*a)%m=(a,m)，则称 x为 a对于模 m的乘法逆元 。若 b对于模 m的乘法逆元是 b，那么b*a/(b,m)就是 b|a时 (a/b)%m的一个解
