連立合同方程式

ちょっと，連立合同方程式を解く必要がでてきたので，実装してみた．

ここで，invMod n p = n^(-1) (mod p)．

-- Input: 互いに素な整数 m1,m2,...,mn, 整数 a1,a2,...,an
-- Output: 連立合同方程式の解 x in Zm s.t. x = ai (mod mi)
congruence :: (Integral a) => [a] -> [a] -> a
congruence ms as = (`mod` m).sum.zipWith3 add as vs $ us
where m = product ms
us = [div m mi | mi <- ms]
vs = zipWith invMod us ms
add a v u = a * v * u

かなり，あっさり．