随笔-21  评论-10  文章-21  trackbacks-0
对于方程组
  • 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 阅读(1171) 评论(0)  编辑 收藏 引用 所属分类: 一次同余

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理