나눗셈과 진법(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.

[다음 읽을거리]

1. 연분수