중국인의 나머지 정리(Chinese remainder theorem)

어떤 수 $x$를 나눈 나머지가 $m =$ 에 대해서는 $a =$ , $n =$ 에 대해서는 $b =$ 입니다. $x$는 무엇일까요?

수 $k$를 두 나머지의 짝 $(k \bmod m,\; k \bmod n)$에 적으면, $k$가 1 늘 때마다 오른쪽 위로 한 칸씩 걸어갑니다. 서로소일 때 모든 칸이 차는 이유는 이렇습니다. 두 수 $0 \le j \lt k \lt mn$이 같은 칸에 떨어지면 $k - j$는 $m$으로도 $n$으로도 나누어떨어집니다. $m$과 $n$이 서로소이면 둘의 공배수는 곧 $mn$의 배수⁠(multiple)⁠인데, $0 \lt k - j \lt mn$이니 그럴 수 없습니다. $mn$개의 수가 $mn$개의 칸에 겹치지 않고 들어가니 칸마다 정확히 하나씩입니다(비둘기집 원리⁠(pigeonhole principle)⁠를 거꾸로 쓴 셈이고, 대응은 전단사⁠(bijective)⁠입니다).

답을 직접 만들 수도 있습니다. $n$의 배수 중 $m$으로 나누면 1이 남는 수와, $m$의 배수 중 $n$으로 나누면 1이 남는 수를 확장 유클리드 호제법⁠(extended Euclidean algorithm)⁠으로 구해 두면, 둘을 $a$배, $b$배 해서 더하면 끝입니다. 격자의 오른쪽 끝과 왼쪽 끝, 위와 아래를 이어 붙이면 도넛 모양의 곡면이 됩니다. 위상수학⁠(topology)⁠에서 원환면⁠(torus)⁠이라 부르는 곡면이고, 걸음은 도넛을 감아 도는 한 줄의 실이 됩니다. 비율이 서로소일 때 한 번에 닫히는 모습은 리사주 곡선⁠(Lissajous curve)⁠과 닮았습니다.

이름은 대략 3~5세기 무렵 중국의 산학서(셈법 책) 『손자산경⁠(Sunzi Suanjing)⁠』의 문제에서 왔습니다. 저자는 손자라는 이름만 전하고 누구인지 분명하지 않습니다. "셋씩 세면 둘이 남고, 다섯씩 세면 셋이 남고, 일곱씩 세면 둘이 남는 수는?" 먼저 3과 5만 풀면 8입니다. 그림에서 보기 이제 $x \equiv 8 \pmod{15}$과 $x \equiv 2 \pmod 7$을 같은 방법으로 합치면 답 $23 \pmod{105}$이 나옵니다. 법이 몇 개든 쌍마다 서로소이기만 하면 됩니다.

이어지는 곳. 이 정리 덕분에 합성수⁠(composite number)⁠를 법으로 하는 계산은 소인수분해⁠(prime factorization)⁠의 각 소수⁠(prime number)⁠ 거듭제곱에 대한 계산으로 쪼개집니다. 서로소인 $m, n$에 대해, $mn$과 서로소인 나머지는 '$m$과 서로소인 나머지'와 '$n$과 서로소인 나머지'의 짝과 하나씩 대응합니다. 그래서 오일러 피 함수⁠(Euler's totient function)⁠는 $\varphi(mn) = \varphi(m)\varphi(n)$를 만족하고, 15에 원시근⁠(primitive root)⁠이 없는 이유도 같은 쪼개기에서 나옵니다. RSA 암호⁠(RSA cryptosystem)⁠는 복호화(잠긴 메시지 풀기)를 $p$와 $q$로 따로 한 뒤 이 정리로 합쳐 3~4배가량 빠르게 합니다. 서로소가 아닌 두 법, 예컨대 4와 6에서는 두 나머지가 2로 나눈 나머지에서 서로 맞을 때만 12로 나눈 나머지 하나로 붙는데, '겹치는 곳에서 맞는 국소 자료는 전체 자료 하나로 붙는다'는 이 모양이 층의 붙이기 조건과 같습니다(글자 그대로의 층은 정수환을 소수들의 공간으로 보는 대수기하학에 있습니다).

확률⁠(probability)⁠로 옮기면 이렇습니다. 0부터 $mn - 1$까지에서 고르게 하나를 뽑으면, $m$으로 나눈 나머지와 $n$으로 나눈 나머지는 서로 독립⁠(independence)⁠입니다. 칸 $mn$개에 수가 정확히 하나씩 들어 있으니, 모든 짝 $(a, b)$가 확률 $\tfrac{1}{mn} = \tfrac1m \cdot \tfrac1n$으로 나오기 때문입니다. 곧 $m$으로 나눈 나머지를 알아도 $n$으로 나눈 나머지에 대해서는 아무것도 알 수 없습니다. 두 수가 서로소일 확률을 소수마다 곱해 구하는 바젤 문제⁠(Basel problem)⁠의 계산이 이 독립성에 기댑니다. 다만 정수⁠(integer)⁠ 전체에서 '고르게' 하나를 뽑는 방법은 없으므로, 그 계산은 1부터 $N$까지에서 뽑은 확률이 $N$을 키울 때 다가가는 값으로 읽어야 합니다. 끝으로, 칸 하나에 속하는 정수 전체는 동치류⁠(equivalence class)⁠ 두 개('$m$으로 나눈 나머지가 같은 수들'과 '$n$으로 나눈 나머지가 같은 수들')의 교집합⁠(intersection)⁠이고, 그것이 곧 $mn$으로 나눈 나머지가 같은 수들의 동치류 하나입니다.