[정수론 입문 시리즈 15편] 중국인의 나머지 정리는 여러 합동식을 어떻게 한 번에 풀까?

지금까지는 하나의 합동식

$$ax \equiv b \pmod n$$

을 다뤘습니다. 그런데 실제 문제에서는 서로 다른 mod 조건이 한꺼번에 주어질 때가 많습니다. 예를 들면 어떤 수가 3으로 나누면 2가 남고, 5로 나누면 1이 남는 수를 찾는 식입니다. 이런 문제를 체계적으로 다루는 정리가 중국인의 나머지 정리입니다.

What this post covers

• 중국인의 나머지 정리가 무엇을 말하는지 설명합니다.
• 서로소 조건이 왜 중요한지 이해합니다.
• 간단한 예시로 해를 실제로 구해 봅니다.
• 다음 단계인 페르마 소정리와 오일러 정리로 넘어갈 준비를 합니다.

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

• 중국인의 나머지 정리 (Chinese Remainder Theorem): 서로소인 여러 mod 조건을 하나의 해로 합칠 수 있다는 정리입니다.
• 합동 (Congruence): 같은 나머지를 가지는 관계입니다.
• 모듈러 역원 (Modular Inverse): 모듈러 세계에서 곱해서 1이 되는 수입니다.
• 서로소 (Coprime): 최대공약수가 1인 관계입니다.

가장 기본적인 형태

예를 들어 다음 조건을 동시에 만족하는 $x$를 찾고 싶다고 합시다.

$$x \equiv 2 \pmod 3$$ $$x \equiv 1 \pmod 5$$

이 두 법 3과 5는 서로소입니다. 중국인의 나머지 정리는 이런 경우 해가 존재하며, 그 해는 $3 \times 5 = 15$를 법으로 해서 하나의 합동류로 유일하게 정리된다고 말합니다.

직접 찾아 보면

3으로 나누면 2가 남는 수는

2, 5, 8, 11, 14, ...

입니다.

이 가운데 5로 나누면 1이 남는 수를 찾으면 11이 나옵니다. 따라서

$$x \equiv 11 \pmod {15}$$

입니다.

즉, 11, 26, 41, ...이 모두 해입니다.

왜 서로소 조건이 중요할까?

서로소 조건은 각 mod가 서로 독립적으로 움직이게 해 줍니다. 법들이 서로소이면 한쪽 조건을 맞추면서 다른 쪽 조건까지 함께 조정할 수 있습니다.

반대로 서로소가 아니면 조건들이 충돌할 수 있고, 해가 있더라도 정리가 가장 깔끔한 형태로 바로 적용되지는 않습니다. 예를 들어

$$x \equiv 0 \pmod 2, \qquad x \equiv 1 \pmod 2$$

같은 식은 동시에 성립할 수 없습니다. 입문 단계에서는 우선 "법들이 서로소일 때 중국인의 나머지 정리가 가장 깨끗하게 작동한다"고 이해하면 충분합니다.

구성의 아이디어는 무엇일까?

중국인의 나머지 정리의 계산 아이디어는 “한 조건에는 맞고 다른 조건에서는 0처럼 행동하는 조각”을 만드는 것입니다.

예를 들어 mod 3과 mod 5를 함께 다룰 때

• 5의 배수는 mod 5에서 0처럼 보이고
• 3의 배수는 mod 3에서 0처럼 보입니다.

여기에 모듈러 역원을 적절히 곱하면 원하는 나머지를 맞출 수 있습니다.

입문 단계에서는 이 아이디어를 느끼는 것만으로도 충분합니다. 자세한 일반 공식은 나중에 다시 다뤄도 됩니다. 여기서 중요한 것은 중국인의 나머지 정리가 단순 대입 요령이 아니라, 여러 합동 조건을 한 개의 합동류로 묶는 구조라는 점입니다.

예시 하나 더

다음을 동시에 만족하는 $x$를 찾아 봅시다.

$$x \equiv 1 \pmod 4$$ $$x \equiv 2 \pmod 3$$

4로 나누면 1이 남는 수는 1, 5, 9, 13, ...이고, 이 가운데 3으로 나누면 2가 남는 수는 5입니다. 따라서

$$x \equiv 5 \pmod {12}$$

입니다.

Common mistakes

1. 서로소 조건 없이 무조건 적용하는 실수

입문 단계에서는 mod들이 서로소일 때만 안전하게 생각하는 것이 좋습니다.

2. 해를 하나 찾고 주기를 쓰지 않는 실수

중국인의 나머지 정리의 해는 보통 하나의 수가 아니라 곱한 법을 기준으로 한 합동류입니다.

3. 직접 대입만 하다가 구조를 놓치는 실수

작은 수에서는 대입으로도 풀리지만, 정리의 핵심은 조건들을 한 해로 묶어 주는 구조입니다.

Wrap-up

이번 글에서는 중국인의 나머지 정리를 통해 서로소인 여러 합동식을 하나의 해로 묶을 수 있다는 점을 정리했습니다. 이는 합동식 세계가 단순 계산을 넘어 구조적인 문제 해결 도구라는 점을 보여 줍니다.

다음 글부터는 시리즈의 마지막 단계로 들어가, 거듭제곱이 반복되는 모듈러 계산을 정리해 주는 페르마 소정리를 살펴보겠습니다.