홍라이프 계산기중국인의 나머지 정리 계산기 쉽게 이해하기 — 개념과 원리
중국인의 나머지 정리는 "3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 수는 무엇인가"와 같은 연립합동식을 푸는 방법입니다. 법(나누는 수)들이 서로소이면 0 이상 N 미만(N은 법들의 곱)에서 답이 정확히 하나 존재하고, 나머지 답은 모두 그 수에 N의 배수를 더한 것입니다. 정수론 공부, 주기와 달력 문제, RSA 암호의 복호화 계산 등에 쓰입니다.
계산 방법
연립합동식 x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), … 를 차례대로 대입하는 방식으로 풉니다.
- x = 0, 간격 N = 1에서 시작합니다.
- 각 합동식마다 t = 0, 1, 2, … 를 넣어 (x + N·t)를 nᵢ로 나눈 나머지가 aᵢ가 될 때까지 찾습니다. 찾으면 x ← x + N·t, N ← lcm(N, nᵢ)(서로소이면 N·nᵢ)로 바꾸고, x는 매 단계 N으로 나눈 나머지로 줄입니다.
- nᵢ번 안에 찾지 못하면 해가 없다고 표시합니다.
결과는 x (mod N) 꼴로 나옵니다. 음수 나머지나 법보다 큰 나머지는 먼저 나머지로 바꾸어 계산합니다.
원리
N은 앞에서 다룬 모든 법의 배수이므로, x에 N의 배수를 더해도 이미 맞춘 나머지는 바뀌지 않습니다. 그래서 합동식을 하나씩 맞춰 나갈 수 있습니다. 또 N과 새 법 nᵢ가 서로소이면 x, x + N, …, x + (nᵢ − 1)N을 nᵢ로 나눈 나머지가 모두 달라서, 그중 꼭 하나가 aᵢ와 일치합니다. 서로소인 주기들은 한 주기 N 안에서 딱 한 번 맞물린다는 것이 이 정리의 핵심입니다.
예제 풀이
- 입력값: 나머지 2, 3, 2와 법 3, 5, 7입니다. 『손자산경』에 나오는 바로 그 문제입니다.
- x ≡ 2 (mod 3): t = 2에서 맞으므로 x = 2, N = 3입니다.
- x ≡ 3 (mod 5): 2, 5, 8을 차례로 보면 8을 5로 나눈 나머지가 3이므로 x = 8, N = 15입니다.
- x ≡ 2 (mod 7): 8은 나머지 1, 23은 나머지 2이므로 x = 23, N = 105입니다.
- 결과는 x ≡ 23 (mod 105)입니다. 23, 128, 233, … 이 모두 답입니다.
결과 해석
"23 (mod 105)"는 가장 작은 음이 아닌 해가 23이고, 여기에 105를 더하거나 빼면 다른 해가 모두 나온다는 뜻입니다. 특정 범위의 답이 필요하면 N의 배수를 더해 범위 안으로 옮기면 됩니다. 답을 각 법으로 나누어 나머지를 확인해 보는 습관이 좋습니다.
흔한 실수
- 4와 6처럼 공약수가 있는 법을 넣는 경우입니다. 이때는 기본 정리가 성립하지 않고 해가 없을 수도 있습니다.
- 나머지와 법의 개수를 다르게 입력하는 경우입니다.
- 답을 하나의 수로만 생각하고 N의 배수만큼 반복된다는 점을 놓치는 경우입니다.
자주 묻는 질문
서로소라는 말은 무슨 뜻인가요?
두 수의 최대공약수가 1이라는 뜻입니다. 4, 9, 25는 소수가 아니지만 어느 두 수를 골라도 서로소입니다.
하나씩 대입하지 않는 공식도 있나요?
있습니다. Mᵢ = N/nᵢ, yᵢ를 Mᵢ의 mod nᵢ 역원이라 하면 x = Σ aᵢMᵢyᵢ (mod N)이며, 역원은 확장 유클리드 호제법으로 구합니다.
왜 '중국인의' 나머지 정리인가요?
가장 오래된 기록이 중국의 『손자산경』에 있고, 1247년 진구소가 일반적인 풀이법을 정리했기 때문입니다.
출처: 『손자산경(孫子算經)』 하권 제26문 · G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press