对于方程组
- x = a (mod p)
- x = b (mod q)
其中p, q互素。
可以采用中国剩余定理，
x = q * Eq * a + p * Ep * b (mod pq ) , 其中 Eq * q + Ep * p = 1;
而模不互素的情况，却有类似的形式：
- x = a (mod pd)
- x = b (mod qd)
其中p, q互素, d > 1。
如果d 不整除 a - b, 则无解, 否则
x = q * Eq * a + p * Ep * b ( mod pqd ) , 其中 Eq * q + Ep * p = 1;
可以验算这个构造解是适合上面两个方程的。
比如验算第一个方程：
首先变形得到 x = (1 - Ep * p ) * a + Ep * p * b (mod pd);
又有：x = a + Ep * p *( b - a ) (mod pd);
又有：d | (b - a) 所以 pd | p*(b - a)
所以 x = a ( mod pd )
也可以证明x 模上 pqd 具有唯一解
posted on 2010-07-28 11:09
wangzhihao 阅读(1232)
评论(0) 编辑 收藏 引用 所属分类:
一次同余