[정수론 입문 시리즈 17편] 중국인의 나머지 정리

동아리 물품을 3개씩 세면 2개 남고, 5개씩 세면 3개 남고, 7개씩 세면 2개 남습니다. 물품은 최소 몇 개일까요? 놀랍게도 답은 23개입니다.

이 고전 문제는 《손자산경》에 실린 유명한 나머지 문제입니다. 이번 글에서는 이런 여러 나머지 조건을 하나로 합치는 중국인의 나머지 정리를 정리합니다.

What this post covers

• 중국인의 나머지 정리의 정확한 내용을 정리합니다.
• 중국인의 나머지 정리를 실제 예제로 풀어 봅니다.
• 《손자산경》에 나오는 고전적인 나머지 문제를 소개합니다.

이번 글에서 새로 나오는 용어

• 중국인의 나머지 정리 (Chinese Remainder Theorem): 서로소인 법들에 대한 나머지 조건을 하나의 해로 합칠 수 있다는 정리입니다.
• 서로소 (Coprime): 최대공약수가 1인 관계입니다.
• 합동 (Congruence): 같은 나머지를 가지는 관계입니다.

시작 문제: 《손자산경》의 나머지 문제

중국인의 나머지 정리에 대한 최초의 기록은 3세기 후반 또는 4세기 초반 무렵의 중국 수학책에서 찾을 수 있습니다. Silverman 본문에는 다음 문제가 인용되어 있습니다.

“우리는 몇 개의 물건을 가지고 있는데, 정확히 몇 개인지 모른다. 만일 이들을 세 개씩 묶어서 세면 두 개가 남고, 다섯 개씩 묶어 세면 세 개가 남고, 일곱 개씩 묶어 세면 두 개가 남는다. 과연 몇 개가 있을까?”

— 《손자산경》, 약 300년경, 3권 26번 문제

즉 다음 조건을 만족하는 수를 찾는 문제입니다.

$$x\equiv2\pmod3, \qquad x\equiv3\pmod5, \qquad x\equiv2\pmod7.$$

직접 작은 수를 넣어 보면 $x=23$이 가장 작은 양의 해입니다. 왜 이런 답이 하나로 정해지는지 설명해 주는 도구가 중국인의 나머지 정리입니다.

먼저 쉬운 두 조건부터: mod 3, mod 5

처음부터 세 조건을 한꺼번에 보지 말고, 두 조건만 봅시다.

$$x\equiv2\pmod3, \qquad x\equiv3\pmod5.$$

3으로 나누어 2가 남는 수는 2, 5, 8, 11, 14, 17, 20, 23, ...입니다. 이 중 5로 나누어 3이 남는 수는 8, 23, 38, ...입니다.

패턴을 보면 답은 15마다 반복됩니다.

$$x\equiv8\pmod {15}$$

여기서 15는 $3\cdot5$입니다. 두 법 3과 5가 서로소라서, 두 나머지 조건이 mod 15의 한 조건으로 합쳐진 것입니다.

왜 나머지 조건을 합치는가?

앞 글들에서 우리는 하나의 법 $m$에 대한 합동식을 주로 다루었습니다. 하지만 실제 문제에서는 여러 법에 대한 조건이 동시에 주어지는 경우가 많습니다. 예를 들어 어떤 수가 3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는다는 식입니다.

중국인의 나머지 정리는 이런 여러 나머지 조건을 하나의 합동식으로 합칠 수 있는지를 알려 줍니다. 핵심 조건은 법들이 서로소라는 점입니다.

중국인의 나머지 정리

위 실험에서 본 패턴을 공식으로 정리하면 다음과 같습니다.

중국인의 나머지 정리

두 정수 $m,n$이 $\gcd(m,n)=1$을 만족한다고 합시다. 임의의 정수 $b,c$에 대해 연립 합동 방정식

$$x\equiv b\pmod m, \qquad x\equiv c\pmod n$$

은 $0\le x<mn$ 범위에서 정확히 하나의 해를 가집니다.

이 정리는 서로소인 두 법에 대해 각각 원하는 나머지를 지정하면, 그 조건을 동시에 만족하는 수가 $mn$을 법으로 해서 하나만 정해진다는 말입니다.

즉, mod $m$에서의 나머지 정보와 mod $n$에서의 나머지 정보가 서로소 조건 아래에서는 mod $mn$에서 하나의 정보로 정확히 합쳐집니다.

조금 더 큰 예시: $x\equiv8\pmod {11}$, $x\equiv3\pmod {19}$

다음 연립 합동 방정식을 풀어 봅시다.

$$x\equiv8\pmod {11}, \qquad x\equiv3\pmod {19}.$$

첫 번째 합동식의 모든 해는

$$x=11y+8$$

로 쓸 수 있습니다. 이것을 두 번째 합동식에 대입하면

$$11y+8\equiv3\pmod {19}$$

이므로

$$11y\equiv -5\equiv14\pmod {19}$$

입니다. 이 선형 합동식을 풀면

$$y\equiv3\pmod {19}$$

을 얻습니다. 따라서

$$x=11\cdot3+8=41$$

입니다. 실제로

$$41\equiv8\pmod {11}, \qquad 41\equiv3\pmod {19}$$

이고, 모든 해는

$$x\equiv41\pmod {209}$$

입니다.

일반적인 풀이 구조

일반적으로

$$x\equiv b\pmod m, \qquad x\equiv c\pmod n$$

을 풀 때는 먼저 첫 번째 식에서

$$x=my+b$$

라고 둡니다. 이를 두 번째 식에 대입하면

$$my\equiv c-b\pmod n$$

이 됩니다. $\gcd(m,n)=1$이므로 이 선형 합동식은 $0\le y<n$ 범위에서 유일한 해를 가집니다. 그 $y$를 이용해 $x=my+b$를 만들면 원래 연립 합동식의 해가 됩니다.

이 해는 $0\le x<mn$ 범위에서 유일하고, 전체 해는 mod $mn$에서 같은 나머지를 가진 수들의 한 묶음입니다.

Common mistakes

1. 서로소 조건 없이 중국인의 나머지 정리를 그대로 적용하는 실수

중국인의 나머지 정리의 깔끔한 형태는 $\gcd(m,n)=1$일 때입니다. 서로소가 아니면 해가 없을 수도 있고, 있더라도 유일성의 법이 단순히 $mn$이 되지 않습니다.

2. 해 하나만 쓰고 법 $mn$을 잊는 실수

예를 들어 $x=41$만 답이 아니라

$$x\equiv41\pmod {209}$$

가 전체 해입니다.

연습 문제

아래 점검 퀴즈에서 중국인의 나머지 정리를 직접 적용해 보세요.

Wrap-up

이번 글에서는 중국인의 나머지 정리를 통해 서로소인 법들에 대한 나머지 조건을 하나의 해로 합치는 방법을 보았습니다. 핵심은 mod $m$의 정보와 mod $n$의 정보가 서로소 조건 아래에서 mod $mn$의 정보로 정확히 합쳐진다는 점입니다.

다음 글에서는 이런 개수와 약수 구조를 함수처럼 다루는 산술함수 관점으로 넘어가겠습니다.