2016년 2월 9일 화요일

나눗셈과 진법(Division and Numeral System)

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


[그림 1] 나눗셈의 원리(출처: wikipedia.org)

누구나 안다고 생각하는 나눗셈에 비밀이 숨겨져 있음을 알고 있는가? 여기서 말하는 나눗셈은 무언가 특별한 연산이 아니다. 우리가 계산에 흔히 사용하는 바로 그 셈법이다. 잘 알고 있듯이, 나눗셈은 어떤 수를 몫(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]. 이전 수학자들이 어렴풋하게 도출했던 기초적인 진법 발상을 세련되게 표현했던 라이프니츠는 이진법을 기반으로 수 체계를 바라보는 새로운 관점을 지속적으로 제시했다. 나눗셈의 유일성 정리로 얻을 수 있는 중요한 결과 중 하나가 아래에 있는 유클리드의 보조 정리이다. 이 보조 정리 증명을 통해 우리가 당연하게 생각하던 나눗셈과 인수 분해에 대한 이해의 폭을 솟수(素數, prime number) 개념을 기반으로 넓힐 수 있다.[1989년부터 시행된 한글맞춤법에 따르면 소수(素數, prime number)로 해야 타당하나, 소수(小數, decimal fraction)와 구별되지 않으므로 옛날 표기인 솟수를 고집한다.]

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

[증명]
일견 당연한 듯한 이 보조 정리에서 증명해야 할 부분은 무엇일까? 자연수 $a$, $b$가 $p$의 배수가 아니면, 그 곱 $ab$도 $p$의 배수가 될 수 없다는 부분이 핵심이다. 이를 입증하면 유클리드의 보조 정리도 자동으로 증명된다. 먼저 나눗셈의 유일성을 이용하면 다음을 얻는다.

                        (6)

여기서 $m$과 $n$은 0을 포함한 자연수, $a$ = $q_a p+r_a$, $b$ = $q_b p+r_b$, $0 \le r_{a,b} < p$. 나머지 $r_a$, $r_b$는 $p$보다 작기 때문에 $r_a r_b$는 $p^2$ 범위 안에 있다. 솟수 제곱인 $p^2$ 내의 자연수 중에서 $p$의 배수가 되는 경우는 $np$만 가능하다. 만약 $r_a$ = $p-1$이라면, $r_b$ = $p$가 되어야만 식 (6)를 만족한다. 이를 이해하기 위해 $p$의 배수인 항 $r_a r_b$를 보자. 나머지 $r_a$를 이 항에 대입하면 $r_a r_b$ = $p r_b - r_b$이다. $p$의 배수가 되려면 당연히 $r_b$ = $p$가 되어야 한다. 하지만 $r_b$ 조건 때문에 $r_b$ = $p$가 될 수 없다. 마찬가지로 $r_a$ = $p-2$라면, $2r_b$ = $p$가 되어야 한다. 더 구체적으로 보면, $r_a r_b$ = $p r_b - 2r_b$이므로 $r_b$ = $p/2$가 된다. 하지만 $p$가 솟수이므로 이는 불가능하다. 비슷하게 나머지 $r_a$를 줄여가면서 이 과정을 계속 반복하면 0이 아닌 어떤 $r_a$에 대해서도 가능한 경우를 찾을 수 없다. 따라서 $n$ = $0$, 즉 $r_a$ 혹은 $r_b$가 0인 경우만 식 (6)을 만족한다.
______________________________

위에 증명한 유클리드의 보조 정리는 두 자연수의 곱만 다루었지만, 동일한 논리 구조를 이용하면 다수 개의 곱에 대해서도 유클리드의 보조 정리가 성립함을 알 수 있다. 위 정리를 이용하면 산술의 기본 정리(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$에 대해 유클리드의 보조 정리를 다시 사용한다. 이 과정을 계속 반복하면 솟수만 가진 소인수 분해는 유일함을 증명할 수 있다.

나눗셈은 워낙 오래되고 유명한 연산이라서 몫과 나머지를 구하기 위한 전용 함수가 여러 가지로 정의된다. 나머지(remainder) 함수는 $\operatorname{rem}(m, n)$으로 표기한다. 함수 $\operatorname{rem}(m, n)$은 $m$을 $n$으로 나눈 나머지를 뜻한다. 몫이 출력되는 함수는 바닥 나눗셈(floor division)인 $\operatorname{fdiv}(m, n)$로 표현된다. 이 개념은 바닥 함수(floor function) $\lfloor x \rfloor$와 나눗셈을 합쳐서 구성한다.

                          (7)

여기서 $\lfloor x \rfloor$ = $[x]$는 실수 $x$를 넘지 않는 최대 정수 함수(greatest integer function)이다. 바닥 함수 $\lfloor x \rfloor$의 상보 함수는 천장 함수(ceiling function) $\lceil x \rceil$이다. 천장 함수는 $x$와 같거나 이 값을 넘어서는 최소 정수 함수(least integer function)를 의미한다. 바닥 함수를 써서 실수 $x$의 소수부(小數部, fractional part)를 얻는 함수 $\{x\}$도 정의할 수 있다.

                          (8)

바닥 함수는 실수 영역에서 정의되기 때문에 식 (8)을 써서 나머지 함수의 정의역을 실수 전체로 확장할 수 있다.

                          (8)

여기서 나머지 함수의 정의역은 식 (2)에 나온 나머지의 개념에 부합한다.

[참고문헌]
[1] A. Glaser, History of Binary and Other Nondecimal Numeration, 2nd ed., Tomash Publishers, 1981.
[2] G. H. Hardy, E. M. Wright, and A. Wiles, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008.

[다음 읽을거리]

댓글 28개 :

  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님. ^^
      천재들도 수년 동안 같은 문제를 고민하는데, 평범한 사람들은 더 많은 시간을 투자해야 해요.

      삭제
  6. 전파거북이님 안녕하세요, 가끔가끔 블로그에 들어와 글을 읽고 가는데 근래에 들어 처음부터 끝까지 전파거북이님의 논리적 전개 흐름을 이해하고자 처음부터 정주행하고 있습니다ㅎㅎ 유클리드 보조정리 중명부분에서 이해 못한 부분이 있어 질문하고자 합니다.
    b와 p가 서로소라는 가정에 의해, (m-qb)가 b의 배수가 되어야 한다는 말씀을 하셨습니다. 현재 유클리드 보조정리가 ab가 p의 배수라면 a 혹은 b가 필히 p의 배수인데, 위의 말씀이 맞다고 한다면 저런 까다로운 절차 없이 a가 p와 서로소 가정하면 b는 p의 배수이다 혹은 b가 p와 서로소라면 a는 p의 배수이다 라는 문장으로 증명이 완성되지 않을까 싶습니다. 즉,"(m-qb)가 b의 배수가 되어야 한다"에 관한 증명이 요구되는 것이 아닐까 싶습니다.

    답글삭제
    답글
    1. 정확한 지적 감사합니다, Unknown님. ^^ 본문의 증명을 수정했습니다.

      삭제
  7. 안녕하세요 여쭤보고 싶은게 있어서 댓글 남깁니다.수학적인 과정은 모두 이해 가능하나 논리적 구조에서 이해가 안되는 점이 있습니다.

    모든 자연수는 소수의 곱으로 표현 가능하며 유일한 소인수분해를 갖는다 라는 증명에서

    최초 가정인 n이 두가지 소인수 분해를 가능한 최소수다.에서 결국 나눗셈 정리를 이용하여 n이 최소수가 아님을 밝혀냄으로써 최초 가정이 틀렸음을 증명한 것은 알겠습니다.

    그런데 이것이 어떻게 두 가지 소인수분해를 가능하다의 가정을 깨트린 것인지 모르겠습니다.n이 최소수가 아님을 밝힌것까지는 알겠으나 어떻게 이 과정이 유일한 소인수분해이다를 말할 수 있는것인지 설명 부탁드립니다!

    답글삭제
    답글
    1. 산술의 기본 정리를 말씀하시는 거죠?
      기본적으로는 귀류법을 따르고 있어요. 두 가지 종류의 솟수로 소인수 분해가 된다면 그런 합성수 중에서 가장 작은 합성수가 있을 겁니다. 하지만 증명 과정을 따라가보면 그런 합성수는 없어요. 없다면 어떤 결론을 내려야 할까요? 합성수는 최소수가 있는데 두 가지로 소인수 분해하는 합성수는 없기 때문에 합성수 자체가 없어요. 이는 두 가지 종류로 분해될 수 있는 합성수는 없다입니다. 그래서 소인수 분해를 두 가지 방법으로 할 수는 없고 유일해야 합니다.

      삭제
  8. 안녕하세요. 항상 잘 보고있습니다 감사합니다!
    아래의 본문내용이 이해가 되지 않아서, 질문을 남깁니다.

    식 (6) 관련

    만약 ra=p−2라면, 2rb=p가 되어야 하지만 p가 솟수이므로 이는 불가능하다.

    위 본문내용은 ra=p-2이고 2rb=p이면 식 (6) rarb = np 즉 p의 배수가 성립한다의 뜻 같은데
    이 부분이 이해가 되질 않아서 몇시간째 고민을 하는중인데 모르겠습니다. 가르침을 을 주실 수 있을까요?

    답글삭제
    답글
    1. 익명님, 본문을 더 구체적으로 썼어요 ^^

      삭제
  9. 빠른 답변 감사드립니다.
    죄송한데, 한번만 더 여쭤봐도 될까요?

    rarb=prb−2rb이므로 rb=p/2면 rarb=prb-2rb= p의 배수 라는게 여전히 이해가 되지 않습니다.

    제 생각은 아래와 같은데
    p가 2인 경우는 ra=p-2 가 0 이라 논외하고
    p가 2가 아닌 솟수(홀수)인 경우는 prb 라는 건 p라는 솟수가 rb개만큼 존재하여 이것을 다 더한것이므로
    rb가 p/2일 경우 p가 홀수인 솟수이므로 2로 나누어 떨어지지 않으므로 rb는 자연수가 아니고
    가령 p가 13이라고 가정하면, 이 경우 prb는 p가 6.5개만큼 존재하고 이것을 다 더한 것 즉 13x6.5=84.5 이건 결국 6.5p - 2rb
    인데 그럼 84.5 - 13 = 71.5 71.5는 13의 배수가 아님

    수학을 처음하다보니 어디가 잘못되었는지 모르겠습니다.

    답글삭제
    답글
    1. 익명님, 우리가 생각하는 수 범위는 자연수입니다. 그래서 소수가 출현할 수 없어요.
      $p$가 2보다 큰 솟수라면 $p/2$는 절대 자연수가 될 수 없어요. 그래서 $p/2$는 불가능한 수예요.

      삭제
    2. 처음부터 이해가 안된건...

      ra가 p-1이고 rb가 p이면
      rb가 p가 될 수 없음은 차치하더라도
      rarb는 p의 배수임이 이해되지만

      ra가 p-2이고 rb가 p/2이면
      rb가 p/2가 될 수 없음은 저도 알고있지만

      rarb가 p의 배수가 맞느냐?에서 이해가 안되네요

      ra가 p-2면 rb가 p/2일때 rarb가 p의 배수가 성립되어서 쓰신게 아닌가요?
      rb가 p/2란 값이 불가능한것은 후술하더라도요

      계속 번거롭게하여서 죄송합니다

      삭제
    3. $r_a r_b$가 $p$의 배수임은 식 (6)의 둘째식에 증명이 있어요. 다음 절차로 식 (6)의 밑에 있는 내용은 $r_a r_b$가 $p$의 배수이므로 $r_a r_b = 0$임을 증명하고 있어요. 그래서 유클리드의 보조 정리가 증명됩니다.

      삭제
    4. 이해하지못해 여러번 질문드렸는데 매번 답변 감사드립니다!

      삭제
  10. 나눗셈의 유일성 증명에서 a=b1c+r1=b2c+r2라고 가정하셨는데, b1과 b2가 서로 다른 몫일 때 왜 c는 같은 값이라고 둘 수 있는 건가요? c도 c1과 c2로 나누어 a=b1c1+r1=b2c2+r2로 가정하고 증명해야 하는 거 아닌가요?

    답글삭제
    답글
    1. 아 설마... a를 b로 나눈다는 상황에서 몫과 나머지 쌍이 유일하다는 것의 증명이었던 건가요? 기본 전제가 a를 b로 나눈다는 전제라면 b가 b1과 b2로 나뉘지 않는 것이 이해가 가네요.

      삭제
    2. 맞습니다. 나눗셈이 전제라서 b는 고정됩니다.

      삭제

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