中国剰余定理

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$ がただ一つ存在する。

解の存在

• 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
• $mx + ny = 1$たる$x, y$ を拡張ユークリッド互除法で求める
• $mx \pmod{n} = 1, ny \pmod{m} = 1$なので$bmx + any$は条件を満たす

解の一意性などはこちら

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