中国剰余定理
CRT Chinese Remainder Theorem 互いに素な$ m, nについて
$ x \equiv a \pmod{m}, x \equiv b \pmod{n}
の時、
$ x \equiv c \pmod{mn}
を満たす$ 0 \le c < ab がただ一つ存在する。
解の存在
code:python
def crt(a, m, b, n):
"""
Find x s.t. x % m == a and x % n == b
>> crt(2, 3, 1, 5)
11
>> crt(1, 4, 3, 6)
9
"""
x, y, g = extended_euclidean(m, n)
if g == 1:
return (b * m * x + a * n * y) % (m * n)
s = (b - a) // g
return (a + s * m * x) % (m * n // g)
$ mx + ny = 1たる$ x, y を拡張ユークリッド互除法で求める
$ mx \pmod{n} = 1, ny \pmod{m} = 1なので$ bmx + anyは条件を満たす
解の一意性などはこちら