线性同余方程

一元线性同余方程
定义：a,b是整数，m是正整数，形如 a*x = b (mod m) 且x是未知整数的同余式称为一元线性同余
定理：a,b,m 是整数且m > 0 (a,m) = d,如果d | b,则方程恰有d个模不同余的解，否则方程无解   如 a/d = b/d (mod m/d) 乘以d--> a = b (mod m/d) b一定要是d的倍数方程才有结
由同余方程的定义可得 a*x + m*y = b (y为整数),这个方程称为二元一次不定方程.
怎么解该方程
扩展欧几里德解方程一定有解 a*x + m*y = d = 易做图(a,m) 方程两边同除以d 得到 a*x/d + m*y/d = 1,然后用扩展欧几里德求解该方程x,y.该解也是a*x + m*y = 1 的解方程同除解不变
但是我们要求a*x + m*y = b的解 所以方程两边同乘以b 解得 a*b*x/d + m/d*b*y = b; 等式两边同乘同除结果不变，但是我们要求的是a*x + m*y = b的解x= x /d *b;
这是一个解，怎么求最小正整数解呢？
x 是一个特殊解，a*x/d*b + m/d*b*y = b -- >  a*x/d*b = b (mod m/d)
其他的解都关于m/d与 x 同余。即x≡x+(m/d)*t (mod m)    (0≤t≤d-1)。
解一元线性同余方程组
任何一元同余方程都可变成若干个形如 x = b (mod m)的方程
对于模线性方程组，不管这样的方程有多少个，都可以两两解决，求得方程组的最终解
x = b1 (mod m1)
x= b2 (mod m2)
n1*m1 + b1 = n2*m2 + b2 即  n1*m1 - n2*m2 = b2 -b1
可以用扩展欧几里得n1,n2,从而得出 xs = m1*n1 + b1;想让 x + x = b1 (mod m1) 说明 x是m1的倍数,同理x1+ x = b2 (mod m2) 说明 x是m2的倍数
x1 除 m1 余b1 且是 m2的倍数
x2 除 m2 余b2 且是 m1的倍数
所以最终解一定是lcm(m1,m2)的倍数
x = xs (mod lcm(m1,m2))
再和以后的式子一直求解得到最终解
 
 
 

补充：综合编程 , 其他综合 ,

上一个：optparse模块OptionParser学习
下一个：Matlab基本函数-colormap函数