1. 求解模线性方程
费马小定理:设a,p为正整数,且p为素数,(p,a)=1,那么a^(p-1)≡1 (mod p)
剩余类:对于整数a及模m,则集合A={x|x≡a(mod m)}称为模m关于a的一个剩余类
简化剩余系:设m为正整数,在与m互质的所有剩余类中,每一个类中取一个数,构成一个集合X,则X称为模m的一个简化剩余系。
模线性方程ax≡b(mod m)的解:
化为ax+my=b
(1) 求d=gcd(a,m)
(2) 若d是b的因数,继续(3)。否则无解
(3) 求ax0+my0=d
(4) x=x0*b/d; y=y0*a/d;
(5) x=(x+k*m/d) (mod m) 所以x一共有d个值,分别为k取0,1,2,3~d-1
2. 求 mod m的逆元
对......
阅读全文