Chinese Remainder Theorem (CRT) using Python

Chinese Remainder Theorem

Given pairwise coprime positive integers $n_1, n_2, \ldots, n_k$ and arbitrary integers $a_1, a_2, \ldots, a_k$, the system of simultaneous congruences

$$x \equiv a_1 \pmod{n_1}$$

$$ x \equiv a_2 \pmod{n_2}$$

$$ \vdots$$

$$ x \equiv a_k \pmod{n_k}$$

has a solution, and the solution is unique modulo $N = n_1 n_2 \cdots n_k$

 

A general construction to find a solution to a system of congruences using the Chinese remainder theorem:

1. Compute $N = n_1 n_2 \cdots n_k$

2. For each $i=1,2,\cdots,k$, compute $\displaystyle y_i = \frac{N}{n_i}=n_1n_2\cdots n_{i-1}n_{i+1}\cdots n_k$

3. For each $i=1,2,\cdots,k$, compute $z_i \equiv y_i^{-1} \pmod{n_i}$ using Extended Euclid’s algorithm.

 

<Extended Euclidean algorithm>

Let $a$$,b \in Z^{+}$ with $a>b>0$

• $\exists x,y \in Z,$
• $d= gcd(a,b) = ax+by$

4. The integer $x = \displaystyle \sum_{i=1}^{k}a_iy_iz_i$ is a solution to the systhem of congruences, and $x \pmod{N}$ is the unique solution modulo $N$

 

Process to solve systems of congruences with CRT

1. Begin with the congruence with the largest modulus, $x \equiv a_k \pmod{n_k}$.
Re-write it as $x = n_k j_k + a_k$, for some integer $j_k$.

2. Substitute this into the next congruence,
3. $n_k j_k + a_k \equiv a_{k-1} \pmod{n_{k-1}}$.

4. Solve this for $j_k$, then substitute the solved value back into $x = n_k j_k + a_k$.

5. Continue substituting and solving until you get the final $x$ satisfying all congruences.

 

 

Example 1.

\[
\begin{cases}
x \equiv 1 \pmod{3} \\
x \equiv 4 \pmod{5} \\
x \equiv 6 \pmod{7}
\end{cases}
\]

 

Start with the largest modulus: $x \equiv 6 \pmod{7} \Rightarrow x = 7j + 6$

 

Substitute into the next:
$7j + 6 \equiv 4 \pmod{5} \Rightarrow 2j + 1 \equiv 4 \pmod{5} \Rightarrow j \equiv 4 \pmod{5}$

 

So $j = 5k + 4$. Substitute back: $x = 7(5k + 4) + 6 = 35k + 34$

 

Substitute into the last congruence:
$35k + 34 \equiv 1 \pmod{3} \Rightarrow 2k + 1 \equiv 1 \pmod{3} \Rightarrow k \equiv 0 \pmod{3}$

 

So $k = 3l$.

Then $x = 35(3l) + 34 = 105l + 34$

 

Hence the final solution is: $x≡34(mod105)x \equiv 34 \pmod{105}x≡34(mod105)$

 

Answer: $x \equiv 34 \pmod{105}$

 

 

Theorem

A system of linear congruences has solutions if and only if for every pair of congruences within the system,

$\begin{cases}
x \equiv a_i \pmod{n_i} \\
x \equiv a_j \pmod{n_j}
\end{cases}$ , $\quad \Rightarrow \quad
a_i \equiv a_j \pmod{\gcd(n_i, n_j)}.$

Furthermore, if solutions exist, then they are of the form

$x \equiv b \pmod{\operatorname{lcm}(n_1, n_2, \ldots, n_k)}$

for some integer $b$.

 

 

Chinese Remainder Theorem Using Python

1️⃣ Basic Form

다음 시스템을 만족하는 $x$를 찾는 것이 목표다:

$$
\begin{cases}
x \equiv r_1 \pmod{n_1} \\
x \equiv r_2 \pmod{n_2} \\
\vdots \\
x \equiv r_k \pmod{n_k}
\end{cases}
$$

​

여기서

• $r_i$: remainder 
• $n_i$: modulus 

만약 모든 $n_i$가 서로소라면, 전체 해는 다음과 같이 유일하게 주어진다

$$
x \equiv \sum_{i=1}^{k} r_i N_i M_i \pmod{N}
$$

• $N = n_1 n_2 \cdots n_k$
• $N_i = N / n_i$
• $M_i = N_i^{-1} \pmod{n_i}$ (modular inverse)

 

2️⃣ Generalized Case

하지만 실제로는 $n_i$들이 서로소(coprime)가 아닐 수도 있다.  
이 경우, 두 식

$$
\begin{cases}
x \equiv a_1 \pmod{n_1} \\
x \equiv a_2 \pmod{n_2}
\end{cases}
$$

에 대해 solution이 존재하려면 다음 조건이 필요하다:

$$
a_1 \equiv a_2 \pmod{\gcd(n_1, n_2)}.
$$

이 조건이 만족되면,

$$
n_1 t \equiv (a_2 - a_1) \pmod{n_2}
$$

라는 linear congruence을 풀어서 두 식을 하나로 병합할 수 있다.  
이 과정을 반복하면 식이 3개, 4개, 혹은 100개여도 문제없이 해를 구할 수 있다.

 

 

Implementation in Python

from math import gcd

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def chinese_remainder_general(remainders, moduli):
    if len(remainders) != len(moduli):
        return None  

    a1, m1 = remainders[0], moduli[0]

    for i in range(1, len(remainders)):
        a2, m2 = remainders[i], moduli[i]
        g, p, q = extended_gcd(m1, m2)

        if (a2 - a1) % g != 0:
            return None 

        lcm = m1 * m2 // g
        a1 = (a1 + (a2 - a1) // g * p % (m2 // g) * m1) % lcm
        m1 = lcm

    return a1 % m1, m1

# Example
r = [2, 3, 2, 5]
n = [3, 5, 7, 11]
print(chinese_remainder_general(r, n))  # (113, 1155)

 

 

Code Explanation

 

1.  extended_gcd(a, b)

 

> Extended Euclidean Algorithm 
주어진 $a, b$에 대해 $a x + b y = \gcd(a, b)$ 를 만족하는 $(g, x, y)$를 구한다.

이 식은 modular inverse (모듈러 역원)를 찾을 때 핵심이다.

예를 들어, 어떤 수 $a$에 대해 $ax \equiv 1 \pmod{m}$ 을 만족하는 $x$를 찾고 싶을 때,
이건 바로
$a \cdot x + m \cdot y = 1$
의 해를 구하는 문제와 똑같다.

즉, Extended Euclidean Algorithm으로 $(x, y)$를 구하면
그 $x$가 바로 $a$의 모듈러 역원이 된다.

 

$b = 0$이면 $\gcd(a, b) = a$이고, 식은 $a \times 1 + 0 \times 0 = a$  
따라서 $(g, x, y) = (a, 1, 0)$

 

유클리드 알고리즘은 단순히 gcd만을 구하지만,

확장 유클리드 알고리즘은 gcd를 a,b의 선형 결합으로 표현

즉, $b x_1 + (a \bmod b) y_1 = g$ 을 알고 있을 때,  
이를 $a$와 $b$에 대한 식 $a x + b y = g$ 로 바꾸는 것.

나머지는 다음과 같이 쓸 수 있다:

$a \bmod b = a - \left\lfloor \frac{a}{b} \right\rfloor b$

$b x_1 + (a \bmod b) y_1 = g$

$\Rightarrow\ b x_1 + \left(a - \left\lfloor \frac{a}{b} \right\rfloor b \right) y_1 = g$

$\Rightarrow\ a y_1 + b \left(x_1 - \left\lfloor \frac{a}{b} \right\rfloor y_1 \right) = g$

즉, $x = y_1, \quad y = x_1 - \left\lfloor \frac{a}{b} \right\rfloor y_1$

 

 

example)

extended_gcd(30, 12)
 ├── extended_gcd(12, 30 % 12 = 6)
 │     ├── extended_gcd(6, 12 % 6 = 0)
 │     │     └── return (g=6, x=1, y=0)
 │     └── 계산: (a=12, b=6) → (g=6, x=0, y=1)
 └── 계산: (a=30, b=12) → (g=6, x=1, y=-2)

 

 

2. chinese_remainder_general()

 

1. 초기값 설정 

a1, m1 = remainders[0], moduli[0]

• 첫 번째 congruence를 초기 값으로 설정한다.

2. 병합

for i in range(1, len(remainders)):
    a2, m2 = remainders[i], moduli[i]

• 다음 식 $(a_2, m_2)$와 현재 결과 $(x, m)$을 병합한다.

3. 두 모듈러의 관계 확인

g, p, q = extended_gcd(m1, m2)

• 두 모듈러 $m_1, m_2$의 최대공약수 $g$와 $m_1p+m_2q = g$를 만족하는 $(p,q)$를 구함.

4. 해 존재 여부 검사

if (a2 - a1) % g != 0:
    return None

• $a_2 - a_1$가 $\gcd(m_1, m_2)$로 나누어떨어지지 않으면 해가 존재하지 않는다.

\[
x \equiv a_1 \pmod{m}, \qquad x \equiv a_2 \pmod{m_2}
\]

이 두 식을 동시에 만족하려면 반드시

\[
(a_2 - a_1) \text{이 } g = \gcd(m_1, m_2) \text{의 배수여야 한다.}
\]

 

 

• 만약 나눠떨어지면 → 해 존재함
• 안 나눠떨어지면 → 서로 모순이라 해 없음

 

5. 새로운 해 계산

lcm = m1 * m2 // g
a1 = (a1 + (a2 - a1) // g * p % (m2 // g) * m1) % lcm
m1 = lcm

 

(1) 최소 공배수 구하기

$lcm = \frac{m_1 ×m_2}{g}$

-> 새 모듈러는 두 모듈러의 최소공배수

 

(2) $x = a_1 + \dfrac{(a_2 - a_1)}{g} \times p \times m_1$

 

1️⃣ 먼저 첫 번째 식에서
$x \equiv a_1 \pmod{m_1} \Rightarrow x = a_1 + m_1 k$

 

2️⃣ 이걸 두 번째 식에 대입하면
$a_1 + m_1k \equiv a_2 \pmod{m_2} \Rightarrow m_1 k \equiv (a_2 - a_1) \pmod{m_2}$

 

3️⃣ 확장 유클리드 알고리즘으로
$m p + m_2 q = g$를 구하면 $m p \equiv g \pmod{m_2}$ 이므로,

 

양변을 $g$로 나누면
$k \equiv \dfrac{(a_2 - a_1)}{g} \times p \pmod{\dfrac{m_2}{g}}$

 

4️⃣ 다시 $x = a_1 + m_1 k$ 를 대입하면
최종적으로 $x = a_1 + \dfrac{(a_2 - a_1)}{g} \times p \times m_1$이 된다.

 

6. 최종 결과 

return x % m, m

 

• 반환값 $(x, m)$은 모든 해가 $x + k m$ ($k \in \mathbb{Z}$)의 형태로 표현됨을 의미한다.