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

중국인의 나머지 정리에 대해서 알아봅시다.

이게 나올때마다 헷갈려서 이번기회에 확실히 정리하고 넘어가야 겠습니다. ㅎ

우선 위키피디아를 살펴볼까요?

---

서로 소인 자연수 n1, n2, … , nk와 임의의 정수 a1, a2, … , ak가 있을 때, 임의의 i(1 ≤ i ≤ k)에 대해 

x ≡ ai (mod ni)

로 표현되는 변수 x의 연립 합동 방정식에 대해, 이 방정식이 성립하는 값 x=a가 항상 존재하며, 또한 그 값은 n1 n2 … nk의 나머지값 안에서 유일하게 존재한다. 즉, 방정식의 해는 모두 x ≡ a (mod n1 n2 … nk)로

표현가능하다.

---

이해가 되나요? 아마 "이게 대체 뭔소리야" 라고 하시는 분이 많을 것 같은데요..

그럼 간단한 예를 들어서 설명하겠습니다.

어떤 사람의 나이를 x라고 하고 그 x가 5로 나누면 1이되고 7로 나누면 2, 9로 나누면 7이 된다고 가정합시다. 이때 중국인의 나머지 정리를 이용해서 x를 쉽게 구할 수 있습니다.

목적은 확실해졌죠?

그럼 좀더 수학적으로 설명해봅시다.

n1, n2, … , nk는 서로 소이고, N = n1·n2·n3 … nk라고 합시다. 각 j = 1,2,  …, k에 대해 합동식 u·(N/ni) = 1 (mod ni)의 해를 u = mi라고 합시다.  그러면 연립 합동식,

x = r1 (mod n1)

x = r2 (mod n2)

 …   …   …

x = rk (mod nk)

의 일반해는 다음과 같습니다.

x  = m1·(N/n1) + m2·(N/n2) + … + mk·(N/nk) (mod N)

아직도 뭐가뭔지 이해하기 힘드실텐데 확실한건 마지막에 x값을 구하는 식이 나왔다는거죠.

그럼 위의 예를 적용해볼까요?

예제를 연립 합동식으로 표현하면 다음과 같습니다.

x = 1 mod 5

x = 2 mod 7

x = 7 mod 9

ni 값들은 5, 7, 9이고 ri값들은 1, 2, 7 이 됩니다. 그럼 mi 값은?

계산을 해야죠. u·(N/ni) = 1 (mod ni) 식에 적용해봅시다.

u·(5·7·9/5) = 1 (mod 5)  -> u·7·9 = 1 (mod 5) -> u·3 = 1 (mod 5) (좌변에 mod 5를 취한 결과) 

결과식을 만족하는 u의 최소값은 2가 될 것입니다. 따라서 m1 = 2 가 됩니다.

이와 같은 방법으로 m2 = 3, m3 = 2를 구할 수가 있습니다.

그러므로 x = 2·9·7 + 3·5·9 + 2·5·7 (mod 5·7·9) = 331

어떤 사람의 나이는 331살 이네요 ㅎㄷㄷ;;

아..아니군요 결과에 mod를 안취했네요 ㅎㅎㅎ

어떤 사람의 나이는 331 (mod 5·7·9) = 16 살이군요^^;

어때요? 이렇게 정리하고 나니까

참 쉽죠?