modと中国剰余定理など

蟻本他を参考にした。

与えられたa,b,mから
ax≡b(mod m)
を満たすxを求めたいとする。
このとき
ay≡1(mod m)
なるyが求まれば

y*ax≡y*b(mod m)
   x≡y*b(mod m)(∵ay≡1)

としてxを求めることができる。

ay≡1(mod m)⇔∃k(ay=1+km)

であるから変形して

ay-mk=1

であり、これは拡張ユークリッドの互除法で求められる。

簡単のため、式が2本の場合を考える

X mod m1 = a
X mod m2 = b
(m1,m2は互いに素)

なるm1,m2,a,bが与えられており、Xを求めたいとする。
ここで、中国人剰余定理は

X = (m2 * a * mod_inverse(m2,m1) + m1 * b * mod_inverse(m1,m2))%(m1*m2)

で求められるというもの。
中国の剰余定理 - Wikipedia
ここで、mod_inverse(m2,m1)及びmod_inverse(m1,m2)はextgcd(m1,m2,p,q)で求められる。
これはextgcd(m1,m2,p,q)は

p*m1 + q*m2 = 1
p*m1 ≡ 1(mod m2)
q*m2 ≡ 1(mod m1)

と変形でき、p,qがそれぞれの逆元になっていることが解る。

Isa@Diary