求解线性模方程的一般步骤：ax+ny=b; 1.求d=gcd(a,n),如果b%n!=0，则不存在解 2.用扩展欧几里德求ax+ny=d的一个解x0，则方程ax+ny=b的一个解是x=x0*b/d（该方程共有d个不同的解，分别为xi=x0+i*(n/d)，其中i=0,1,2,...,d-1） 注：这里求出一个解其实也可以用求逆元的方法，方程两边同时除以d，得到a'x+n'y=b',这时候x0=b'*(a'模n下的逆元) 3.特别的，最小解是x1=(x0%(n/d)+n/d)%(n/d)，最大解是x2=x1+(d-1)*(n/d);   其中用到了几个定理： 定理一：若gcd(a, b) = 1，则方程ax ≡ c (mod b)在[0, b-1]上有唯一解。 证明：由定理一知，总可以找到或正或负的整数k和l使a*k + b*l = gcd(a, b) = 1，即我们可以求出ax ≡ 1 (mod b)的解x0。当然，两边乘以c有a(cx0) ≡ c (mod b)，所以有x = cx0就是ax ≡ c (mod b)的解。由于加上或减去若干倍b都是该方程的解，所以x在[0, b-1]上有解。那么怎样确定它的唯一性呢？我花了一个小时终于证明出来了，证明方法就是，假设x1和x2都是[0, b-1]上的解，那么就有ax1 ≡ c (mod b)，ax2 ≡ c (mod b)，两式相减就有a(x1-x2) ≡ 0 (mod b)，即a(x1-x2)可以被b整除。但gcd(a, b) = 1啊！所以a和b之间没有共同的语言可以交流，所以只能说(x1-x2)被b整除了。但x1和x2都在[0, b-1]上，所以x1-x2也在[0, b-1]上，所以只能说x1-x2=0了，因此x1=x2。这就证明了解的唯一性！ 定理二：若gcd(a, b) = d，则方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解。 证明：上面说过，这个该死的方程等价于ax + by = c，如果有解，两边同除以d，就有a/d * x + b/d * y = c/d，即a/d * x ≡ c/d (mod b/d)，显然gcd(a/d, b/d) = 1，所以由定理二知道x在[0, b/d - 1]上有唯一解。所以ax + by = c的x在[0, b/d - 1]上有唯一解，即ax ≡ c (mod b)在[0, b/d - 1]上有唯一解，得证   上面两个定理来自：http://www.cnblogs.com/comeon4mydream/archive/2011/07/18/2109060.html 代码就不贴了，网上一大把