중국인의 나머지 정리 계산기
연립 합동식 x ≡ r (mod m) 을 풀어 가장 작은 해와 주기를 구합니다. 법이 서로소가 아닌 경우까지 다뤄, 해가 없는지 여러 개인지 이유와 함께 알려 줍니다.
눌러서 바로 넣어 볼 수 있습니다.
한 줄에 하나씩. “2 3”, “x ≡ 2 (mod 3)”, “3으로 나누면 2” 모두 됩니다.
해
x ≡ 23
mod 105 · 법이 모두 서로소
두 식을 하나로 합치는 것을 반복합니다.
구한 해를 각 법으로 나눠 봅니다.
계산 방법
- 1합동식을 한 줄에 하나씩 적습니다. "2 3"처럼 나머지와 법만 적어도 되고, "x ≡ 2 (mod 3)"이나 "3으로 나누면 2"도 읽습니다.
- 2가장 작은 해와 주기(최소공배수)를 확인합니다.
- 3법이 서로소가 아니면 곱 범위 안에 해가 몇 개인지 함께 나옵니다.
- 4합쳐 가는 과정과 검산으로 어디서 답이 나왔는지 따라갑니다.
자주 묻는 질문
나눈 나머지들만 알고 있을 때 원래 수를 찾아 주는 정리입니다. "3으로 나누면 2, 5로 나누면 3, 7으로 나누면 2인 수"를 물으면 23이라고 답하는 것이 이 정리입니다. 법(나누는 수)들이 서로소이면 그 곱의 범위 안에 해가 정확히 하나 있습니다.
해가 없거나, 곱 범위 안에 여러 개 있습니다. 두 법의 최대공약수를 g라 할 때 두 나머지도 g로 나눈 나머지가 같아야 풀립니다. 풀리더라도 해는 곱이 아니라 최소공배수마다 돌아오므로, 곱 범위 안에는 곱÷최소공배수 개만큼 들어갑니다.
x ≡ 1 (mod 4) 이고 x ≡ 2 (mod 6) 인 수는 없습니다. 4와 6의 최대공약수는 2인데, 첫 식은 x가 홀수라 하고 둘째 식은 짝수라 하기 때문입니다. 이 계산기는 어느 두 법이 부딪히는지 짚어 줍니다.
RSA 복호화를 빠르게 하는 데 씁니다. 개인키 계산을 두 소인수로 나눠 각각 하고 이 정리로 합치면 3~4배 빨라집니다(RSA-CRT). 그밖에 여러 주기가 겹치는 날짜 찾기, 해시 분산, 오류 정정 부호에도 쓰입니다.
법은 18자리까지, 식은 12개까지 넣을 수 있습니다. 계산은 정수형(BigInt)으로 하므로 법을 다 곱해 자릿수가 크게 늘어도 반올림 오차 없이 정확합니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 이름은 5세기경 「손자산경(孫子算經)」의 문제에서 왔습니다. 일반 해법을 세운 것은 진구소(秦九韶)의 「수서구장(數書九章)」(1247)입니다.
- 두 식을 하나로 합치는 것을 반복해 풉니다. 이 방식이면 법이 서로소가 아닌 경우도 함께 처리됩니다.
- "해가 유일하다"는 말은 법이 모두 서로소일 때만 맞습니다.
- 모듈러 역원 하나만 구하려면 모듈러 역원 계산기를 보세요.
함께 보면 좋은 도구
마지막 검증: 2026년 8월 30일 · 결과는 참고용 추정치입니다.