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차합동방정식이다.

  어찌 보면 사장과 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 \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뿐이다. 이로써 이런 문제는 해가 한 종류뿐임을 증명했다.

중국인의 나머지 정리

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

원래 풀이

  그럼 이 문제가 처음 나온 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세기 중국인이 ≡ 같은 식이나 디오판토스, 베주 같은 사람을 알았을 리는 없다. 아마 손자는 우리 사장과 같은 방식으로 문제를 푼 것 아니었을까.

시작하는 이야기

  한밤중, 칠흑 같은 바다가 일렁인다. 조명을 켜놓은 항구는 분주하다. 양복을 입은 남자들이 짐을 나르고 있다. 컨테이너에서 박스를 꺼내 화물차에 싣는다. 이 일은 밤에 해야만 한다. 박스 속에 있는 건 위험한 물건이기 때문이다. 그게 뭐냐고? 알면 안 된다. 위험하다니까...

"사장님."

  양복쟁이 하나가 검은 세단으로 다가가 허리를 굽히며 말한다. 진한 선팅을 씌운 창문이 내려간다. 그곳 뒷좌석에 한 남자가 앉아 있다. 사장님이라 불린 남자는 선글라스를 벗는다. 애초에 한밤중에 선글라스는 왜 쓴 것일까. 역시 위험한 물건을 다루는 사람답다.

"뭔데?"

사장은 목에 힘을 준다. 이 세계는 멋이 힘이다.

"작업 끝났습니다."

  사장이 창문 틈으로 보니 벌써 화물차가 상자로 가득하다. 이제 마무리하고 뜨기만 하면 된다.

"갯수는 확인했고?"

"그게..."

"무슨 일 있어?"

차 밖에 선 남자가 식은땀을 흘린다. 조짐이 심상치 않다.

"중국 쪽에서 상자 수를 알려주지 않았습니다."

"무슨 소리야? 몇 박스인지도 안 말하고 보내주다니. 그쪽에서 삥땅이라도 치면 어쩔 셈이야!"

"큰형님, 아니 회장님께서 이번 일은 믿어도 된다고 하셨습니다."

"회장님이 그리 말씀하신다면야..."

사장은 선글라스를 고쳐 쓴다.

"그래도 빼돌린 게 있는지는 알아야지. 정말 중국 쪽에서 아무 말도 없었어?"

"조심히 배송했다고 그랬습니다. 세 박스씩 묶어 보내려니 두 박스가 남고, 다섯 박스씩 보내려니 세 박스가 남고, 일곱 박스씩 보내려니 두 박스가 남았답니다. 그래서 그냥 공안에 돈 좀 찔러 한 번에 보냈다면서 말입니다."

"이게 뭔 개 같은 수학 문제냔 말이야."

  많은 사람은 이런 '사장님'과 '회장님'은 학창시절에 놀기만 했다고 생각한다. 그러나 위험한 물건을 다루는 사람 중에는 고학력자가 의외로 많다. 이 일도 머리가 좋아야 하는 법이다. 사장도 서울에 있는 이름 있는 대학교를 나와 수학에는 자신이 있다.

"어디 보자. 일곱 박스씩 보내면 두 박스가 남는다 그랬지? 7에 2를 더하면 9. 9는 세 박스로 딱 떨어지니까 아니야. 14에 2를 더하면 15. 15는 다섯 박스로 딱 떨어지니까 아니야. 21에 2를 더하면 23. 23은 세 박스로 나누면 2가 남고 다섯 박스로 나누면 3이 남아. 그래, 23박스다. 내 말 맞지?"

"사장님, 죄송하지만 그보다는 많이 왔습니다."

"뭐야? 아 씨. 계속 구해야 하잖아. 28에 2를 더하면 30. 이것도 아니고. 35에 2를 더하면 37. 이것도 아니고…."

  칠흑 같은 밤. 바다는 계속 일렁이고 사장은 검은 세단에 앉아 7의 배수에 2를 더해간다….

이 문제는 중국에서 시작되어…

서기 440년 경 남북조 시대(출처 : Ian Kiu, Wikipedeia Commons)

  고구려 장수왕이 재위하던 서기 5세기. 중국은 한족의 남조와 유목민족의 북조가 땅을 갈라 살았다. 이때를 남북조 시대라고 하는데, 이 글은 중국 역사 교과서가 아니므로 자세한 건 다른 사람한테 묻기 바란다. 아무튼, 이 5세기 즈음 중국에서 손자산경孫子算經이라는 책이 나온다. 글쓴이는 손자인데 손자병법을 쓴 손자와는 동명이인이다.

청나라 때 나온 손자산경

  손자산경은 상권, 중권, 하권으로 총 세 권이 있다. 이중 하권 26번 문제는 다음과 같다.

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

  언뜻 보기에는 쉽다. 나눗셈과 나머지는 초등학교만 나와도 아는 것이다. 복잡한 수식도 없고 이상한 그리스어 문자도 없다. 기쁜 마음에 답을 찾으려니 곧 아리송해진다. 3으로 나누어 2가 남는 수는 구하기 쉽다. 3의 배수에 2를 더하면 된다. 5로 나누어 3이 남는 수도, 7로 나누어 2가 남는 수도 구할 수 있다. 문제는 세 조건을 전부 만족하는 수를 구하는 일이다.

  검은 세단에 앉은 사장처럼 7의 배수에 2를 더한 다음 나머지 조건에 맞는지 계속 확인할 수도 있다. 아니면 이런 방법은 어떤가?

  사장은 23을 발견했다. 여러분이 숫자를 잔뜩 쓴다면 128도 찾아낼 수 있다.

그런데 그다음은? 또 그다음은?

  23이라는 답이 일찍 나와 망정이지, 첫 답이 19473이면 어쩔 뻔했을까? 사장은 다음 날 아침까지 계산해야 할 것이다.

  게다가 이 방법은 '수학적'이지 않다. 여기서 '수학적'이란 모범생이 칠판에 온갖 수식을 뽐내는 짓을 뜻하지 않는다. 사장처럼 하나하나 수를 알아보는 대신, 논리적 과정을 거쳐서 어떤 답을 딱 하고 내놓는 걸 말한다. 규칙을 찾는다면 23과 128 다음 수도 구할 수 있지 않을까?

합동식

  나쁜 소식과 좋은 소식이 있다. 나쁜 소식은, 여러분이 괴로운 학창 시절처럼 무언가 배워야 한다는 것이다. 좋은 소식은, 여러분 앞에는 나무판자에 절연테이프를 감고 휘두르는 수학 선생이 없다는 것이다.

3으로 나누어 2가 남는 수를 생각해보자. 2, 5, 7, 11… 이 있다. 예를 들어 11을 보자. 11은 3으로 나누어 2가 남는 수다. 소리쳐도 될 만큼 정확한 사실이다.

"11은 3으로 나누어 2가 남는 수다!"

  와. 띄어쓰기 포함 무려 21자다. 효율을 좋아하는 수학자들이 이걸 가만히 둘 리가 없다. 이들은 기어코 합동식이란 걸 발명하고 말았다.

이 글을 쓰는 사람도 공대생인 건 함정

  '11은 3으로 나누어 2가 남는 수다'는 합동식으로 이렇게 쓴다.

11≡2 (mod 3)

  ≡ 양옆에 있는 수는 mod 뒤에 있는 수로 나눈 나머지가 같다는 뜻이다. 그러니까 이렇게 써도 맞는 말이다.

11 ≡ 5 (mod 3)

11 ≡ 19 (mod 4)

  이때 이 식은 '11과 2는 법(modulo) 3에 대해 합동'이라고 읽는다.

합동식의 성질

  벌써 졸릴 것이다. 조금(아주) 졸리겠지만, 이걸 짚고 넘어가야 진행이 된다. 합동식을 통성명만 하고 끝낼 수는 없으니까 말이다. 합동식의 고향과 직업과 연봉도 물어봐야 한다.

1

자기 자신과는 무조건 합동이다

a≡a(mod m)

2

좌우 바꿔도 된다.

a≡b(mod m)이면 b≡a(mod m)

3

친구의 친구는 친구다.

a≡b(mod m)이고 b≡c(mod m)면

a≡c(mod m)다.

4

양옆으로 서로 더하고 뺄 수 있다.

a≡b(mod m)이고 c≡d(mod m)면

a±c≡b±d(mod m)다

5

양옆으로 서로 곱할 수 있다.

a≡b(mod m),c≡d(mod m)이면

ac≡bd(mod m)다

6

양옆으로 같이 제곱할 수 있다.

a≡b(mod m)면 a^k≡b^k(mod m)다.

7

mod 뒤 숫자를 좀 나누는 조건으로

양옆 숫자를 나눌 수 있다.

ab≡ac(mod m)이고 d=gcd(a, m)이면

b≡c(mod m/d)다.

* gcd : 최대공약수

* 특히 중요하니 눈여겨보도록

8

mod 뒤 숫자의 약수는 꿀빤다.

a≡b(mod m)고, n이 m의 약수라면

a≡b(mod n)다.

9

모든 이의 약수로 세계평화를 실천할 수 있다.

a≡b(mod m)고, 0보다 큰 d가 a, b, m의 공약수라면

a/d≡b/d (mod m/d)다.

  과연 이런 것들이 1500년 전 중국 사람이 낸 문제와 사장이 ‘위험한 물건’이 몇 상자인지 벌이는 고민과 무슨 상관일까? 당연히 상관이 있다.

다음 시간에 계속…….

2부 보러가기