Chinese remainder theorem

CRT Chinese Remainder Theorem

For mutually prime [$m,n$x \equiv a \pmod{m}, x \equiv b \pmod{n}$time,$x \equiv c \pmod{mn}$Thereexistsonlyone$0 \le c < ab$ that satisfies

Existence of a solution

• c can be obtained by [Extended Euclidean reciprocal division 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
• Find $mx+ny=1$ s $x,y$ by extended Euclidean reciprocal division
• $mx(\mathrm{mod}n)=1,ny(\mathrm{mod}m)=1$, so $bmx+any$ satisfies the condition

Click here for solution uniqueness, etc.

• Chinese Remainder Theorem (CRT) and a summary of problems that use it - Qiita

---

This page is auto-translated from /nishio/中国剰余定理 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.