중국인의 나머지 정리

참고문헌 

나무위키 

https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC

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

중국인의 나머지 정리의 핵심 질문은 다음과 같다.

`3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?`

그러한 x를 찾기위해 1, 2, 3 ... 다 넣어보자 ㅋㅋ.. 내가 찾은 것은 23이다. 만약 23을 찾았다 하여도 다른 해도 존재한다고 하자. 그렇다면 23의 다음 숫자인 24부터 찾아야 할 것이다.  

위 질문을 만족하는 x는 여러개가 존재하는 것 처럼 보이지만 실제론 유일하다(mod 에서만, 위 예는 128, 233 등 만족하지만 mod 105 에는 모두 23 이다.). 중국인의 나머지 정리의 정확한 뜻은 다음과 같다. 

m_1, m_2, ... m_n이 쌍마다 서로 소(gcd(m_i,m_j) = 1, i != j) 이면, 다음 연립 합동식

x == a_1(mod m_1) 
x == a_2(mod m_2)
x == a_3(mod m_3)
...
x == a_n(mod m_n)   - 식 (1)

은 법 m_1m_2...m_n 에 대하여 유일한 해를 갖는다.  (유일한 해를 갖는다는 건 이해하는데 법 m_1m_2..m_n 이라는 표현은 정확히 무슨 표현인지 모르겠다. 추측하건데 m_1~m_n 까지만 고려했을 때만을 엄격하게 강조하는 뜻인가?)

어쨌든 위 질문에서 3 과 5와 7은 서로소이므로, 해를 하나를 찾으면 그 것이 유일한 해라는 것이다. 

* 해가 존재한다는 존재성의 증명

m = m_1m_2...m_n라고 하자. 단, m_1,m_2,...,m_n은 서로소이다. 또, n_k = m/m_k 라고 놓자. 즉, n_k는 m_k를 제외한 나머지 m_i들의 곱을 의미한다. 이때, gcd(n_k,m_k)는 1이다. 베주항등식(*, 나도 증명은 이해못했음 수 a, b 와 두 수의 gcd(a,b) = g 는 다음과 같이 표현할 수 있다고함. ax+by = g 여기서 x, y는 정수)에 의해 n_k*x_k + m_k*y_k = 1 를 만족하는 정수 x_k, y_k가 존재한다. 이를 합동식 형태로 고치면 n_k*x_k = 1 (mod m_k)이다.

이제 x=a_1*n_1*x_1 + a_2*n_2*x_2 + ... + a_n*n_n*s_n라 하자. j != k 이면 m_k | n_j 이고( n_i의 정의에 따라) 따라서 다음을 만족한다. x = a_k*n_k*s_k = a_k *1 = a_k (mod m_k) 이다. 즉 x는 주어진 연립 합동식의 한 해이다.  

* 해가 유일하다는 유일성의 증명

x, y 가 주어진 연립 합동식의 해라고 하자. 그렇다면 두 수 모두 식 (1)을 만족한다. 그렇다면 임의의 k에 대하여 x = a_k = y (mod m_k) 이고, 그래서 x-y = 0 (mod m_k) 이다. 즉, x-y는 모든 m_k들의 배수이다. 따라서 m_1*m_2*...m_n | (x-y)이고, x = y (mod m_1*m_2*...*m_n) 이고 주어진 연립 합동식의 해가 유일함을 보인다. 

 

증명파트는 ...-_-;;이해가 어렵다. 쓰고 다시 읽고 쓰고 다시 읽어보자.

* 문제를 푸는 방법, 존재성의 증명하는 것과 비슷

맨 위에 보았던 문제 `3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?` 예를 들어 푸는 방법을 제시한다.

m_1*m_2*m_3 = 105 이고, n_1 = 105/3 = 35 , n_2 = 105/5 = 21, n_3 = 105/7 = 15 이다. 

n_1*x_1 = 35*x_1 = 2*x_1 = 1 (mod 3)
n_2*x_2 = 21*x_2 = x_2 = 1 (mod 5)
n_3*x_3 = 15*x_3 = x_3 = 1 (mod 7) 

을 풀면 x_1 = 2, x_2 = x_3 =1 임을 알 수 있다. 그러므로, x= a_1*n_1*x_1 + a_2*n_2*x_2 + a_3*n_3*x_3 = 2*35*2 + 3*21 + 2* 15 = 233 = 23 (mod 105) 이다. 따라서 x = 23 (mod 105)가 주어진 연립 합동식의 해이다.