중국인의 나머지 정리(CRT) 계산기 — 연립 합동식 풀기
x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)… 형태의 연립 합동식을 중국인의 나머지 정리로 풉니다. 법(모듈러스)들이 서로소인지 자동으로 검증하고, 가장 작은 음이 아닌 해와 일반해를 구합니다.
계산 예시: 손자산경의 「미지수 문제」
중국인의 나머지 정리의 기원으로 여겨지는, 3~5세기경 중국의 수학서 『손자산경』에 나오는 고전적인 문제입니다. 「3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 수는 무엇인가」라는 질문의 답은 105를 법으로 하여 23입니다.
| 조건1 | x ≡ 2 (mod 3) |
|---|---|
| 조건2 | x ≡ 3 (mod 5) |
| 조건3 | x ≡ 2 (mod 7) |
| 해 | x ≡ 23 (mod 105) |
중국인의 나머지 정리(CRT)란
중국인의 나머지 정리는 **‘3으로 나누면 2 남고, 5로 나누면 3 남고, 7로 나누면 2 남는 수는 무엇인가’**와 같은 연립 합동식을 푸는 정리입니다. 법이 모두 서로소이면, 법의 곱을 법으로 하는 범위에서 오직 하나의 해가 정해집니다. 이 도구는 합동식을 최대 5개까지 넣어 최소의 음이 아닌 정수 해와 일반해를 구합니다.
**이 도구는 법이 모두 서로소인 ‘고전적인’ 꼴만 다룹니다.** 어느 두 법에 1보다 큰 공약수가 있으면 풀 수 없어 그러한 뜻의 오류가 납니다(서로소가 아닌 경우의 일반화 중국인의 나머지 정리는 범위 밖입니다). **법은 2 이상의 정수**이며, 나머지는 저절로 0 이상 그 법 미만으로 정규화되므로 법 이상의 값이나 음수를 넣으셔도 됩니다. 내부는 다배정도 정수이므로 자릿수의 제한이 없습니다.
중국인의 나머지 정리 계산기 사용 방법
- 나머지와 법을 입력합니다 합동식 하나마다 나머지 a와 법 n을 넣습니다. x ≡ a (mod n)의 꼴에 대응합니다.
- 합동식을 늘립니다 ‘합동식 추가’로 최대 5개까지 늘어놓으실 수 있습니다. 개수가 늘면 해의 유일성이 지켜지는 범위(법의 곱)도 커집니다.
- 해를 구합니다 ‘풀기’를 누르시면 최소의 음이 아닌 정수 해와, 법의 곱을 법으로 하는 일반해가 나옵니다.
- 계산 과정을 좇습니다 각 합동식에 대해 Nᵢ(법의 곱에서 자기 법을 뺀 것)와 Mᵢ(Nᵢ의 역원)가 늘어섭니다. 손으로 셈한 답을 맞춰 보기에 쓰실 수 있습니다.
- 서로소가 아니면 풀 수 없습니다 ‘법이 서로소가 아니다’라고 나오면, 예컨대 4와 6처럼 공약수를 지닌 법이 섞여 있습니다. 조합을 다시 보아 주세요.
더 잘 활용하기 위한 팁
- 법（nᵢ）들이 서로소가 아니면 오류가 발생합니다. 예를 들어 mod 4와 mod 6은 최대공약수가 2이므로 이 계산기로는 풀 수 없습니다（일반화된 중국인의 나머지 정리가 필요한 경우입니다）。
- 나머지 aᵢ가 법 nᵢ보다 크거나 음수여도 괜찮습니다. 내부적으로 자동으로 mod nᵢ 값으로 정규화한 뒤 계산합니다.
- 합동식은 2개에서 5개까지 추가할 수 있습니다. 세 가지 이상의 주기적 조건을 동시에 만족하는 수를 찾는 「병사의 수 맞히기」와 같은 문제에도 응용할 수 있습니다.
- 결과의 일반해는 x ≡ 해 (mod N) 형태로 표시됩니다. N의 정수배를 더한 어떤 수든 원래의 모든 조건을 만족합니다.
중국인의 나머지 정리가 도움이 되는 상황
정수론 연습이나 시험 준비
손으로 푼 답을 확인하는 데 쓰실 수 있습니다. Nᵢ·Mᵢ의 중간값도 나오므로, 어디서 틀렸는지를 좁히실 수 있습니다.
암호 알고리즘을 배우실 때
RSA 복호를 빠르게 하는 CRT 최적화는 이 정리를 그대로 씁니다. 구조를 수치로 좇으실 수 있습니다.
주기의 겹침을 구하실 때
서로 다른 주기로 되풀이되는 일이 동시에 일어나는 시각은, 연립 합동식으로 나타낼 수 있습니다.
고전적인 문제를 되짚으실 때
『손자산경』의 ‘물부지기수’(3으로 2 남고, 5로 3 남고, 7로 2 남는 수)는 105를 법으로 23입니다. 그대로 넣어 확인하실 수 있습니다.
관련된 정수론 도구를 쓰고 싶으실 때
역원이나 합동식 자체는 합동식·모듈러 계산, 최대공약수는 최대공약수·최소공배수, 소인수분해는 소인수분해에서 다루실 수 있습니다.
중국인의 나머지 정리에 관한 용어집
- 중국인의 나머지 정리(CRT)
- 법이 서로소인 연립 합동식에, 법의 곱을 법으로 하는 유일한 해가 존재함을 말하는 정리입니다.
- 합동식
- x ≡ a (mod n) 꼴의 식으로, ‘x를 n으로 나눈 나머지가 a와 같음’을 나타냅니다.
- 법(모듈러스)
- 나누는 수입니다. 이 도구에서는 2 이상의 정수로 한합니다.
- 서로소
- 두 정수의 최대공약수가 1임을 말합니다. 고전적인 CRT는 어느 두 법을 잡아도 서로소일 것을 요구합니다.
- 쌍마다 서로소
- 셋 이상의 수에 대해, 어느 둘을 꺼내어도 서로소임을 말합니다. 전체의 최대공약수가 1이어도 쌍마다 서로소가 아닌 경우가 있습니다.
- 모듈러 역원
- a·x ≡ 1 (mod n)을 채우는 x입니다. CRT에서는 Nᵢ의 역원 Mᵢ를 구하는 자리에서 씁니다.
- 확장 유클리드 호제법
- 최대공약수와 함께 베주 계수를 구하는 셈법입니다. 모듈러 역원의 계산에 쓰입니다.
- 일반해
- 최소의 음이 아닌 정수 해에 법의 곱의 정수배를 더한 것 모두입니다. x ≡ 23 (mod 105) 같은 꼴로 나타냅니다.
자주 묻는 질문
여담 ― 3세기의 수학서에서 RSA 암호 고속화까지
중국인의 나머지 정리의 기원은 3세기에서 5세기경 성립된 것으로 여겨지는 중국의 수학서 『손자산경(孫子算經)』에 실린 「미지수 문제」로 거슬러 올라갑니다. 「3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 것은 몇 개인가」라는 질문은, 여러 나눗셈의 나머지로부터 원래의 수를 역산한다는 현대 CRT와 본질적으로 같은 발상을 이미 보여주고 있었습니다.
중국인의 나머지 정리가 현대에 가장 실용적으로 쓰이는 사례 중 하나는 RSA 암호의 복호화 처리 고속화입니다. RSA 암호의 복호화는 「큰 수를 비밀키로 거듭제곱한 뒤 법으로 나눈 나머지를 구하는」처리인데, 법으로 쓰이는 합성수 n = p × q（p, q는 큰 소수）를 그대로 쓰는 대신, CRT를 이용해 mod p와 mod q 각각에서 독립적으로 계산한 뒤 결과를 결합하면 이론적으로 최대 4배 가까운 속도 향상을 기대할 수 있습니다. 이를 「CRT-RSA」라고 하며, 많은 암호 라이브러리에 구현되어 있는 최적화 기법입니다.
이 도구가 지원하는 것은 법이 모두 서로소인 「고전적인 중국인의 나머지 정리」입니다. 법이 서로소가 아닌 경우（예: mod 4와 mod 6처럼 공약수를 가지는 경우）에도 조건에 따라 해가 존재할 수 있지만, 그 판정과 계산에는 일반화된 확장 알고리즘이 필요하므로 이 도구의 범위 밖으로 두었습니다.