数论线性同余方程-欧拉函数》.pptVIP

一元线性同余方程 形如　　　　　　　（或者形如(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)都是解。即其解可以表示为：x+k*m/(a,m)，其中k为任意整数。 扩展欧几里德辗转相除法 对于x*a+y*b=(a,b)，若已知a,b则可以用下面的算法求得x和y function extend_gcd(a,b:int; var x,y:int): int // x*a+y*b=(a,b) var x1,y1: int 　　if (ab) then 　　　　result:=extend_gcd(b,a,y,x) 　　else if (a=0) then 　　　　result:=b 　　　　x:=0　　　　y:=1 　　else 　　　　result:=extend_gcd(b%a,a,lx,ly) 　　　　x:=ly-lx*b/a　y:=lx 商的模与乘法逆元 但是这有个比较讨厌的条件就是： 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的一个解 商的模与乘法逆元 其实还能更简化，完全可以抛开乘法逆元的概念： b|a且(b,m)m时(a/b)%m的解，就是一元线性同余方程 的解，而这个方程等价于 其中a’=a%m，b’=b%m，于是求b|a时(a/b)%m的解就只需要a’和b’的值了，于是求解过程的中间值就都与m同级别了。 商的模与乘法逆元 那么还剩下的问题就是(b,m)=m时的状况。 一种策略是想办法得到a和b包含的m因子的个数，当a和b都是一列数的连乘时，这个方法是可行的： 首先对m做因式分解。设　　　　若　　　　，则只需要将每个ai包含的mi的因子个数累加一下，最后就能得到a包含的m因子的个数了，并且还可以知道a除开这些因子之外的部分累乘的积模m的结果。 于是当a包含的m的个数大于b时，(a/b)%m=0 否则他们包含的m因子的个数一定相等。可以设b=b’*mk，a=a’*mk ，此时(a/b)%m=(a’/b’)%m，且b’%m0，于是就可以用前几页的方法了。 商的模与乘法逆元 另一种方法是： 设(a/b)%m=x，那么一定存在整数y使得a/b=y*m+x（xm）， 即a=y*m*b+x*b（x*bm*b）， 即a%(m*b)=x*b， 即x=(a%(m*b))/b 当b不是很大时，这个方法是比较好用的，但是若b很大，这个方法就够呛了。 欧拉函数 一元线性同余方程组与中国剩余定理 问题： 如果m1、m2、…、mk两两互质这个条件不满足，怎么办？ 一元线性同余方程组与中国剩余定理 那么可知，这k个一元线性同余方程构成的同余方程组的解就是一元线性同余方程组： 的解。 于是任意个一元线性同余方程构成的同余方程组的求解问题就转化为了包含两个一元线性同余方程的一元线性同余方程组的求解问题了。 一元线性同余方程组与中国剩余定理 对于包含两个一元线性同余方程的一元线性同余方程组 其有解当且仅当(a1-a2)%d=0。 同余方程组与中国剩余定理 实际上若方程组存在解，则一定存在整数p和q满足：a1+m1*p=a2+m2*q 即：p*m1-q*m2=a2-a1 于是根据扩展欧几里得可证明前面的结论，并且也同时给出了解。 同余方程组与中国剩余定理 进而可知方程组的每个解对应了不定方程 p*m1-q*m2=a2-a1的一个解。 而且易知若(p0,q0)是此不定方程的解，则x=a1+m1*p0是原同余方程组的解。 故若p0+k*m2/(m1,m2)是p*m1-q*m2=a2-a1的解。 那么原同余方程组的解就是： a1+m1*(p0+k*m2/(m1,m2)) =a1+m1*p0+k*m1*m2/(m1,m2) =