中国剰余定理

CRT Chinese Remainder Theorem

互いに素な $m, n$ について $x \equiv a (mod m), x \equiv b (mod n)$ の時、 $x \equiv c (mod mn)$ を満たす $0 \leq c < ab$ がただ一つ存在する。

解の存在

cは拡張ユークリッド互除法で求めることができる 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)

src
$m x + n y = 1$ たる $x, y$ を拡張ユークリッド互除法で求める
$m x (mod n) = 1, n y (mod m) = 1$ なので $bm x + an y$ は条件を満たす

解の一意性などはこちら

中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita