중국인의 나머지 정리
나머지 조각으로 전체를 알아냅니다
바구니에 든 사탕을 3개씩 묶어 세면 2개가 남고, 5개씩 묶으면 3개가 남고, 7개씩 묶으면 2개가 남습니다. 사탕은 모두 몇 개일까요?
전체 개수를 직접 세어보지 않고도 각각의 나머지들만 모아서 원래의 정확한 숫자를 단번에 맞히는 마법 같은 계산법이 있습니다. 1500년 전 손자산경에 적힌 이 지혜의 원리는 무엇일까요?
이야기
1247 년
Public domain · 위키미디어 공용
사탕이 몇 개 있는지 모릅니다. 그런데 이것은 압니다 — 3개씩 묶으면 2개 남고, 5개씩 묶으면 3개 남고, 7개씩 묶으면 2개 남습니다. 사탕은 몇 개일까요?
답은 23개입니다. 확인해 보세요. 23÷3은 나머지 2, 23÷5는 나머지 3, 23÷7은 나머지 2입니다.
이 문제는 5세기 중국의 『손자산경』에 실려 있습니다. 그래서 중국인의 나머지 정리라 부릅니다.
핵심은 이것입니다. 나누는 수들이 서로소이면, 나머지들만 알아도 답이 하나로 정해집니다. 3·5·7의 곱인 105보다 작은 범위에서 딱 하나입니다.
옛날 장군이 병사 수를 셀 때 썼다는 이야기도 전해집니다. 일일이 세지 않고 3열·5열·7열로 세워 남는 사람만 보면 전체 수를 알 수 있습니다.
큰 수 계산을 잘게 쪼개 빠르게 합니다. 여러 나머지로 나눠 셈한 뒤 다시 합칩니다.
RSA 암호의 복호화 속도를 네 배 가까이 올리는 표준 기법이고, 오류 정정 부호와 병렬 계산에도 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
사탕을 3개씩·5개씩 나눠 남는 수로 맞히기
사탕이 3개씩 세어 2개 남는 수(2, 5, 8, 11, 14, 17, 23…)를 공책에 적고, 5개씩 세어 3개 남는 수(3, 8, 13, 18, 23…)를 적어 봅니다.
두 모둠에서 겹치는 수(23)를 찾은 뒤, 7개씩 나누어 2가 남는지 직접 확인해 보세요. 가장 작은 수 23을 눈으로 직접 찾아내며 수들이 겹치는 규칙을 느껴보세요.
나머지 셋으로 수를 찾아 보세요
3·5·7 로 나눈 나머지만 알면 105 안에서 딱 하나로 정해집니다.
나머지로 수 찾기
3으로 나눈 나머지가 1이고 5와 7의 배수인 수(70), 5로 나눈 나머지가 1이고 3과 7의 배수인 수(21), 7로 나눈 나머지가 1이고 3과 5의 배수인 수(15)를 각각 미리 찾아둡니다.
각각에 원하는 나머지 를 곱해 더하면 이 됩니다. 여기서 의 배수들을 덜어내면 가장 작은 양수 23이 명쾌하게 계산됩니다.
왜 105 마다 되풀이될까요
3·5·7 은 서로소라 105 — 4 와 6 은 아니라 12 밖에 안 됩니다.
합동식으로 증명
쌍마다 서로소(pairwise coprime)인 자연수 에 대해 연립합동식 는 법 에 대해 유일한 해를 가집니다.
라 할 때, 잉여역수 를 유클리드 호제법으로 구하면 일반해는 으로 완벽하게 구성됩니다.
큰 수를 작게 쪼개 보세요
RSA 를 네 배 빠르게 하는 것이 바로 이 기법입니다.
환의 분해
대수학에서 중국인의 나머지 정리(CRT)는 환의 직합 분해 동형사상 으로 일반화됩니다.
현대 컴퓨터 과학에서는 수천 자리의 거대한 정수 연산을 작은 소수 모듈러 연산 여러 개로 쪼개어 병렬 처리한 뒤 CRT로 복원하는 초고속 연산 알고리즘(RNS) 및 RSA 암호 시스템의 복호화 가속에 핵심적으로 활용됩니다.
달력과 주기
10·12 = 120 이 아니라 60 — 둘이 서로소가 아니기 때문입니다.
풀어 보기
연립합동식과 미지의 수. 어떤 양의 정수 를 3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는다.
(1) 5와 7의 공배수 중 3으로 나누어 1이 남는 가장 작은 자연수를 구하시오.
(2) 조건을 만족하는 가장 작은 양의 정수 의 값을 구하시오.
(3) 조건을 만족하는 100 이상 300 이하의 자연수 의 값을 모두 구하시오.
(2) 이며, 일반해는 이므로 (3)은 입니다.
답과 풀이 보기
(1) 70 입니다.
5 와 7 의 공배수는 35, 70, 105, … 인데 이므로 70 이 처음입니다.
이 수는 5 로도 7 로도 나누어떨어지고 3 으로만 1 을 남기는 열쇠 조각입니다.
(2) 입니다.
확인하면 — 셋 다 맞습니다.
⭐ 3 으로 2 남고 7 로도 2 남으니 는 21 의 배수입니다. 그 가운데 5 로 나눠 3 남는 것을 찾으면 → .
(3) 128 과 233 입니다.
3·5·7 이 서로소이므로 답은 마다 되풀이됩니다 — .
이므로 100 이상 300 이하는 128 과 233 뿐입니다.
기원후 3 세기 손자산경에 이 물음이 그대로 실려 있습니다. 병사를 3 명씩·5 명씩·7 명씩 세워 남는 수만 보고 전체 인원을 알아냈다고 합니다. 지금도 이 셈은 암호 속에서 그대로 돌아가고 있습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「나머지만으로 알아내기」는 지금도 쓰입니다.
- 큰 수 계산 — 큰 수를 작은 나머지 여러 개로 쪼개 빠르게 셈합니다
- 암호 — RSA 복호화를 빠르게 하는 데 씁니다
- 달력 — 요일과 날짜를 맞추는 데도 같은 생각이 쓰입니다
이어지는 장
서로 소인 여러 수로 나눈 나머지들만으로 원래의 수를 정확하게 하나로 결정짓는 계산법은, 12로 나눈 나머지의 세계를 다루었던 제93장 의 시계 산수를 넘어 현대 컴퓨터 암호 알고리즘의 핵심 계산 기법으로 뻗어 나갑니다.
영감을 받은 곳
3세기경 중국 남북조 시대의 산학서 『손자산경』(孫子算經) 하권 제26문의 '물부지수'(物不知數) 문제에서 기원하여, 1247년 남송의 수학자 진구소(秦九韶)가 『수서구장』(數書九章)에서 '대연구일술'로 완전한 일반 해법을 정립했습니다.