[Algorithm] 중국인의 나머지 정리

조재훈·2024년 10월 4일

개요

PS 문제를 풀다가 이런 문제를 발견했다
백준 6064

패턴이 보일랑 말랑하는데 시간을 너무 잡아 먹어서 그냥 도움을 받기로 했다
그런데 처음 들어보는 방법으로 문제를 푸는 것이었음

중국인의 나머지 정리라는 문제같은데 블로그에 한 번 가볍게 남겨보고자 한다

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

위와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 유용한 정리라고 한다. 정수론에서 배운다고 함

서로 다른 모듈로 나누는 여러 합동식을 단일 합동식으로 결합할 수 있음

정수 a, b, m에 대하여 m | (a - b)일 때(a - b가 m으로 나누어 떨어질 때), a는 법 m에 대하여 b와 합동이다라고 한다

기호로는 a ≡ b(mod m)이라고 쓴다. m를 합동의 법이라고 한다

간단히 말해, "a를 m으로 나눈 나머지는 b"라는 문장을 수식으로 표현한 것. a = mk + b

다시 돌아가 중국인의 나머지 정리를 보면

다음과 같은 여러 합동식이 있을 때

이때 이 합동식들을 동시에 만족하는 x가 존재하며, 그 해는 모듈로 M = m1 m2 ... * mn 아래에서 유일하다

즉, 이 시스템은 다음을 만족하는 x를 가진다 => x ≡ a (mod M)
해는 M의 모듈로 유일하며, 이는 M보다 작은 범위에서 해를 구할 수 있음을 의미한다

위의 예시처럼 이런 여러 합동식이 있다고 생각해보자

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

먼저 M = 3 x 5 x 7 = 105를 구한다
각 모듈 값에 대해 Mi = M / mi를 계산한다
- M1 = 105 / 3 = 35
- M2 = 105 / 5 = 21
- M3 = 105 / 7 = 15
각 Mi에 대해 Mi와 mi의 역원을 찾습니다. 이 역원은 Mi * y ≡ 1(mod mi)을 만족하는 y입니다
- 35 * y1 ≡ 1 (mod 3)이 되는 y1 = 2
- 21 * y2 ≡ 1 (mod 5)이 되는 y2 = 1
- 15 * y3 ≡ 1 (mod 7)이 되는 y3 = 1
이제 해를 구하는 식은 다음과 같습니다
- x = a1 x M1 x y1 + a2 x M2 x y2 + a3 x M3 x y3 (mod M)
- x = 2 x 35 x 2 + 3 x 21 x 1 + 2 x 15 x 1 (mod 105)
- x = 233 (mod 105)
x = 23, 그래서 합동식 시스템을 만족하는 해는 x ≡ 23(mod 105) 입니다

사실 이 문제에서 뭐가 중국인의 나머지 정리 부분인지 잘 모르겠지만
이런게 있다 정도로 알고 있으면 될 것 같다

나태지옥