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

1부 보러가기

3 으로 나누어 2가 남고,

5로 나누어 3이 남고,

7로 나누어 2가 남는 수는?

합동방정식

---

  지난 시간엔 사장의 고민과 5세기 중국인의 고민을 같이 살펴봤다. 보기엔 별것 아닌 듯 보여도 막상 풀려니 안 풀리는 문제였다. 이제 여러분은 ≡과 합동을 대강 알게 되었다. 그럼 문제로 들어가 볼까?

  사장은 조건에 맞는 수를 구하느라 진을 빼는 중이다. 알지 못하는 수를 우리는 미지수라고 부른다. 미지수가 들어간 식을 방정식이라고 한다. 우리가 자주 보는 방정식은 이렇게 생겼다.

$4x + 15 = 9$

$x^2 - 6x + 9 = 16$

(참고로 위 식 해는 $x=-4$, 아래는 $x=7, -1$이다.)

  이렇듯 =를 사이에 두고 모르는 숫자 x가 있어 그걸 풀 수 있다. 그럼 ≡가 있는 방정식은 없을까? 합동식인데 x가 있는 방정식이니, 이런 식을 합동방정식이라 부르자.

보통 1차합동방정식은 이렇게 생겼다.

$25x\equiv10 \pmod{15}$

  $25x$는 15로 나누어 10이 남는다는 말이다. 이 정도면 계산이 필요 없긴 하다. $x=1$ 이면 $25\equiv10 \pmod{15}$니까 맞다. $x=2$는 성립 안 하고, $x=3$이면 $75\equiv10 \pmod{15}$가 성립한다.

아마 답은 $x= 1, 3, 5\dotsc$인 모양이다. 이렇게 합동방정식의 해는 하나가 아니며 ≡를 넣어 표현할 수 있다. 위 같은 경우는 $x\equiv1 \pmod{2}$일 것이다.

일차합동식 풀어보기

---

  그럼 $25 \equiv10 \pmod{15}$를 '수학적'으로 풀어보자. 사장이 원하는 답은 일차합동식과 큰 관련이 있다.

  우리가 알고 싶은 건 $ax \equiv b \pmod{m}$을 만족하는 x다. ≡가 있는 걸 보니 ax와 b는 m으로 나눈 나머지가 같다. 식으로 표현하면 이렇다.

ax = □m + ※

b  = △m + ※

(□, △, ※는 당연히 정수다)

※가 공통이니까 따로 정리할 수 있다. 따라서

※ = ax-□m = b-△m,

ax-b = (□-△)m = km

이다.

  a, b, m은 알고 x, k는 모른다. 그런데 k를 y로 바꾸면 x와 y가 있는, 그나마 보기에 평범한 식이다.

$ax - my = b$

  이런 방정식을 선형 디오판토스 방정식이라고 한다. 옛날 그리스 수학자 디오판토스가 열심히 연구해서 이런 이름이 붙었다. 여기서 디오판토스 방정식을 구구절절 설명할 생각은 없다. 하나 확실한 건, 선형 디오판토스 방정식에 해가 존재하려면 b가 (a, m)의 최대공약수에 나누어떨어져야 한다는 점이다.

  a, m의 최대공약수를 d라고 부르자. 즉 b가 d에 나누어떨어져야만 위 일차합동식의 해가 존재한다.

  만약 저 조건이 맞아서 정수해가 존재한다고 하자. 그럼 그 해는 얼마일까? 다행히 수학자들이 다 구해 두었다.

  헷갈리지 않게 원래 식으로 쓰자면 u와 v는 각각 a와 m을 $gcd(a, m)$으로 나눈 값이다.

  보다시피 선형 디오판토스 방정식의 x는 가짓수가 무한하다(존재한다면). 그러나 우리는 합동식을 푸니까 x는 0보다는 크고 b보다는 작아야 함을 잊지 말자.

  디오판토스 방정식에서 해를 $x_0$, $y_0$라고 하자. $x_{0}$는 수많은 해 중에 제일 작은 양수다. 선형 디오판토스 방정식의 해에 따라 정수해 쌍은 $(x,y)=(x_0+\frac{mk}{d}, y_0-\frac{ak}{d})$다. 이 쌍의 x들이 우리가 원하는 일차합동식의 해가 되어줄 것이다.

잠깐, $x=x_{0}+\frac{mk}{d}$라고?

그럼 x는 '$\frac{m}{d}$의 정수곱에 $x_{0}$를 더한 것'이라고 말해도 되겠네?

그럼 $x \equiv x_{0} \pmod{{m/d} }$라고 불러도 되지 않을까?

  바로 예시로 들어가 보자.

예시- $35x \equiv14 \pmod{21}$의 해는?

성질 7

“$ab \equiv{ac} \pmod{m}$ 이고  $d=gcd(a, m)$ 이면 $b \equiv c \pmod{m/d}$다.”

를 기억하는가?

이 공식을 알면 합동식 양변을 나누어 쉽게 문제를 풀 수 있다.

  위 식을 쪼개면 $7 \times 5x \equiv 7 \times 2 \pmod{21}$이 된다. 7과 21의 최대공약수는 7이니까 $5x \equiv 2 \pmod{21/7=3}$으로 바꾸어 쓸 수 있다. 디오판토스 식으로 쓰면 $5x-3y = 2$고 제일 단순한 해는 'x가 1, y가 1'이다.

  단순해진 합동식은 더는 나눌 수가 없으니 여기서 멈추자. 이 단순해진 디오판토스 방정식의 해는 $(1 + k \times 3/1 , 1 – k \times 5/1)=(1+3k, 1-5k)$다. 우리한테는 x만 필요하니 결국 해는 $x \equiv 1 \pmod{3}$이다.(다른 말로 하면 3으로 나누어 나머지가 1인 수, 그러니까 1, 4, 7, 10....인 것이다.)

  근데 이건 단순해진 디오판토스 식의 해일 뿐 우리가 원하는 디오판토스 식의 해가 아니다. 물론 1, 4, 7, 10… 도 답이지만 뭔가 부족하다.

$35x \equiv 14 \pmod{21}$역시 쉬운 해를 구해서 $mk/d$를 더하면 일반적인 해가 될 텐데….

아까 구한 1, 4, 7, 10... 이 쉬운 해 아닌가!

$x_{0}=1$이라면 $1+k21/7=1+3k  \to x \equiv1 \pmod{21}$

$x_{0}=4$라면 $4+k21/7=4+3k \to x \equiv4 \pmod{21} \dots$

  ($x \equiv 22 \pmod{21}$부터는 쓰지 말자. 21로 나누어 나머지가 어떻게 21이냐는 말이다.)

  이렇게 일차합동방정식의 해를 구해 보았다. 보다시피 해는 7가지가 나왔다. 물론 이보다 더 복잡한 일차합동식이 있으며, 지금 배운 방법으로 풀 수 없는 합동식도 있지만 우린 여기까지만 하자. 필요한 건 다 챙겼으니 말이다.

  다음 시간에...

3부 보러가기