[정수론] - 중국인의 나머지정리

중국인의 나머지 정리

연립 합동식의 유일한 공통해를 찾는 정리

r 개의 서로 다른 서로소인 양의 정수 n1, n2, ... , nr에 대하여 연립 선형 합동식

x ≡ a1 (mod n1)

x ≡ a2 (mod n2)

.

.

.

x ≡ ar (mod nr)

mod n1n2...nr에 대하여 유일한 공통 해를 가진다

 

예시

x ≡ 2 (mod 3) → a --- (1)

x ≡ 3 (mod 5) → b --- (2)

x ≡ 1 (mod 7) → c --- (3)

 

각 a, b, c를 세 연립 합동식의 해라고 하고,

중국인의 나머지 정리를 증명하기 위해

x ≡ a + b + c (mod 3·5·7) --- (4)

로 둘 수 있다

 

식 (1)을 만족하기 위해 a는 3으로 모듈러 연산을 하였을 때 0이 되면 안되고,

마찬가지로 식 (2), (3)도 각각 5와 7로 나누어 떨어지지 않아야 한다.

즉,

a = 5·7a'

b = 3·7b'

c = 3·5c'

로 나타낼 수 있다.

 

따라서 식 (4)를 다시 적어보면,

x ≡ 35a' + 21b' + 15c' (mod 3·5·7) --- (5)

로 적을 수 있다.

 

식 (5)를 이용해 식 (1), (2), (3)을 풀려면, 다시말해

35a' ≡ 2 (mod 3)

21b' ≡ 3 (mod 5)

15c' ≡ 1 (mod 7)

에 해당하는 a', b' c'를 구하려면 곱셈의 역원을 찾아야한다.

 

곱셈의 역원은 페르마의 소정리나 확장 유클리드 알고리즘으로 찾을 수 있다. 두 개념은 따로 블로그로 정리하고 지금은 바로 역원을 구하면,

35n ≡ 1 (mod 3) → 2

21n ≡ 1 (mod 5) → 1

15n ≡ 1 (mod 7) → 1

이다.

 

따라서,

a' = 4

b' = 3

c' = 1

이고 이제 최종적으로 세 연립 합동식의 유일해를 구하면

 

x ≡ 35·4 + 21·3 + 15·1 (mod 105)

  ≡ 219 mod 105

  ≡ 8

이다.

 

정리

최종적으로 활용하려면 연립 합동식들의 모듈러 연산이 각각 서로소인지 확인하고 맞다면 예시와 같은 순으로 적용하면 된다!

사실.. 백준 6064번 카잉 달력에 알고리즘 분류에 있길래 공부하고 코딩하려고 이 개념에 대하여 공부하게 됐는데, 이 정리를 쓸쯤에야.. 이 문제는 서로소가 아닌 것도 모듈러 연산에 사용된다는 것을 방금 알아 버렸다.. 하하 그래도 공부했으니까 이득~..