Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

中国剰余定理で2式の場合の解を求める

中国剰余定理とは、2式の場合 m_1, m_2を互いに素とするとき、
 x = a_1 \mod m_1
 x = a_2 \mod m_2
を満たす整数xが 0 \le x \lt m_1 m_2の範囲内にただ一つ存在するというものです。
xの求め方はこうです。
まず m_1 p + m_2 q = 1を満たす(p, q)のセットを一つ求めます。
以下のアルゴリズムを用います。

37x+10y = 1 を拡張されたユークリッドの互除法で解いてみる - Pebble Coding

求まったpを用いて、解は、
x = a_1 + (a_2 - a_1) m_1 pとなります。
なお、qを用いて、 x = a_1 + (a_2 - a_1)(1 - m_2 q)でもよいです。
ここでxが 0 \le x \lt m_1 m_2の範囲にない場合は、 m_1 m_2の倍数を加えて、範囲内に持ってこればよいです。

プライバシーポリシー

お問い合わせ

スポンサーリンク