2016년 2월 9일 화요일

나눗셈과 진법(division and numeral system)


[경고] 아래 글을 읽지 않고 "나눗셈과 진법"을 보면 바보로 느껴질 수 있습니다.
1. 2의 제곱근은 무리수


누구나 안다고 생각하는 나눗셈에 비밀이 숨겨져 있는 것을 알고 있는가? 여기서 말하는 나눗셈은 무언가 특별한 것은 아니다. 우리가 계산에 흔히 사용하는 바로 그 셈법이다. 잘 알고 있는 것처럼, 나눗셈은 어떤 수를 몫(quotient)과 나머지(remainder)로 분리하는 초보적인 계산법이다. 이걸 수학식으로 표현하면 다음과 같다.


                        (1)

식 (1)은 $a$를 $b$로 나눌 때 얻어지는 몫 $q$와 나머지 $r$을 표현한 수식이다. 여기서 아주 초보적이지만 근본적인 질문을 해보자. 식 (1)은 왜 이 형태대로 정의해야 하는가? 나눗셈을 정의하는 다른 방법은 없는가? 이런 질문들로 인해 수학의 근원적 기반을 잘 이해할 수 있고, 해답을 찾는 과정에서 다른 풍성한 결과를 도출할 수 있다.
먼저 근본 질문에 대한 답을 하기 위해 다음처럼 식 (1)의 유일성을 증명해보자.

[나눗셈의 유일성]
몫과 나머지로 구성한 자연수 나눗셈은 아래와 같이 유일하게 정의된다. 

                        (2)

여기서 $a$, $b$, $q$, $r$은 0을 포함한 자연수이며 $0 \le r < b$.

[증명]
유일성 증명을 위해 식 (2)의 몫과 나머지가 다르다고 가정하자. 몫만 다르거나 나머지만 다를 수는 없으므로, 몫과 나머지가 모두 다르다고 하자. 그러면,

                        (3)

식 (3)의 좌변과 우변을 살펴보자. $r_1 \ne r_2$이므로 우변은 정수가 아닌 유리수가 나온다. 하지만 좌변은 정수가 나와야 하므로, 좌변과 우변이 같을 수 없는 모순된 결과가 얻어진다. 따라서 $r_1 = r_2$가 성립해야 하며, 연달아서 $q_1 = q_2$도 얻어진다.
______________________________

위 정리는 자연수로 한정하여 증명했지만, $0 \le r < b$인 조건에서 $a$, $b$, $q$를 정수로 확장하더라도 식 (3)과 동일한 방식으로 모순을 이끌어낼 수 있다. 이상을 종합하면 나눗셈의 유일성은 정수 범위까지 성립한다. 위 정리에서 한 걸음 더 나가면 진법(進法, numeral system)의 유일성도 자연스럽게 증명된다.

[진법의 유일성]
자연수 $a$를 $b$진법으로 표현하는 방법은 단 하나이다. 

                        (4)

여기서 $0 \le q_0, q_1, \cdots, q_{n-1}, q_n < b$.

[증명]
나눗셈의 유일성에 의해 자연수 $b$가 주어지면, $a = p_1 b + q_0$으로만 표현할 수 있다. 만약 $p_1 \ge b$라면, 다시 $p_1 = p_2 b + q_1$로 바꾼다. 이 과정을 계속 반복하면서 $p_{n} < b$가 되면, $q_n = p_{n}$으로 바꾸고 나눗셈을 멈춘다. 그러면,

                   (5)
______________________________

현시점의 우리에게는 십진법 이외의 진법 체계가 익숙하지만, 새로운 진법 체계가 수학적으로 체계화된 시기는 의외로 오래지 않다. 곱셈이 가능한 계산기를 발명했던 라이프니츠(Gottfried Wilhelm Leibniz, 1646-1716)가 주역(周易)을 공부하면서 음양 이론을 바탕으로 1679년(라이프니츠 33살, 조선 숙종 시절)에 0과 1만을 사용하는 이진법(binary number system)을 제안하고 이진수의 산술 체계를 구체화했다[1]. 이전 수학자들이 어렴풋하게 도출했던 진법 아이디어를 세련되게 표현했던 라이프니츠는 이진법을 기반으로 수 체계를 바라보는 새로운 관점을 지속적으로 제시했다.
나눗셈의 유일성 정리로 얻을 수 있는 중요한 결과 중 하나가 아래에 있는 유클리드의 보조 정리이다. 이 보조 정리 증명을 통해 우리가 당연하게 생각했던 나눗셈과 인수 분해에 대한 이해의 폭을 넓힐 수 있다.

[유클리드의 보조 정리(Euclid's lemma)]
솟수 $p$가 두 자연수의 곱 $ab$를 나눈다면, $p$는 반드시 $a$ 혹은 $b$를 나눈다.

[증명]
솟수 $p$가 $ab$를 나눌 수 있으므로, 나눗셈의 유일성을 이용하면 다음을 얻는다.

                        (6)

여기서 $q$, $r$, $m$은 0을 포함한 자연수, $a = qp+r$, $0 \le r < p$. 또한 나머지 $r$의 범위를 생각하면, $qb \le m < (q+1)b$가 성립한다.
만약 $b$와 $p$가 서로소인 경우, $p/b$는 자연수가 될 수 없고 $r$은 0을 포함한 자연수이므로 $b$는 $(m-qb)$의 배수가 되어야 한다. $m$의 가능 범위를 생각하면, $m = qb$ 및 $r = 0$을 얻을 수 있다. 따라서 $ab = qp \cdot b$가 되므로, $a$는 $p$의 배수가 되어야 한다. 이와 유사하게 $a$와 $p$가 서로소인 경우도 쉽게 증명할 수 있다.
______________________________

위에 증명한 유클리드의 보조 정리는 두 자연수의 곱만 다루었지만, 동일한 논리 구조를 이용하면 다수 개의 곱에 대해서도 유클리드의 보조 정리가 성립한다는 것을 알 수 있다.
위 정리를 이용하면 산술의 기본 정리(fundamental theorem of arithmetic)도 쉽게 증명 가능하다. 사실 유클리드의 보조 정리는 산술의 기본 정리와 거의 등가이다. 증명을 위해 어떤 자연수 $n$이 두 종류로 소인수 분해가 가능하다고 $n = p_1 p_2 \cdots p_M = q_1 q_2 \cdots q_N$처럼 가정하자. 유클리드의 보조 정리에 의해 $n$은 $p_1$로 나누어지므로, $q_1 q_2 \cdots q_N$ 중 하나는 $p_1$로 나누어져야 한다. 예를 들어 $q_1$이 $p_1$로 나누어진다면, $p_1 = q_1$이므로 $p_2 \cdots p_M = q_2 \cdots q_N$에 대해 유클리드의 보조 정리를 다시 사용한다. 이 과정을 계속 반복하면 솟수만 가진 소인수 분해는 유일하다는 것을 증명할 수 있다.

[참고문헌]
Tomash Publishers, 1981.

댓글 14개 :

  1. 안녕하세요.
    전파거북이 님께서 올려주신 글들이 참 좋아서 인쇄해서 보고 싶습니다.
    그런데 블로그 특성인지, 수학 탭을 눌렀을 때 글의 목록이 나오지 않는 점이 약간 아쉽네요.

    (1) 수학 글의 목록을 볼 수 있는 방법이 있나요? (네이버 블로그 같은 식으로 제목만)
    (2) 인쇄 버튼이 혹시 숨겨져있나요..?
    (3) 혹시 괜찮은 입문용 정수론 한국어 책이 있나 여쭤보고 싶습니다.

    읽어주셔서 감사합니다. 좋은 하루 보내셔요. 오늘은 다 지났지만...

    답글삭제
    답글
    1. 방문 감사해요, 한도영님. ^^

      1. 탭은 블로거 제공 기능을 쓰고 있어 저도 방법이 없습니다. 수학글 목차는 아래 링크에 모으고 있습니다.

      http://blog.naver.com/ghebook/30113491161

      2. 블로거에서는 인쇄 기능을 제공하고 있지는 않네요.

      3. 한글로 된 책은 잘 모르겠네요. 좋은 영어책 번역본을 찾아보시는 것도 좋지 않을까요. 아래 한 번 참고해보세요.

      G. H. Hardy, E. M. Wright, and A. Wiles, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008.

      제4판은 인터넷에도 공개되어 있습니다.

      http://matematica.cubaeduca.cu/medias/pdf/842.pdf

      삭제
    2. 소중한 답변 감사합니다. 앞으로도 들러서 많이 배우겠습니다. ^^

      삭제
    3. 아 블로글 글 잘 보고 갑니다. 전 구글 블로그 잘안보는데 잼있는 그루이 많습니다.
      제.블로그는 www.blog.naver.com/sirianoo
      구여 좋은글 많이 보고 갑니다.

      삭제
  2. 나눗셈만 잘해도 산술의 기본정리는 증명이 되는군요 ㅋㅋ
    귀류법을 이용한 증명은 편리하긴 한데 뭔가 직관적인 이해가 좀 결여된 부분이 있다는 느낌이 강하게 들었었는데, 이 증명은 소인수분해의 일의성에 대한 직관에 부합하는 것 같아서 굉장히 좋은 것 같습니다. 감사합니다^^

    답글삭제
    답글
    1. 나눗셈마저도 그냥 받아들일 수 없다는 것이지요. 수학의 세계는 끝이 없습니다. ^^

      삭제
  3. 오랜만입니다 전파거북이님
    중고등학생때 가끔씩 방문해서 글을 읽곤 했었는데
    제가 어느덧 대학생이 되었어요!
    앞으로는 더 자주 방문할 것 같네요 :)
    양질의 글들 감사합니다!

    답글삭제
    답글
    1. 중고등 시절에 이런 글을 보려면 어려운데 대단했네요. ^^
      대학생으로서 많은 꿈을 꾸고 이루기를 바랍니다, 익명님.

      삭제
  4. 맥스웰 방정식에 대해 알아보다가 프로필에 깊은 감명을 받고 다른 글들도 천천히 읽고 있습니다. 그런데 전파거북이님, 혹시 실례가 되지 않는다면 본 블로그의 글들을 제가 보는 용도로 종이책으로 제본해도 될까요? 기숙사에 다니는 고등학생인지라 컴퓨터로 보는 건 상황이 여의치가 않아서요. 항상 좋은 글 감사합니다.

    답글삭제
    답글
    1. 인터넷에 공개한 것이라서 제본하셔도 문제 없습니다. ^^

      삭제
  5. 안녕하세요! 대학원을 준비하며 틈틈히 수학을 기초부터 다시 다지고 있는 학생입니다! 저는 그동안 위키피디아를 보면서 링크타고타고 나름 정리하면서 공부하다 푸리에변환을 보다 블로그를 알게 되었고 정말 체계적인 정리와 트리를 보면서 감명받아 미분법의 이해부터 다시 차근차근 보고있습니다! 위키로 볼때보다 이해면,속도면에서 정말 많은 도움이되네요

    한가지 여쭈고 싶은게 혹시 블로그에 글을 게시하시면서 정리할때 자료와 내용등은 어떻게 준비,정리하시나요. 저도 전파거북이님처럼 개인적으로 지금까지 공부했던 내용들을 체계적으로 정리하고 싶은데 단순히 번역하는 정도 인것 같아서 제대로 안된다고 생각하네요 ㅜㅜ 팁 있으시면 알려주세요 ㅎㅎ

    답글삭제
    답글
    1. 안녕하세요, Jung-sub님. ^^ 원하시는 대학원에 꼭 가셔서 마음껏 공부하시길 바랍니다.

      수학이나 물리학 내용은 세부적인 내용을 빠짐없이 이해할 때까지 계속 고민합니다. 저는 이런 방식이 좋아요.

      삭제
    2. 고민한다는 것은 나쁜게 아니군요. 전 고민하면 머리가 너무 아파서 나쁜 것인줄 알았는데. 아니네요! 감사합니다!

      삭제
    3. 많이 고민해야 많이 발전한다는 것이 전파거북이의 지론입니다, Jaewoo님. ^^
      천재들도 수년 동안 같은 문제를 고민하는데, 평범한 사람들은 더 많은 시간을 투자해야 해요.

      삭제

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.