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)로 표현가능하다. 이해가 되나요? 아마 "이게 대체 뭔소리야" 라고 하시는 분이 많을 것 같은데요.. 그럼 간단한 예를 들어서 설명하겠습니다. 어떤 사람의 나이를 ..
