模和同余 定义：设a，b和m均为整数，且m>0。如果a和b被m除所得的余数相同，那么称a和b关于模m是同余的，记作a≡b mod n. 同于有以下性质： 1.若n|(a-b),则a≡b mod n。 2.若a mod n≡b mod n，则a≡b mod n。 3.a≡a mod n。 4.若a≡b mod n，则b≡a mod n。 5.若 a≡b mod n，b≡c mod n，则aºc mod n。 6.若a≡b mod c，c≡d mod n，则a+cºb+d mod n. 一般的，定义Zn为小于n的所有非负整数集合，即Zn=｛0,1，……，n-1｝，称Zn为模n的同余类集合。Zn中的加法和乘法都为模n运算，具有如下性质： 1.交换率 (w+x)mod n ≡(x+w)mod n ,(w*x)mod n≡(x*w)mod n 2.结合律  [(w+x)+y]mod n≡[w+(x+y)]mod n, [(w*x)*y]mod n≡[w*(x*y)]mod n 3.分配率  [w*(x+y)]mod n≡[(w*x)+(w*y)]mod n 4.单位元  (0+w)mod n≡w mod n, (1*w)mod nºw mod n 5.加法逆元: 对w属于Zn，存在x属于Zn，使得w+x=0 mod n，称x为w的加法逆元，记作x=-w。 6.乘法逆元 : 设w属于Zn，如果存在x属于Zn，使得w*x=1modn，就说w是可逆的，称x为w的乘法逆元，记作x=w ，并不是每个元素都又乘法逆元，可以证明，w属于Zn是可逆的，当且仅当gcd（w，n）=1.如果w是可逆的，则可顶一除法。 费马小定理：设a，p为整数，且p为素数,（p,a）=1, 那么：a^(p-1) ≡1(mod p).    例：当a分别为3与5时，求a^16被17除后所得的余数。 答案：均为1.   模线性方程  ax≡b(mod m)      其中a,b和m是已知的（m>0），要求解出满足上式的对模m的x值。满足同余方程的x可能有多个，也可能一个都没有，上述模线性方程也称为一次同余方程。     例如：57x≡7（mod 11）有一个解x=9，而9x≡7（mod 6）无解。     解：模线性方程ax≡b(mod m)的步骤如下： （1）求 d=gcd（a,m） （2）若d不是b的因数，则ax≡b(mod m)无解，结束；否则转（3） （3）求x0,y0,是a*x0+m*y0=d; （4）由于d是b的因数，将a*x0+m*y0=d改写，得a(x0*(b/d))+m*(y0*(b/d))=b,       于是ax+my=b的一个特解为 x=x0*(b/d),y=y0*(b/d); （5）x0*(b/d)是ax≡（mod m）的一个特解，由此的ax≡b(mod m)的所有解    （共d个）为：x= (x0*(b/d)+ i*(m/d) ) (mod m),    i=0,1,2,3,4.……d-1 定理1：      设d=gcd(a,n)，假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d| b，则方程ax=b(modn)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod(n/d)，最大整数解x2=x1+(d-1)*(n/d)。
定理2：       假设方程ax=b(mod n)有解，且x0是方程的任意一个解，则该方程对模n恰有d个不同的解(d=gcd(a,n))，分别为：xi=x0+i*(n/d) mod n 。   void modeq(int a, int b, int n) // ! n > 0 { int e, i, d, x, y; d = extgcd(a, n, x, y); if (b % d > 0) printf("No answer! "); else { e = (x * (b / d)) % n; for (i = 0; i < d; i++) // !!! here x maybe <0 printf("%d-th ans: %d ", i+1,(e+i*(n/d))%n); } } 参考http://www.cnblogs.com/qq812689440/archive/2011/08/27/2155683.html