對于方程組
- 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 閱讀(1288)
評論(0) 編輯 收藏 引用 所屬分類:
一次同余