나눗셈 정리(Division theorem)

중고교 수학에서 젯수와 피젯수를 몫과 나머지에 관한 식으로 정리한 적이 있습니다. 이제 그 정리가 왜 성립하고, 유일하게 존재하는지를 증명하여 확실히 옳음을 확인해 보겠습니다.

 

 

---

1. 나눗셈 정리

 

정리($N.T$) 1.4
[나눗셈 정리(Division Theorem)]
임의의 두 정수 $a,b\;(b\ge 1)$ 이 주어졌을 때, 다음의 등식을 만족하는 유일한 정수 $q$ 와 $r$ 이 존재한다. 이들을 각각 '몫(quotient)'과 '나머지(remainder)'이라 부른다.
$$a=bq+r\;\;\;\;\; (0\leq r < b)$$ 이 관계를 나눗셈 과정으로 생각하면, $a$ 는 나누어지는 수이니 '피젯수'이고, $b$ 는 나누는 수이니 '젯수'라 한다.^[각주:1]

 

증명) 존재성과 유일성을 각각 순서대로 증명해보자.

i) 존재성 : $T=\left\{ a,a-b,a-2b,\cdots \right\}$ 이라 가정하자. $S$를 $T$에 속한 음이 아닌 정수의 집합 $S=\left\{ a-mb\mid m\in \mathbb{Z}\;\;,\;\;a-mb\ge0 \right\}$ 라 정의한다. 여기서 $a-mb\ge 0$ 을 만족하는 정수 $m$ 중 $m=-\left| a \right|$ 를 택하자. 그러면

$$a-mb=a+\left| a \right|b\ge 0 \;\;\;(\because\; b\ge1)$$
이 되고, 이는

$$a+\left| a \right|= \left\{ \begin{array}{cl}
2a &  \ (a \geq 0) \\
0 &  \ (a < 0)
\end{array} \right.$$
이기 때문이다.

만일 $a-mb=a+\left| a \right|b=0 \in S$ 이면 $0$ 은 $S$ 의 최소원소가 된다. 만일 $a-mb=a+\left| a \right|b\neq 0$ 이더라도 $S$ 는 적어도 하나의 원소를 가지기 때문에, 공집합이 아니다. 고로 자연수의 정렬성(Well-Ordering Principle)에 의하여 공집합이 아닌 자연수의 부분집합은 최소 원소를 가지고, 이를 $r$ 이라 가정하자. 그러면

$$r=a-mb=a-qb\ge 0$$
인 정수 $r$이 존재하고, 이때의 $m$을 특별히 $m=q$ 라 표기한다. 또한 $r$ 의 범위가 $r<b$ 임을 보여야 하는데 만일 $r\ge b$ 라 가정하면 $r-b$ 는 자연수이므로 $r-b\in S$ 이다. 그런데 $r$이 $S$ 의 최소 원소이고 $r>r-b$ 이므로 이는 모순이다. 따라서 $r<b$ 이다.

ii) 유일성
$a=bq'+r'$ 을 만족하는 $q',r'\in\mathbf{Z}$ 가 존재한다고 가정하자. $(0\le r' \le b)$ 이때 $a=bq+r$ 을 만족함을 이미 알고 있으므로 양변을 각각 빼면

$$0=b(q-q')+(r-r')\;\;\Rightarrow \;\; \frac{1}{b}\left( r-r' \right)=q-q'$$
가 된다. $b\ge 1$ 이고 $0\le r \le 1\;\;,\;\;0\le r' \le 1$ 이므로 $0\le r-r' < 1$ 이다. 따라서

$$0\le \frac{1}{b}\left( r-r' \right)<\frac{1}{b} < \frac{b}{b}=1$$
이다. 그러면 자연스럽게 우변에서도

$$0\le q-q' < 1$$ 이다.
그러나 $q-q'\in \mathbb{Z}$ 이므로 $q-q'=0$ 이어야 한다. 따라서 $\displaystyle\frac{1}{b}\left( r-r' \right)$ 이므로 $r=r'$ 이고 $q=q'$ 이다. $_\blacksquare$

 

 

 

[참고문헌]

Introduction to Number Theory - William W. Adams, Larry Joel Goldstein

 

 

 

 

1. 문법적으로 사이시옷 표기를 적지 않는 것이 적절하나 저는 그냥 적겠습니다. 그리고 '제(除)'는 '덜다 제'라는 한자입니다. 나눈다는 것은 결국 쪼개어 줄인다는 의미가 있기 때문에 이러한 표현을 사용한 것으로 보입니다. [본문으로]