위키득계정 ↗
과학

중국인의 나머지 정리

중국인의 나머지 정리과학
영문명
Chinese remainder theorem
기본 조건
법들이 쌍마다 서로소
결과
동시 합동식의 해 존재
유일성의 범위
법들의 곱에 대한 합동류
중국인의 나머지 정리는 법들이 쌍마다 서로소일 때 여러 나머지 조건을 동시에 만족하는 정수가 존재하며, 그 법들의 곱을 법으로 하여 유일하다는 정리다.

두 조건을 합치는 예

x를 4로 나누면 나머지가 1이고 7로 나누면 나머지가 3이라고 하자. 17은 두 조건을 모두 만족한다. 4와 7이 서로소이므로 전체 해는 x≡17 (mod 28)로 나타난다.

유일하다는 뜻

17만이 유일한 정수 해라는 뜻은 아니다. 17에 28의 정수배를 더한 45와 −11도 같은 두 나머지 조건을 만족한다. 0 이상 28 미만에서 대표값을 고르면 17 하나로 정해진다.

쌍마다 서로소

법이 세 개 이상이면 전체의 최대공약수가 1이라는 조건만으로는 부족하다. 서로 다른 두 법을 고를 때마다 최대공약수가 1이어야 기본 형태의 정리를 적용할 수 있다.

서로소가 아닐 때

법이 서로소가 아니면 주어진 나머지 조건들이 충돌할 수 있다. x≡0 (mod 4)는 짝수를 요구하지만 x≡1 (mod 6)은 홀수를 요구하므로 두 조건에는 공통 해가 없다. 이때는 조건의 양립 가능성을 별도로 확인해야 한다.

관련 문서

합동식 / 나머지 / 서로소 / 최대공약수 / 최소공배수 / 동치류 / 정수 / 모듈러 역원 / 연립방정식