중국인의 나머지 정리

조선 시대 경선징의 <묵사집산법> 지권 인잉구총문은 다음과 같은 칠언 절구의 한시로 시작한다.

3인이 70세까지 함께 가기는 드문데 三人同行七十稀
5마리의 봉새가 21일 전에 깃들인다. 五鳳棲前二十一
7월의 가을바람이 십오[15]야에 일고 七月秋風三五夜
동지에서 한식까지는 105일이러라. 冬至寒食百五除

특이한 점은 시에 숫자가 많이 등장한다는 사실이다. 무엇을 위한 시일까?

구결 : 수학 지식을 시로 나타낸 것

동아시아의 산학 책을 보면 위와 같은 한시 형태의 문장이 종종 나타난다. 이는 수학 지식을 시의 형식으로 나타낸 것으로 흔히 구결(口訣)이라 말하는 것이다. 대표적인 것으로 누구나 알고 있는 곱셈 구구단이 있다. 나눗셈 구구단인 구귀제법(九歸除法)이란 구결도 있다. 실생활에서 빈번히 나타나는 단위 환산을 위한 구결도 있다. 이를테면 무게의 단위로 1근은 16냥인데, 1냥, 2냥, ⋯, 15냥을 근으로 환산하기 위한 구결로 근하유양법(斤下留兩法)이 있다. 이렇게 수학 내용을 구결로 만든 이유는, 수학 지식을 손쉽게 배우고 암기해서 널리 보급하기 위한 것으로 보인다.

한시의 의미

위의 시 바로 밑에 다음과 같은 문제가 있다.

지금 물건이 있는데, 그 개수는 알지 못한다. 다만, 3개씩 세면 1개 남고 
5개씩 세면 2개가 남으며 7개씩 세면 3개가 남는다고 한다. 원래의 개수는 얼마인가?

위의 시에서 처음 세 구는 차례로 3, 5, 7로 시작하는데, 이 문제에서 3개씩, 5개씩, 7개씩 묶어서 세는 것과 관계가 있다. 그리고 시에서 3, 5, 7과 함께 나타나는 수 70, 21, 15 및 넷째 줄에 나타나는 105에는 다음과 같은 의미가 있다.

　　　　　 70 : 5와 7의 공배수 중에서 3으로 나누면 나머지가 1인 가장 작은 수
　　　　　 21 : 3과 7의 공배수 중에서 5로 나누면 나머지가 1인 가장 작은 수
　　　　　 15 : 3과 5의 공배수 중에서 7로 나누면 나머지가 1인 가장 작은 수
　　　　　105 : 3, 5, 7의 최소 공배수

시에 있는 이런 정보를 이용하면, 다음과 같이 위 문제를 만족시키는 값을 얻을 수 있다.

이것이 문제의 답이 될 수 있다. 그런데 언급하지 않아도 통상 조건을 만족시키는 가장 작은 값을 찾는 것이 관례였다. 그래서 157에서 세 수 3, 5, 7의 최소 공배수 105를 필요한 만큼 몇 번 빼서 답을 얻는다. 다음이 이 문제의 답이다.

손자의 문제

위의 문제의 원형은 중국의 수학 고전으로 ‘산경십서’(算經十書)의 하나인 <손자산경(孫子算經, 3~4세기)> 하권에 있는 다음 문제이다.

물건이 몇 개 있는지 총수는 알 수 없다.
다만, 3개씩 세면 2개가 남고 5개씩 세면 3개가 남고 7개씩 세면 2개가 남는다고 한다. 총수는 얼마인가?

이를 ‘손자의 문제’라 부르는데, <묵사집산법>의 해법에 따라 이의 답을 구하면 다음과 같다.

손자의 문제는 일반인 사이에서도 널리 회자됐는데, 진나라 왕의 비밀 병사 점호법(秦王暗點兵), 한신 장군의 병사 점호법(韓信點兵), 반복 사격술(覆射之術), 귀곡산(鬼谷算) 등 여러 가지 이름으로 불렸다.

손자의 문제는 그 자체로 매우 흥미롭다. 그런데 고대 중국에서 역법(曆法) 계산과 깊은 관련도 있었다. 당시의 천문학자들은 장기간에 걸친 천문관측 기록에 의거해서 해와 달 및 (당시에 알려진) 다섯 행성의 운동 주기를 추산하고, 이들 천체의 주기 운동의 기점, 즉 상원(上元)을 정할 필요가 있었다. 위와 같은 문제의 일반적인 해법이 바로 그 유명한 ‘중국인의 나머지 정리’인데, 이런 천문 계산에 필수적인 지식이었다.

중국인의 나머지 정리

손자의 문제와 해법은 서양 수학자들의 관심도 끌게 되었고, 해법의 원리는 ‘중국인의 나머지 정리’라는 이름을 얻게 되었다. 위대한 수학자 오일러(Leonhard Euler, 1707∼1783)는 1734년에 러시아의 한 잡지에 중국인의 나머지 정리를 다음과 같이 서술했다.

이는 앞에서 설명한 손자의 해법과 정확하게 일치하는데, 구체적인 수 대신에 문자를 사용해서 일반화했고, 서로 소인 수의 개수를 3에서 5로 증가시켰을 뿐이다. 여기서 서로 소인 수의 개수는 5뿐만 아니라 임의의 수로 확장시킬 수 있다.

중국인의 나머지 정리에서 가장 어려운 부분은 서로 소인 수 중에서 한 개를 제외한 나머지 수들의 곱(즉 최소 공배수)으로 나누어 떨어지지만 제외한 수로 나누면 나머지가 1인 수를 찾는 과정이다. 예를 들면, 오일러의 서술에서 bcde로 나누어 떨어지지만 a로 나누면 나머지가 1인 수 A를 찾는 과정이다. 손자의 문제에서와 같이 서로 소인 수가 세 개인 경우는 단순히 시행착오를 통해서도 이런 수를 찾을 수 있지만, 그렇지 않은 경우에는 결코 쉽게 얻을 수 없다. 바로 이런 문제를 해결하는 알고리즘인 대연구일술(大衍求一術)이 진구소(秦九韶)의 <수서구장(數書九章)> (1257)에 나타난다. 이는 현대 수학에 기여한 산학의 또 다른 공헌이다.

중국인의 나머지 정리의 현대적 표기 
중국인의 나머지 정리를 현대적으로 표기하면 아래와 같다. 아래 식에서 ‘a≡b (mod m)’은 두 정수 a, b를 자연수로 나누었을 때 나머지가 서로 같다는 뜻이고, 'a는 법 m에 관해 b와 합동이다'라고 한다.

네이버캐스트