중국인의 나머지 정리(Chinese Remainder Theorem) 기본 이해하기

1. 중국인의 나머지 정리(Chinese Remainder Theorem)

 

정수 $m_{1}, m_{2}, ..., m_{n}$이 임의의 i,j = 1,2,...,n에 대하여 $i \neq j$일때, $m_{i}$와 $m_{j}$가 서로소라면, 즉

 

$$gcd(m_{i}, m_{j}) = 1, i \neq j$$라고 하자.

 

일차연립합동식 $$x \equiv a_{1} (mod m_{1})$$,  $$x \equiv a_{2} (mod m_{2})$$,  $$x \equiv a_{3} (mod m_{3})$$, $$\vdots$$,  $$x \equiv a_{n} (mod m_{n})$$ 의 해는 mod $m_{1}, m_{2}, ..., m_{n}$에 대하여 유일하게 존재한다.

 

 

2. 보조정리 1

 

정수 a,b,k에 대하여 $$1 - ka \times [(ka)^{-1} (mod b)] = b \times [b^{-1} (mod a)]$$

 

여기서 $[a^{-1} (mod m)]$은 m에 대한 a의 곱셈의 역원이다.

 

(증명)

 

곱셈 역원의 정의는, $a \times [a^{-1} (mod m)] \equiv 1$이다.

 

즉, a와 a의 역원 $[a^{-1} (mod m)]$의 곱을 m으로 나눈 나머지가 1이라는 뜻이다.

 

그러므로 $ka \times [(ka)^{-1} mod b] \equiv 1$은 b에 대하여 적당한 정수 p가 존재하여...

 

$$ka \times [(ka)^{-1} mod b] = bp + 1$$로 바꿔쓸수 있다.

 

그런데, $ka \times [(ka)^{-1} mod b]$은 a로 나눈 나머지가 0이다.

 

왜냐하면, $ka \times [(ka)^{-1} mod b]$는, 정수 k, 정수 a, 정수 $[(ka)^{-1} mod b]$의 곱으로 이루어져 있기 때문에, a로 나누면 당연히 나누어 떨어진다.

 

그러므로 다음과 같이 a에 대한 합동식으로 바꿔쓸수 있다.

 

$$bp + 1 \equiv  0 (mod a)$$

 

합동식의 성질에 따라 양변에 -1을 빼도 성립하므로,

 

$$bp \equiv  -1 (mod a)$$

 

양변에 -1을 곱해도 성립하므로...

 

$$b(-p) \equiv 1 (mod a)$$

 

그러므로 -p는 b의 a에 대한 곱셈의 역원 $[b^{-1} mod a]$이고 $$ka \times [(ka)^{-1} mod b] = bp + 1$$으로부터 다음 식이 유도된다.

 

$$1 - ka \times [(ka)^{-1} mod b] = -bp = b \times [b^{-1} mod a]$$

 

 

3. 보조정리 2

 

정수 a,b,m에 대하여...

 

$$[a^{-1} mod m][b^{-1} mod m] = [(ab)^{-1} mod m]$$

 

(증명)

 

곱셈 역원의 정의로부터..

 

$$a \times [a^{-1} mod m] \equiv 1 (mod m)$$

$$b \times [b^{-1} mod m] \equiv 1 (mod m)$$

 

두 식을 곱하면...

 

$$ab \times [a^{-1} mod m][b^{-1} mod m] \equiv 1 (mod m)$$

 

그러므로, ab의 m에 대한 곱셈의 역원은... $[a^{-1} mod m][b^{-1} mod m]$

 

 

4. 중국인의 나머지 정리 해법

 

두 식 $$x \equiv a_{1} (mod m_{1})$$, $$x \equiv a_{2} (mod m_{2})$$을 생각해보자.

 

먼저 첫번째 식으로부터.. x를 $m_{1}$으로 나눈 나머지가 $a_{1}$이므로..

 

$$x = m_{1}k_{1} + a_{1}$$

 

두번째 식에 대입하면..

 

$$m_{1}k_{1} + a_{1} \equiv a_{2} (mod m_{2})$$

 

양변에 $a_{1}$을 빼면...

 

$$m_{1}k_{1} \equiv (a_{2} - a_{1}) (mod m_{2})$$

 

양변에 정수 $m_{1}$의 $m_{2}$에 대한 곱셈의 역원을 곱해주면

 

$$k_{1} \equiv [m_{1}^{-1} mod m_{2}](a_{2}-a_{1}) (mod m_{2})$$

 

위 식은 나머지 식이므로, 등식으로 바꾸면 다음과 같다.

 

$$k_{1} = m_{2}k_{2} + [m_{1}^{-1} mod m_{2}](a_{2} - a_{1})$$

 

이 식을 $x = m_{1}k_{1} + a_{1}$에 대입하면 다음과 같다.

 

$$x = m_{1}m_{2}k_{2} + m_{1}[m_{1}^{-1} mod m_{2}](a_{2} - a_{1}) + a_{1}$$

 

식을 풀어써보면 다음과 같다.

 

$$x = m_{1}m_{2}k_{2} + a_{1} - a_{1}(m_{1}[m_{1}^{-1} mod m_{2}]) + a_{2}m_{1}[m_{1}^{-1} mod m_{2}]$$

 

보조정리 1 $1 - ka \times [(ka)^{-1} (mod b)] = b \times [b^{-1} (mod a)]$에 의하여

 

$$x = m_{1}m_{2}k_{2} + a_{1}(m_{2}[m_{2}^{-1} mod m_{1}]) + a_{2}m_{1}[m_{1}^{-1}mod m_{2}]$$

 

이것을 세번째 식인 $x \equiv a_{3} (mod m_{3})$에 대입하고 보조정리 2를 이용하면 다음을 얻는다고 한다.

 

$$x = m_{1}m_{2}m_{3}k_{3} + m_{2}m_{3}[(m_{2}m_{3})^{-1} mod m_{1}]a_{1} + m_{3}m_{1}[(m_{3}m_{1})^{-1} mod m_{2}]a_{2} + m_{1}m_{2}[(m_{1}m_{2})^{-1} mod m_{3}]a_{3}$$

 

n개의 합동식에 대해 위 과정을 반복하면 다음을 얻는다고 한다.

 

$M = m_{1}m_{2}...m_{n}$이고 이것을 $m_{i}$로 나눈 몫 $M_{i} = M / m_{i}$라고 하자.

 

n개의 연립합동식은 다음과 같은 하나의 합동식으로 나타낼 수 있다.

 

$$x \equiv \sum_{i=1}^{n} M_{i}[M_{i}^{-1} mod m_{i}]a_{i} (mod M)$$

 

 

5. 예시를 통해 이해해보기

 

$$x \equiv 5 (mod 7)$$, $$x \equiv 13 (mod 18)$$, $$x \equiv 21 (mod 29)$$의 x를 구해보자.

 

먼저 $m_{1} = 7$, $m_{2} = 18$, $m_{3} = 29$이고.. 어떤 두 쌍을 잡아도 서로소이다.

 

(7,18)과 (18,29), (7,29)가 서로소이다.

 

세 수의 곱 $M = 7 \times 18 \times 29 = 3654$

 

그리고 $M_{1} = 3654/7 = 522$, $M_{2} = 3654/18 = 203$이고, $M_{3} = 3654/29 = 126$

 

그러면 $[M_{1}^{-1} mod m_{1}]$을 구해야하는데 어떻게 할 수 있을까

 

페르마의 소정리로도 구할 수 있고 확장 유클리드 호제법으로도 구할 수 있다.

 

def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0

    x = 0 
    y = 1

    while b != 0:
        
        q,r = a//b, a%b

        a,b = b,r

        before_x,x = x,before_x - x*q
        before_y,y = y,before_y - y*q
    
    return a,before_x,before_y

 

$522x \equiv 1 (mod 7)$는 다음과 같이 바꿔쓸수 있다.

 

$$522x = 7y + 1$$

 

그러므로, $$522x-7y = 1$$

 

522와 7에 대한 확장 유클리드 알고리즘을 사용하면 x=2를 얻는다.

 

$$[M_{1}^{-1} mod m_{1}] = 2$$

 

비슷한 방식으로 나머지 $M_{2}$, $M_{3}$에 대한 역원은 다음과 같이 구해진다.

 

$$[M_{2}^{-1} mod m_{2}] = 11$$,

 

$$[M_{3}^{-1} mod m_{3}] = 3$$

 

그러므로 $$x \equiv \sum_{i=1}^{n} M_{i}[M_{i}^{-1} mod m_{i}]a_{i} (mod M)$$에 대입하면 다음과 같은 하나의 합동식으로 나타난다.

 

$$x \equiv (522*2*5 + 203*11*13 + 126*3*21) = 42187 \equiv 1993 (mod 3654)$$

 

그래서 연립합동식의 해는 정수 k에 대하여..

 

$$x = 3654k + 1993$$으로 나타낼 수 있다.

 

 

6. 2개의 연립합동식의 해

 

공식을 외우지 못하더라도.. 합동식이 뭔지 알고 있다면 사실 충분히 풀 수 있다.

 

$$x \equiv a_{1} (mod m_{1})$$,

$$x \equiv a_{2} (mod m_{2})$$이라고 하자.

 

첫번째 합동식은 $m_{1}$에 대하여... $x = m_{1}y + a_{1}$인 정수 y가 존재한다.

 

이를 두번째 합동식에 대입하면... $$m_{1}y+a_{1} \equiv a_{2} (mod m_{2})$$

 

양변에 $a_{1}$을 빼면... $$m_{1}y \equiv (a_{2}-a_{1}) (mod m_{2})$$

 

역시 등식으로 바꾸면.. $$m_{1}y = m_{2}k +(a_{2}-a_{1})$$

 

그러므로 다음과 같은 선형 디오판토스 방정식으로 바꿀 수 있다.

 

$$m_{1}y - m_{2}k = a_{2} - a_{1}$$

 

이 선형 디오판토스 방정식의 해법은 다음과 같았다.

 

먼저 $g = gcd(m_{1}, m_{2})$에 대하여, $(a_{2} - a_{1})$가 g의 배수가 아니면 해 (y,k)가 존재하지 않는다.

 

g의 배수라면 (y,k)가 존재하고... 양변을 g로 나눈다.

 

그러면 $m_{1}/g$와 $m_{2}/g$는 서로소이고... $(m_{1}/g)y' + (m_{2}/g)k' = 1$의 해를 확장 유클리드 알고리즘으로 찾는다.

 

그러한 해 y', k'에 대하여... y = ((a_{2}-a_{1})/g)y', k = -((a_{2}-a_{1})/g)k'을 고르면...

 

$$m_{1}y - m_{2}k = a_{2} - a_{1}$$이 된다.

 

따라서, y = ((a_{2}-a_{1})/g)y', k = -((a_{2}-a_{1})/g)k'이 하나의 해가 된다.

 

 

7. $m_{i}$의 쌍들이 서로소가 아닐때

 

위에서 구한 중국인의 나머지 정리의 공식

 

$$x \equiv \sum_{i=1}^{n} M_{i}[M_{i}^{-1} mod m_{i}]a_{i} (mod M)$$의 전제조건은, $m_{1}, m_{2}, ..., m_{n}$의 모든 쌍들이 서로소여야 한다.

 

하지만, 모든 쌍이 서로소인 경우는 극히 드물것이다.

 

실제로 서로소가 아니더라도, 연립합동식을 하나의 합동식으로 나타낼 수 있다.

 

바로 위 6번에 기술한대로...

 

$$x \equiv a_{1} (mod m_{1})$$

$$x \equiv a_{2} (mod m_{2})$$이라고 하자.

 

첫번째 식은 x를 $m_{1}$으로 나눈 나머지가 $a_{1}$이라는 뜻이므로, $$x = m_{1}k_{1} + a_{1}$$을 만족하는 정수 k_{1}이 존재한다.

 

이 식을 두번째 합동식에 넣으면...

 

$$m_{1}k_{1} + a_{1} \equiv a_{2} (mod m_{2})$$

 

양변에 a_{1}을 빼면..

 

$$m_{1}k_{1} \equiv a_{2} - a_{1} (mod m_{2})$$

 

이러한 합동식을 푸는 방법은 이미 배운적이 있다.

 

$m_{1}k_{1}$을 $m_{2}$로 나눈 나머지가 a_{2} - a_{1}이므로...

 

$$m_{1}k_{1} = m_{2}k_{2} + a_{2} - a_{1}$$

 

식을 바꿔쓰면..

 

$$m_{1}k_{1} - m_{2}k_{2} = a_{2} - a_{1}$$의 선형 디오판토스 방정식이 된다.

 

이미 알다시피 $m_{1}$과 $m_{2}$의 최대공약수를 $g=gcd(m_{1}, m_{2})$라고 하자.

 

$a_{2} - a_{1}$이 g의 배수가 아니면, 이 방정식의 해는 존재하지 않는다.

 

g의 배수라면, 방정식의 해가 존재하고..

 

구하는 방법은 $$m_{1}k_{1} - m_{2}k_{2} = a_{2} - a_{1}$$의 양변을 g로 나누면..

 

$\frac{m_{1}}{g}$와 $\frac{m_{2}}{g}$는 서로소이고.. 이들을 이용해서 확장 유클리드 알고리즘을 통해 $k_{1}^{'}, k_{2}^{'}$을 구할 수 있다.

 

이들은 $$\frac{m_{1}}{g}k_{1}^{'} - \frac{m_{2}}{g}k_{2}^{'} = 1$$ 의 특수해이다.

 

그러므로.. $m_{1}/g, m_{2}/g$를 이용한 확장 유클리드 알고리즘으로 $k_{1}^{'}, k_{2}^{'}$을 구하자.

 

만약, $k_{1} = \frac{a_{2}-a_{1}}{g}k_{1}^{'}$, $k_{2} = \frac{a_{2}-a_{1}}{g}k_{2}^{'}$인 $k_{1}$, $k_{2}$를 선택하자.

 

그러면, $k_{1}^{'} = \frac{g}{a_{2}-a_{1}}k_{1}$, $k_{2}^{'} = \frac{g}{a_{2}-a_{1}}k_{2}$이므로,

 

$$\frac{m_{1}}{g}k_{1}^{'} - \frac{m_{2}}{g}k_{2}^{'} = 1$$에 대입하면 다음과 같다.

 

$$m_{1}k_{1} - m_{2}k_{2} = a_{2}-a_{1}$$

 

그러므로  $$x = m_{1}k_{1} + a_{1}$$을 만족하는 x를 찾기 위한 특수해 $k_{1} = \frac{a_{2}-a_{1}}{g}k_{1}^{'}$과 같이 구할 수 있다.

 

이 식의 일반해는 다음과 같이 구할 수 있다.

 

$$m_{1}k_{1} - m_{2}k_{2} = a_{2}-a_{1}$$에서 $m_{1}m_{2}/g$를 더하고 빼면..

 

$$m_{1}(k_{1} + m_{2}/g) -m_{2}(k_{2}+m_{1}/g) = a_{2}-a_{1}$$

 

적당한 정수 p에 대하여... 위 과정을 p번 반복하면

 

$$m_{1}(k_{1} +pm_{2}/g) - m_{2}(k_{2} + pm_{1}/g) = a_{2} - a_{1}$$

 

그러므로, 일반해는 적당한 정수 p에 대하여.. $$k_{1} = \frac{(a_{2}-a_{1})}{g}k_{1}^{'}+ \frac{pm_{2}}{g}$$

 

이것을 $x = m_{1}k_{1} + a_{1}$에 대입하면 다음과 같다.

 

$$x = \frac{m_{1}(a_{2}-a_{1})}{g}k_{1}^{'} + \frac{pm_{1}m_{2}}{g} + a_{1}$$

 

여기서 $g = gcd(m_{1}, m_{2})$이므로, $\frac{m_{1}m_{2}}{g} = lcm(m_{1},m_{2})$이다.

 

그러므로 양변을 $lcm(m_{1}, m_{2})$로 나누면...

 

$$x \equiv \frac{m_{1}(a_{2}-a_{1})}{g}k_{1}^{'} + a_{1} (mod (lcm(m_{1},m_{2})))$$

 

만약에 3개 이상의 연립합동식이 존재한다면..

 

2개씩 합치는 과정을 계속해서 반복하면 된다.

 

그런데, 합치다가 단 1번이라도 해가 존재하지 않는다면..

 

즉 $a_{2} - a_{1}$이 g의 배수가 아니라면... 전체 연립합동식의 해도 존재하지 않는다.

 

 

8. 연습문제

 

23062번: 백남이의 여행 준비의 준비 (acmicpc.net)

23062번: 백남이의 여행 준비의 준비

 

중국인의 나머지 정리를 사용하는 문제

 

 

9. 풀이

 

결국 다음 연립합동식의 해를 구하면 된다.

 

$$x \equiv a (mod A)$$  $$x \equiv b (mod B)$$  $$x \equiv c (mod C)$$

 

당연하지만 A,B,C가 서로소라는 보장은 없다.

 

그러므로 2개씩 합쳐서 반복적으로 합쳐나가면 되겠다.

 

위에서 구한 공식에 맞게 구해

 

from sys import stdin

#확장 유클리드 알고리즘
def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0

    x = 0 
    y = 1

    while b != 0:
        
        q,r = a//b, a%b

        a,b = b,r

        before_x,x = x,before_x-x*q
        before_y,y = y,before_y-y*q
    
    return a,before_x,before_y

#유클리드 알고리즘
def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

T = int(stdin.readline())

for _ in range(T):
    
    A,B,C,a,b,c = map(int,stdin.readline().split())

    m = [0,A,B,C]
    s = [0,a,b,c]

    answer = 0

    for i in range(1,3):

        m_gcd = gcd(m[i],m[i+1])

        if (s[i+1] - s[i]) % m_gcd != 0:

            answer = -1
            break 

        M_gcd,k1,k2 = extended_gcd(m[i]//m_gcd,m[i+1]//m_gcd)
        
        #서로소가 아닐때, 중국인의 나머지 정리 점화식
        s[i+1] = m[i]*(s[i+1]-s[i])*k1//m_gcd + s[i]
        m[i+1] = m[i]*m[i+1]//m_gcd
    
    #s[-1]이 음수일수 있어서 최소의 양수로 바꾸는 과정
    #나머지연산 1번이면 가능
    if answer == 0:            
        
        answer = s[-1] % m[-1]
    
    print(answer)

 

공식에 맞게 반복적으로 합쳐나가는데,

 

합동식 $x \equiv a (mod A)$에서 합치고 나서 얻은 a와 A를 저장해나가면 되겠다.

 

그런데 최종적으로 합치면, 반복문이 끝난건데..

 

그리고 나서 얻은 합동식은 $$x \equiv s[-1] (mod m[-1])$$

 

최소인 자연수 x를 찾아야하는데 그런데, s[-1]이 음수일수 있다.

 

이걸 양수로 바꾸는 방법은? 먼저 m[-1]을 양수가 될때까지 계속 더해준다.

 

    if answer == 0:
        
        if s[-1] < 0:
            
            k = 1

            answer = s[-1]

            while answer <= 0:

                answer += m[-1] 
        
        else:
            
            answer = s[-1]

    print(answer)

 

 

근데 s[-1]이 우연히 매우 작은 음수 -10000000000000000000000000000000이고 m[-1]이 매우 작은 양수 1이라면..

 

10000000000000000000000000000000번 더해야 겨우 0이 되는데

 

여기서 시간이 너무 오래걸린다

 

그것을 바꾸는 방법은 그냥 나머지 연산 1번만 하면 바로 양수로 바뀐다.

 

이 나머지 연산 테크닉은 많이 사용한 적이 있지

 

    if answer == 0:            
        
        answer = s[-1] % m[-1]
    
    print(answer)

 

참조

 

3. 중국인의 나머지 정리 :: rkm0959 (tistory.com)

3. 중국인의 나머지 정리

 

 

중국인의 나머지 정리 (casterian.net)

The Casterian

 

 

중국인의 나머지 정리 - 나무위키 (namu.wiki)

중국인의 나머지 정리 - 나무위키