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

  레온하르트 오일러(1707~1783)는 스위스에서 태어난 수학자입니다. 오일러라는 이름을 못 들어봤다면, 여러분은 한 분야에 인생을 매진했거나 수학에 담을 쌓은 사람일 겁니다.

  그 정도로 오일러는 수학에 엄청난 발자취를 남겼고 심지어 그 발자취 하나하나가 교과서를 장식합니다. 오일러는 함수를 $f(x)$로 쓰기 시작한 사람입니다. 또 자연상수 $e$, 지수함수와 로그함수를 대중화했습니다. '세상에서 제일 아름다운 공식'이라고 불리는 오일러의 공식을 발견했고, 심지어 기둥이 좌굴(기둥이 무게에 찌그러지는 대신 옆으로 꺾여버리는 현상. 좌굴을 일으키는 하중은 찌그러뜨리는 하중보다 작은 경우가 많아 꼭 대비해야 합니다.)하는 임계하중을 계산해내어 건축/토목공학에까지 자기 이름을 남겼습니다.

  '심심풀이로 읽는 수학' 등에 잘 나오는 이른바 '한붓그리기'도 오일러가 이론으로 승화했습니다. 그야말로 사람이 수학계에 세울 수 있는 업적은 거의 다 세웠다고 봐도 좋은 사람입니다. 삶이 곧 계산이자 수학이던 오일러는 1783년 76세의 나이에 뇌출혈로 사망합니다.

오일러의 정리

  오일러는 수학 전반에 걸쳐 업적을 남겼고, 오일러가 만든 공식과 기호도 많습니다. 이번에 살펴볼 것은 바로 오일러의 정리(Euler's theorem)입니다. 오일러의 공식(Euler's formula)와 헷갈리지 않도록 조심합시다. 물론 언젠가 오일러의 공식도 한 번 살펴볼 겁니다. 오일러의 정리는 다음과 같습니다.

  ≡는 보셨다시피 나눈 나머지가 같음을 나타내는 기호입니다. 나눗셈, 몫, 나머지랑 관련한 기호에 제곱이 당당하게 나오는 것이 신기합니다.

  그러나 아무 숫자나 넣어 보시면 공식이 맞음을 알게 됩니다. 예를 들어 10을 봅시다. 10 미만 자연수 중 10과 서로소인 수는 1, 3, 7, 9로 네 가지입니다. 즉 $\varphi(10)=4$입니다. 여기에 10과 서로소인 7을 a로 해 봅시다. 7^4는 2401입니다. 이걸 10으로 나누면 2401 = 10*240 + 1이 되어 나머지가 1입니다.

  합동식의 기본 개념을 '중국인의 나머지 정리'를 설명하면서 설명했습니다.

오일러의 정리 증명

  $\varphi(n)$에 해당되는 수(n보다 작으며 n과 서로소인 수)들만 모으면 $b_1, b_2 \dots$가 있다고 합시다.

(당연히 개수는 $\varphi(n)$)

  여기에 n과 서로소인 a를 곱하면 $ab_1, ab_2 \dots$가 됩니다. $b_1, b_2 \dots$가 모두 n과 서로소이고 a도 n과 서로소이므로 둘을 곱한 $ab_1, ab_2 \dots$도 n과 서로소입니다.

$ab_1, ab_2 \dots$를 n으로 나눕니다. 나머지는 서로 전부 다릅니다. 어떻게 알까요?

귀류법을 사용합니다. 귀류법은 일부러 틀리게 시작한 다음, 모순이 생기면 처음 가정이 틀리다고 결론 짓는 방법입니다. 그럼 나머지가 전부 다르지 않다, 같은 것이 있다고 가정해 봅시다.

  $ab_i \equiv ab_j \pmod{n}$ (단 i≠j)인 i와 j가 있다고 칩시다. ($= ab_i$를 n으로 나눈 나머지가 같은 i가 둘 있다) $ab_i \equiv ab_j$는 n으로 나눈 나머지가 같으므로 둘을 빼면 나머지가 상쇄해 n으로 나누어떨어질 겁니다.

  즉, $a(b_i-b_j)$가 n의 배수가 되는 셈이죠. a는 n과 서로소이므로 $(b_i-b_j)$쪽이 n의 배수입니다. b들은 n보다 작으면서 서로소인 수라고 했습니다. 당연히 전부 n 이하입니다. 이 b 둘을 뺐으니 차이의 절댓값도 n 보다 작습니다.

$-(n-1) \leq b_i-b_j \leq n-1$

그런데 이 범위에는 n의 배수가 있을 수 없습니다.

n=10이라면 $-(n-1)=-9, n-1=9$입니다.

-9와 9 사이엔 10의 배수가 없습니다.

$(b_i-b_j)$이 n의 배수인데 가능한 범위에 n의 배수가 존재하지 않다니요? 모순입니다.

따라서 귀류법에 따라 $ab_i$는 n으로 나눈 나머지가 같은 쌍이 있을 수 없습니다. 즉 나머지는 모두 다릅니다.

여기서 잠깐. 서로소를 나눈 나머지는 나눈 수와 서로소일까요?

X와 Y는 서로소다. X를 Y로 나눈 나머지는 Y와 서로소인가?로 써 봅시다.

이번에도 귀류법을 사용합니다.

Y와 나머지 Z가 서로소가 아니라고 해 보죠.

$Y=ay, Z=az (a \neq 1)$로 쓸 수 있습니다. a라는 1이 아닌 공약수가 있는 것이죠.

나눗셈은 $X = ay*m + az = a(ym + z)$로 표현 가능합니다.

$X =a(ym + z)$로 X는 a의 배수입니다.

X가 a의 배수라면 Y와 서로소라는 가정을 어기므로

귀류법에 따라 Y와 Z는 서로소입니다.

이렇게 n과 $ab_i$도 서로소이므로 n으로 나눈 나머지도 n과 서로소입니다.

$ab_1, ab_2 \dots$를 n으로 나눈 나머지들은

1) n보다 작고

2) n과 서로소고

3) 개수가 'n보다 작고 서로소인 숫자'들 개수와 같다.

그러므로 이 나머지들은 $b_1, b_2 \dots$와 순서는 다를지 몰라도 내용물이 완전히 같습니다.

  합동식은 mod 뒤 숫자만 같으면 여러 합동식이 있을 때 좌변은 좌변끼리, 우변은 우변끼리 곱해도 합동이 성립합니다.

$ab_1 \equiv \bigcirc_1 \pmod{n}$

$ab_2 \equiv \bigcirc_2 \pmod{n}$

$\dots$

↓

$ab_1 \times ab_2 \dots \equiv \bigcirc_1 \times \bigcirc_2  \dots \pmod{n}$

○들은 순서는 몰라도 내용물은 전부 $b_1, b_2 \dots$와 같습니다. 다 곱해버렸으니 이제 순서는 상관이 없겠죠. 따라서 

$ab_1 \times ab_2 \dots \equiv b_1 \times b_2 \dots \pmod{n}$

$ab_1 \times ab_2 \dots = a^{\varphi(n)} \times b_1 \times b_2 \dots $

로 쓸 수 있으니까 결과적으로

$a^{\varphi(n)} \times b_1 \times b_2 \dots \equiv b_1 \times b_2 \dots \pmod{n}$

입니다.

$b_1 \times b_2 \dots $는 n과 서로소고 최대공약수는 1이므로

합동식 성질에 따라

$ ab \equiv ac \pmod{m} $

일 때 d='a와 m의 최대공약수'라면

$b \equiv c \pmod{m/d}$로 나눌 수 있습니다.

  이 식에선 $b_1 \times b_2 \dots $와 n은 서로소니까 최대공약수 d=1입니다. 그러니 $b_1 \times b_2 \dots $로 나눠도 mod 뒤에 있는 n은 1로 나뉘어 똑같겠네요.

$1 \equiv a^{\varphi{n}} \pmod{n}$

페르마의 소정리

  수학자 하면 페르마도 빼놓을 수 없습니다. 비록 아마추어 수학자라고는 하지만 웬만한 프로 수학자만큼 업적이 대단한 사람이죠. 그 유명한 페르마의 마지막 정리로 수학자들을 고생시킨 장본인이고요.

페르마의 소정리(Fermat's little theorem)는 다음과 같습니다.

  페르마의 소정리는 오일러의 정리에 n 대신 소수 p를 입력하면 됩니다. 소수는 1과 자기 자신 빼고는 약수가 없는 수입니다. 따라서 소수 미만 자연수는 전부 그 소수와 서로소입니다.($\varphi(p)= p-1$)

응용

  페르마의 정리는 솔직히 실생활에 거의 쓸모가 없는 공식입니다. 주로 수학경진대회에 나와서 학생들의 골머리를 아프게 하죠.

문제 예) 7^2016의 마지막 세 자리를 구하시오

풀이 ) $\varphi(1000) = 400$임을 이미 아는 상태에서 시작하자.

$a=7, n=1000$으로 놓으면

$7^{400} \equiv 1 \pmod{1000}$이다.

$7^{2016} = (7^{400})^5 * 7^{16}$이고

$7^{2016} \equiv (7^{400})^5 * 7^{16} \pmod{1000}$이며

($a \equiv a \pmod{m}$이니까)

$7^{2016}$을 1000으로 나눈 나머지(마지막 세 자리)는

$(7^{400})^5 * 7^{16}$을 1000으로 나눈 나머지와 같다.

$(7^{400})^5$는 1000으로 나눈 나머지가 1이므로

......001로 끝난다. 여기에 $7^{16}$을 곱한 수는

마지막 세 자리가 $7^{16}$과 같다. 그러므로

$7^{2016}$의 마지막 세 자리는 $7^{16}$의 마지막 세 자리와 같다.

(물론 $7^{16}$의 마지막 세 자리도 구하긴 어렵겠지만)

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부 보러가기

시작하는 이야기

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

"사장님."

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

"뭔데?"

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

"작업 끝났습니다."

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

"갯수는 확인했고?"

"그게..."

"무슨 일 있어?"

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

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

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

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

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

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

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

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

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

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

"어디 보자. 일곱 박스씩 보내면 두 박스가 남는다 그랬지? 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부 보러가기