개나 소나 이해하는 중국인의 나머지 정리(3부)

1부 보러가기

2부 보러가기

항구로 돌아가자.

3으로 나누어 2가 남고, 5로 나누어 3이 남고, 7로 나누어 2가 남는 수는 무엇일까?

검은 세단 뒷좌석에 앉아 고민하던 사장은 불현듯 손뼉을 친다.

"맞아, 그거야!"

"뭡니까?"

부하는 사장의 말에 귀를 기울인다.

"화물차 세 대에 상자를 쌓는다고 생각해 봐.

3 상자씩 나누면 2가 남는다고 했으니까, 첫 화물차는 3의 배수에 2를 더한 만큼 쌓자.

나머지 두 화물차는 3으로 딱 나뉘게 3개씩 쌓는 거야.

그럼 3으로 나눈 나머지는 첫 화물차만 신경 쓰면 되겠지."

"그럼 다섯 상자, 일곱 상자씩 쌓는 건 어떡합니까?"

"끝까지 들어 봐!

두 번째 화물차에는 5의 배수에 3을 더한 만큼 쌓되, 첫 번째와 세 번째 화물차에는 5의 배수만큼 쌓는 거야.

세 번째 화물차에는 7의 배수에 2를 더한 만큼 쌓되, 첫 번째와 두 번째 화물차에는 7의 배수만큼 쌓자고."

"화물차마다 조건이 제각각이지 않습니까?"

"그래!

하지만 무식하게 세 조건에 맞는 수를 일일이 찾는 것보다는 쉽겠지.

이제 보라고.

첫 화물차에 쌓는 상자 수는 3으로 나누어 2가 남고, 5의 배수고, 7의 배수야.

5의 배수면서 7의 배수는 곧 35의 배수니까, 35 배수 중에 3으로 나누어 2가 남는 수를 알아보면 되겠지."

"35가 3으로 나누어 2로 남습니다."

"그럼 첫 화물차에는 35상자가 있다고 치자고.

두 번째 화물차 상자 수는 3의 배수, 5로 나누어 3이 남는 수, 7의 배수야.

3*7=21의 배수 중에 5로 나누어 3이 남는 수는 얼마지?"

"63입니다."

"마지막 세 번째 화물차도 같은 식이야.

15의 배수 중에 7로 나누어 2가 남는 수는?"

"30입니다."

"그럼 이제 세 화물차 상자 수를 더하면 돼.

35 더하기 63 더하기 30은 128야. 23뿐 아니라 128도 답인 거지."

"더하면 배수가 아니게 되지 않습니까?"

"바보야. 그러니까 네가 내 밑에서 일하는 거다.

배수끼리는 아무리 더해도 배수란 말이야.

16은 4가 네 조각, 24는 4가 여섯 조각이지?

그럼 합치면 결국 열 조각. 더한 것도 4의 배수가 된다.

두 번째 화물차와 세 번째 화물차는 3의 배수다.

그러니 둘은 합쳐도 3의 배수야.

거기에 3으로 나누어 2가 남게 첫 화물차를 채웠으니,

셋을 합치면 2가 남을 수밖에 없는 거지.

이런 식으로 세 조건을 모두 만족하는 수를 구할 수 있다고."

"그런데 사장님. 만약 128상자보다 많으면 어떻게 합니까?"

"쉽지. 아무 화물차나 수를 키우면 돼.

첫 화물차가 35상자였지? 35의 배수 중에 3으로 나누어 2가 남는 수가 또 뭐 있지?"

"140입니다."

"그럼 35 대신에 140을 넣으면 되지. 그럼 128이 아니라 233상자겠군."

연립1차합동방정식 풀기

---

  사장, 머리도 좋다. 세 조건을 모두 만족하는 수를 손으로 구하기란 여간 힘든 일이 아니다. 그러니 수를 셋으로 나누어 문제를 쉽게 풀어낸 것 아닌가. 이 정도면 문제를 다 풀었다고 봐도 좋다. 그러나 아직 '수학적'이지 못하다. 

  어떻게 '수학적'일 수 있을까?

  이 문제는 일차합동식 셋으로 표현할 수 있다.

$x \equiv 2 \pmod{3}$

$x \equiv 3 \pmod{5}$

$x \equiv 2 \pmod{7}$

  이 세 식을 만족하는 x를 구하라, 이 말이다. 방정식이 여럿 있는 문제는 연립방정식이라 부른다. 그럼 합동방정식이 여럿 있는 문제는 뭐라고 부를까? 맞다. 연립합동방정식이다. 1차니까 굳이 길게 부르자면

연립1차합동방정식이다.

연립1차합동방정식 $x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$ $\dots$ $x \equiv a_n \pmod{m_n}$ (* 단 m들은 자기들끼리 전부 서로소라는 조건을 붙이자. 아니라면 좀 어려워지니까.)

  어찌 보면 사장과 5세기 손자가 고민한 문제는 연립1차합동방정식 그 자체인데, 연립1차합동방정식(쓰기도 힘들다)은 어떻게 풀까?

연립1차합동방정식을 푸는 법

---

  놀랍게도 이 문제를 푸는 방법은 사장이 생각한 '화물차 방법'과 비슷하다.

$x= \square_1 (m_1 * m_2 \dots m_n)$ 

$+ \square_2 (m_1 * m_3 \dots m_n)$

$+ \dots+$

$+ \square_n (m_1 * m_2 \dots m_{n-1})$

  라고 놓는다. 항마다 m을 하나만 빼고 전부 곱한 값을 넣는 것이다.

예를 들어 $x$를 $m_1$으로 나눈다면 첫 항 빼고는 전부 나누어떨어진다. 그럼 첫 항을 $m_1$으로 나누어 $a_1$가 남게 하는 $\square_1$ 두 번째 항은$m_2$로 나누어 $a_2$가 남게 하는 $\square_2$... 를 전부 구해야 한다. 이번에도 '수학적'일 순 없을까?

  아이디어가 없으면 빌리거나 훔쳐라. 많은 자기개발서에 나오는 말이다.

  자기개발서가 좋든 싫든, 프랑스 수학자 에티엔 베주Etienne Bezout의 아이디어를 하나 가져오자. 

  베주가 만든 베주 항등식이 있다. 두 정수의 최대공약수를 두 수의 배수의 합으로 나타낼 수 있다는 공식이다. 만약 두 정수가 서로소라면, 즉 공약수가 1뿐이라 최대공약수도 1이라면 공식은 이렇게 바뀐다.

'1을 두 서로소인 수의 배수 합으로 나타낼 수 있다.'

  $m_1, m_2 \dots m_n$은 자기들끼리 전부 서로소다. 이들 중 두 수를 아무리 잡아도 서로소라는 말이다. $m_k$와 $m_k$를 뺀 나머지를 전부 곱한 값도 서로소다.

  $m_k$를 뺀 나머지를 전부 곱한 값을 $n_k$라고 부르자. $m_k$와 $n_k$는 서로소다. 그럼 베주님의 가르침에 따라 1을 '$m_k$와 $n_k$의 배수의 합'으로 나타낼 수 있다.

$1 = \vartriangle m_k + \blacktriangle n_k$

$\vartriangle m_k + \blacktriangle n_k = 1$

  근데 이런 식, 어디서 많이 봤다. 바로 디오판토스 방정식이다. x와 y가 △와 ▲가 되었을 뿐. 디오판토스 방정식은 합동식과 거의 한 몸이니, 합동식으로도 쓸 수 있다.

$\blacktriangle * n_k \equiv 1 \pmod{m_k}$

  x에서 값마다 곱하던 \square는 바로 $a_1*\blacktriangle$이다. 왜 그럴까? 예를 들어 첫 항은 $a_1*\blacktriangle*n_1$이 된다. 이게 과연 $m_1$으로 나누어 $a_1$이 남는지 보자.

  $\blacktriangle*n_1$은 $m_1$으로 나누어 1이 남는다.(바로 위에 식이 있다) 그럼 $\blacktriangle*n_1 = m_1*k + 1$이다. $a_1*\blacktriangle*n_1=a_1*(m_1*k + 1) = a_1*m_1*k + a1$인데

$a_1*m_1*k$은 $m_1$으로 나누어떨어지므로 나머지는 $a_1$이 된다!

이는 나머지 항에도 다 적용되므로, 이제 방정식의 답 x를 거의 구한 셈이다.

$x= a_1n_1s_1 + a_2n_2s_2 + ... + a_n*n_n*s_n$

(▲는 '수학적'으로 s라 부른다)

그런데 답은 하나가 아니었다. 23도 됐고 128, 233도 되었다. 128-23은 105, 233-128도 105. 간격은 105인 것 같은데…. 105는 3,5,7의 최소공배수다. 그렇다. 최소공배수를 더하면 $m_1, m_2 \dots ,m_n$에 모두 나누어떨어지므로 x를 나눈 나머지를 방해하지 못한다!

$x=$ $a_1n_1s_1 + a_2n_2s_2 + \dots + a_n*n_n*s_n + (m_1,m_2...m_n의 최소공배수)*k$

  그러나 우리는 합동식을 배웠기에 더 멋지게 쓸 수 있다.

$x\equiv a_1n_1s_1 + a_2n_2s_2 + \dots + a_n*n_n*s_n \pmod{m_1*m_2*\dots*m_n}$

라고….

해답

---

  그렇다면 이제 문제는 풀린다.

$x \equiv 2 \pmod{3}$

$x \equiv 3 \pmod{5}$

$x \equiv 2 \pmod{7}$

$a_1 = 2, a_2 = 3, a_3 = 2$이며

$m_1 = 3, m_2 = 5, m_3 = 7$이며

$n_1 = m_2*m_3 = 35$

$n_2 = m_1*m_3 = 21$

$n_3 = m_1*m_2 = 15$다.

  다주와 디오판토스의 합작에 따라 $s_k * n_k \equiv 1 \pmod{m_k}$니까 $s_1 * 35 \equiv 1 \pmod{3}$, 35의 배수 중에 3으로 나누어 1이 남는 수는 70이므로 $s_1=2$다.

  이런 식으로 전부 구하면 $s_2=1, s_3=1$이다.

  물론 s는 이것보다 클 수 있다. 사실, $s_1$을 80으로 $s_2$를 125 같은 숫자로 넣어도 상관은 없다. 어차피 연립1차합동방정식의 해는 뒤에 $\pmod{m_1*m_2*m_3…}$가 붙을 예정이다. 따라서 $m_1*m_2*m_3…$ 보다 작게 조절할 것이므로 이왕이면 처음부터 s를 작게 잡으면 좋을 것이다.

이제 s도 구했으니 답을 알아보자.

  $a_1n_1s_1 + a_2n_2s_2 + \dots + a_n*n_n*s_n \pmod{m1*m2*m3\dots}$는 $2*35*2 + 3*21*1 + 2*15*1 \pmod{3*5*7}$이고 즉 $x \equiv 233 \pmod{105}이 나온다.

  105로 나눈 나머지가 233일 수는 없으니까 233에서 $105*2=210$을 빼면 $x\equiv23 \pmod{105}$이 된다. 한 마디로 x는 105의 배수에 23을 더한 수가 되어 23, 128, 233… 이 되는 것이다.

또 다른 해?

---

그런데 잠깐. 과연 우리가 구한 이 해가 유일한 해일까?

$35x \equiv14 \pmod{21}$도 해가 $x \equiv 1, 4, 7, 10, 13, 16, 19 \pmod{21}$로 다양했다. 

  상상력을 발휘해 보자. x말고 y라는 해가 또 있다고 상상하는 것이다. 그럼 $x\equiv a_k \pmod{m_k}이고 $y\equiv a_k \pmod{m_k}$다.

합동식 성질 2번에 따라

$a_k \equiv y \pmod{m_k}$며,

합동식 성질 3번에 따라

$x \equiv a_k \equiv y \pmod{mk}$ 즉

$x \equiv y \pmod{mk}$가 성립된다.

합동실 성질 4번에 따라

$x-y \equiv ak - ak \pmod{m_k}$,

$x-y \equiv 0 \pmod{m_k}$다. 즉 $x-y$는 $m_k$로 나누어떨어지는 배수다.

$m_1$의 배수기도 하고 $m_2$의 배수기도 하고…….

최소공배수와 관련한 정리

'm이 a, b, c...의 배수면

m은 a, b, c..의 최소공배수의 배수다'

에 따라

$x-y$는 $m_1, m_2, \dots $의 배수이므로

$x-y$는 $m_1, m_2, \dots $ 의 최소공배수의 배수다

$x-y \equiv 0 \pmod{lcm(m_1, m_2\dots)}$

*LCM : 최소공배수

$m_1, m_2, m_3 \dots $는 모든 쌍에 서로소니까

또 다른 정리

'a, b, c...중 어떻게 두 숫자를 뽑아도 전부 서로소면

$a*b*c...$는 $a, b, c...$의 최소공배수다'

에 따라

$m_1, m_2, m_3\dots$의 최소공배수는 m들의 곱이다.

$x-y \equiv 0 \pmod{m_1*m_2*m_3\dots}

$y\equiv y \pmod{m_1*m_2*m_3\dots}인데,

(합동식 1번 규칙에 따라 자기 자신과는 무조건 합동)

  두 식을 더하면 $x \equiv y \pmod{m_1*m_2*m_3\dots}$다.

순서를 바꾸면 $y \equiv x \pmod{m_1*m_2*m_3 \dots}$다.

$x\equiv a_1n_1s_1+a_2n_2s_2+\dots+a_n*n_n*s_n \pmod{m_1*m_2*m_3\dots}$였는데

연결하면 $y\equiv a_1n_1s_1+a_2n_2s_2+\dots+a_n*n_n*s_n \pmod{ m_1*m_2*m_3\dots}$이다.

똑같다.

  즉, 다른 해는 x와 같다. 그러니까 해는 x뿐이다. 이로써 이런 문제는 해가 한 종류뿐임을 증명했다.

중국인의 나머지 정리

---

  지금까지 배운 모든 과정은 중국 책에서 처음 나왔다고 해서 중국인의 나머지 정리라고 부른다.

중국인의 나머지 정리 (Chinese remainder theorem) $m_1, m_2... m_n$이 모든 쌍에 서로소라면 $x\equiv a_1 \pmod{m_1}$ $x\equiv a_2 \pmod{m_2}$ $\dots$ $x\equiv a_n \pmod{m_n}$ 인 연립합동방정식은 $\pmod{m_1*m_2\dots m_n}$에 유일한 해를 지닌다. (해가 있다(존재성) + 하나다(유일성))

원래 풀이

---

  그럼 이 문제가 처음 나온 5세기 손자산경은 이걸 어떻게 풀었을까?

  "셋씩 세어 둘이 남으면 140을 적는다. 다섯씩 세어 셋이 남으면 63을 적는다. 일곱씩 세어 둘이 남으면 30을 적는다. 이들을 더해 233이 되고, 210을 빼면 답을 얻는다. 마찬가지로 셋씩 세어 하나가 남으면 70을 적는다. 다섯씩 세어 하나가 남으면 21을 적는다. 일곱씩 세어 하나가 남으면 15를 적는다. 합이 106보다 크므로 105를 빼면 답을 얻는다."

  3으로 나누어 2가 남으면서 5와 7로는 나누어떨어지는 수를 찾는다.

→ 140

  5로 나누어 3이 남으면서 3과 7로는 나누어떨어지는 수를 찾는다.

→ 63

  7로 나누어 2가 남으면서 3과 5로는 나누어떨어지는 수를 찾는다.

→ 30

  식으로 옮기면

$140\equiv2 \pmod{3}, \equiv0 \pmod{5},\equiv0 \pmod{7}$

$63\equiv0 \pmod{3},\equiv3 \pmod{5},\equiv0 \pmod{7}$

$30\equiv0 \pmod{3}, \equiv0 \pmod{5},\equiv2 \pmod{7}$

  가 된다.

  합동식 성질 4번에 따라 법(mod 뒤에 있는 수)이 같다면 식을 통째로 더할 수 있으니

세 식을 다 더하면

$140+63+30$

$\equiv 2+0+0 \pmod{3},$

$\equiv0 \pmod{5},$

$\equiv2 \pmod{7}$

  $233 \equiv 2\pmod{3},\equiv3\pmod{5}, 2 \pmod{7}$으로 식을 만족한다. 다만 $3*5*7=105$보다 크므로 두 번 빼서 23으로 만들 수 있다고 저 책은 말하고 있다.

  5세기 중국인이 ≡ 같은 식이나 디오판토스, 베주 같은 사람을 알았을 리는 없다. 아마 손자는 우리 사장과 같은 방식으로 문제를 푼 것 아니었을까.