중국인의 나머지 정리 설명

어떤 수를 3으로 나누면 2, 5로 나누면 3, 7로 나누면 2가 남습니다. 이 수는 무엇일까요? 수를 하나씩 대입해 보면 얼마 뒤 23에 이르지만, 이 질문에는 정리가 숨어 있습니다. 나누는 수들이 공약수를 갖지 않는 한, 그 곱보다 작은 답은 언제나 정확히 하나 있고, 아무것도 대입해 보지 않고 찾을 수 있습니다. 이 정리는 약 1,500년이 되었으며, 지금도 달력과 컴퓨터 연산, 그리고 웹을 지키는 암호에서 일하고 있습니다.

3으로 나누면 2, 5로 나누면 3, 7로 나누면 2가 남는 수를 나타내는 세 줄의 표시가 23의 열에서 한 줄로 맞춰진 그림
3으로 나누면 2, 5로 나누면 3, 7로 나누면 2가 남는 수를 나타내는 세 줄의 표시가 23의 열에서 한 줄로 맞춰진 그림

『손자산경』의 문제

3~5세기의 중국 산학서 『손자산경』은 셋씩 세면 2, 다섯씩 세면 3, 일곱씩 세면 2가 남는 물건의 개수를 묻습니다. 답은 23이고, 그 방법은 지금도 가르칩니다. 셋씩 세고 남은 하나마다 70, 다섯씩 세고 남은 하나마다 21, 일곱씩 세고 남은 하나마다 15를 잡아 더한 뒤, 뺄 수 있는 만큼 105를 뺍니다. 2 × 70 + 3 × 21 + 2 × 15 = 233이고, 233 − 2 × 105 = 23입니다. 명나라의 노래가 70, 21, 15, 105라는 수를 몇백 년 동안 사람들의 기억에 남겼습니다. 진구소는 1247년에 일반적인 방법을 내놓았고, 같은 문제가 피보나치의 1202년 『산반서』에도 나오며, 카를 프리드리히 가우스는 1801년 『정수론 연구』에서 정리를 현대적인 형태로 서술했습니다.

청대에 찍은 『손자산경』의 한 쪽. 3~5세기 중국 산술서로, 셋, 다섯, 일곱씩 세면 각각 2, 3, 2가 남는 수를 묻는다.
청대에 찍은 『손자산경』의 한 쪽. 3~5세기 중국 산술서로, 셋, 다섯, 일곱씩 세면 각각 2, 3, 2가 남는 수를 묻는다.
카를 프리드리히 가우스, 크리스티안 알브레히트 옌센의 1840년 초상. 1801년의 Disquisitiones Arithmeticae에서 합동 기호 a ≡ b (mod n)를 도입했다.
카를 프리드리히 가우스, 크리스티안 알브레히트 옌센의 1840년 초상. 1801년의 Disquisitiones Arithmeticae에서 합동 기호 a ≡ b (mod n)를 도입했다.

정리의 내용

어떤 두 개도 공약수가 없는 법 n₁, n₂, …, nₖ와 아무 나머지 a₁, a₂, …, aₖ를 잡습니다. 그러면 모든 i에 대해 nᵢ로 나누면 aᵢ가 남는 정수 x가 0부터 N − 1 사이에 정확히 하나 있습니다. 여기서 N = n₁ × n₂ × … × nₖ입니다. 다른 모든 해는 그 해와 N의 배수만큼 차이가 납니다. 모듈러 산술의 기호로 쓰면, 연립 합동식 x ≡ aᵢ (mod nᵢ)는 해를 가지며 그 해는 N을 법으로 유일합니다. 달리 말하면, 0부터 N − 1까지의 수와 그 나머지들의 목록은 정확히 같은 정보를 담고 있습니다. 3 × 5 × 7 = 105개의 수와 3 × 5 × 7 = 105가지 나머지 목록이 하나씩 짝지어집니다.

해 만들기

70, 21, 15라는 수는 마법이 아닙니다. 각각 자기 법으로 나누면 1이 남고, 다른 법으로 나누면 0이 남습니다. 70 = 2 × 35는 5와 7의 배수이고, 3으로 나누면 1이 남습니다. 일반적으로는 nᵢ를 뺀 모든 법의 배수인 Nᵢ = N / nᵢ를 잡고, Nᵢ의 mod nᵢ 역원 yᵢ를 곱합니다. Nᵢ와 nᵢ는 공약수가 없으므로 역원이 있고, 확장 유클리드 호제법이 그것을 찾습니다. 최대공약수를 구하는 유클리드의 나눗셈을 한 뒤 베주 항등식 1 = s × nᵢ + t × Nᵢ까지 거꾸로 올라가면 t가 역원이 됩니다. 그러면 x = a₁N₁y₁ + a₂N₂y₂ + …를 N으로 나눈 나머지는 모든 식에 맞습니다. 각 항이 자기 식에 맞고 다른 모든 식에서는 사라지기 때문입니다.

식을 하나씩 풀기

모든 법의 곱이 필요 없는 두 번째 방법도 있습니다. x ≡ 2 (mod 3)의 모든 해는 x = 2 + 3t 꼴입니다. 이것을 다음 식에 대입하면 2 + 3t ≡ 3 (mod 5), 곧 3t ≡ 1 (mod 5)이고, 3의 mod 5 역원인 2를 곱하면 t ≡ 2 (mod 5)를 얻습니다. 그러면 x = 2 + 3 × 2 = 8이고, 처음 두 식을 합치면 x ≡ 8 (mod 15)입니다. 세 번째 식으로 되풀이하면 8 + 15t ≡ 2 (mod 7)에서 t ≡ 1이므로 x ≡ 23 (mod 105)입니다. 이 대입법은 수를 작게 유지하고, 컴퓨터가 이런 연립 합동식을 보통 푸는 방법이며, 법들이 공약수를 가질 때도 통합니다.

공약수를 가진 법

두 법이 공약수를 가지면 그 식들은 겹칩니다. x ≡ 1 (mod 4)는 이미 x가 홀수라는 뜻이고, x ≡ 4 (mod 6)은 x가 짝수라는 뜻이므로, 둘을 모두 만족하는 x는 없습니다. 일반적으로 x ≡ a (mod m)과 x ≡ b (mod n)이 동시에 성립하는 것은 a와 b를 g = gcd(m, n)으로 나눈 나머지가 같을 때, 곧 g가 a − b를 나눌 때뿐입니다. 그때 해는 m × n이 아니라 lcm(m, n) = m × n / g를 법으로 유일합니다. 2개, 3개, 4개, 5개, 6개씩 꺼내면 1개가 남고 7개씩 꺼내면 남지 않는 달걀 바구니라는 오래된 수수께끼의 답은 301이며, 420 = lcm(2, 3, 4, 5, 6, 7)마다 반복됩니다. 연립 합동식에 해가 있는 것은 모든 두 식이 서로 맞을 때뿐이므로, 해가 없는 연립 합동식에는 언제나 서로 부딪치는 쌍이 들어 있습니다.

달력, 컴퓨터, RSA

1583년 조제프 스칼리제르는 세 가지 달력 주기, 곧 28년의 태양 주기와 19년의 태음 주기와 15년의 인딕티오를 묶어 28 × 19 × 15 = 7,980년의 율리우스 주기를 만들었습니다. 정리에 따라 모든 해는 세 주기 번호의 고유한 조합을 가지며, 주기는 세 번호가 모두 1이었던 가장 최근의 해인 기원전 4713년에 시작합니다. 천문학자들은 지금도 그때부터 율리우스일을 셉니다. 컴퓨터는 이 정리를 써서 아주 큰 수를 작은 나머지들의 목록으로 계산합니다. 나머지들은 따로따로 동시에 더하고 곱할 수 있고, 마지막에 합칩니다. RSA 복호화도 같은 방식입니다. n = p × q일 때 c^d mod n을 mod p와 mod q에서의 두 거듭제곱으로 계산해 정리로 합치면, mod n 거듭제곱 한 번보다 약 네 배 빠릅니다. 미뇨트의 방식이나 아스무스-블룸의 방식 같은 비밀 분산 기법은 비밀을 나머지 속에 숨겨, 충분히 많은 나머지가 모여야만 비밀이 드러나게 합니다.

론 리베스트, 아디 샤미르, 렌 애들먼(왼쪽부터)
론 리베스트, 아디 샤미르, 렌 애들먼(왼쪽부터)

직접 해 보기

풀이기를 열어 20개까지의 식과 200자리까지의 수로 아무 연립 합동식이나 입력하거나, 예제 중 하나를 고르세요. 손자의 문제, 달걀 바구니, 율리우스 주기, 두 버스의 시간표, RSA 복호화, 그리고 해가 없는 연립 합동식이 있습니다. 풀이는 구성법이나 대입법으로, 모든 역원을 확장 유클리드 호제법으로 구하면서 여러분의 수로 적힙니다. 그림은 각 식을 만족하는 수에 표시해 모든 식이 만나는 단 하나의 열을 보여 주거나, 두 식의 나머지를 모든 수가 제 칸을 갖는 표에 늘어놓습니다.

자주 묻는 질문

연립 합동식의 해는 유일한가요?

법의 배수만큼의 차이를 빼면 유일합니다. x = 23이 손자의 문제의 해라면 23 + 105 = 128, 233, −82도 해입니다. 105를 더해도 어떤 나머지도 바뀌지 않기 때문입니다. 정리가 말하는 것은 0부터 104 사이에 해가 정확히 하나 있다는 것이고, 법들이 공약수를 가지면 최소공배수보다 작은 해가 정확히 하나 있다는 것입니다.

왜 법들은 서로소여야 하나요?

구성법에서는 Nᵢ가 mod nᵢ 역원을 가져야 하는데, 이는 공약수가 없을 때만 존재하기 때문입니다. 정리 자체에서는 공약수가 있으면 일부 식이 겹치기 때문입니다. 그러면 연립 합동식은 해가 없거나 서로 다른 해가 더 적어지고, 해는 곱마다가 아니라 최소공배수마다 반복됩니다.

모듈러 역원을 손으로 구하려면?

확장 유클리드 호제법을 씁니다. 15의 mod 7 역원은 15 = 2 × 7 + 1이므로 1 = 15 − 2 × 7이고, 15 × 1 ≡ 1 (mod 7)이므로 역원은 1입니다. 35의 mod 3 역원은 35 = 11 × 3 + 2, 3 = 1 × 2 + 1이므로 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35이고, 역원은 −1 ≡ 2입니다. 법이 작으면 곱의 나머지가 1이 될 때까지 1, 2, 3, …을 대입해 봐도 됩니다.

이 정리는 시계와 무슨 관계가 있나요?

mod n의 나머지는 n시간짜리 시계 위의 한 위치입니다. 3시간짜리와 5시간짜리 시계를 함께 출발시켜 한 시간씩 움직이면, 처음으로 돌아오기 전에 15가지 위치 쌍을 한 번씩 모두 보여 줍니다. 3과 5에 공약수가 없기 때문입니다. 4시간짜리와 6시간짜리 시계는 12걸음 만에 처음으로 돌아오고, 24가지 쌍 중 12가지만 보여 줍니다. 홀수 위치와 짝수 위치는 결코 함께 나타나지 않습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

중국인의 나머지 정리 풀이기 열기