나눗셈 정리 (Division Theorem) 은 다음과 같습니다.
임의의 두 양의 정수 $a$, $b$에 대하여 $$ a = bq + r (0 \leq r \le b) $$ 인 정수 $q$, $r$이 유일하게 존재한다.너무 간단하고 당연해보이는 정리이지만 우선 이런 정리부터 증명하고 깔고 가야 다른 정리들을 깔끔하게 증명할 수 있습니다.
Part 1. $q$, $r$이 존재한다.
먼저, $S$의 원소로 $a + b$가 존재하므로 $S$는 공집합이 아니다.
$a + b > 0$임은 쉽게 알 수 있다. (전제가 $a$, $b$ 모두 양수였으므로)
따라서 다음과 같은 집합 $S = \{ a - nb \mid n \in \mathbb{Z}, \, a - nb \geq 0 \}$은 공집합이 아니다. ($n = -1$일 때 원소가 있음)
$S$에는 최소 원소가 존재함을 보이기
만약 $0 \not\in S$이면 $S = \{ a - nb \mid n \in \mathbb{Z}, \, a - nb \geq 0 \} = \{ a - nb \mid n \in \mathbb{Z}, \, a - nb > 0 \}$이므로, $S$가 자연수 집합 $\mathbb{N}$의 공집합이 아닌 부분집합이다.
따라서 자연수의 정렬 원리 에 따라 최소 원소가 존재한다.
$0 \in S$ 인 경우에는 집합 $S$에 $0$보다 작은 원소가 있을 수 없으므로 $S$의 최소 원소는 $0$으로 존재한다.
(자연수 집합 $\mathbb{N}$에 $0$이 포함된 상태로 자연수의 정렬 원리를 증명한 경우에는 그냥 $S$가 자연수 집합 $\mathbb{N}$의 공집합이 아닌 부분집합이므로 자연수의 정렬 원리에 의해 최소 원소를 가진다고 할 수 있다.)
$r$의 크기를 따져야 하는데, $r \geq b$이면 $a - b(q + 1) = r - b \leq 0$에서 $r - b$도 $S$의 원소가 되어서 $r$이 최솟값이라는데에 모순이므로 $r \le b$이다.
또, $S$의 정의에 의해 $0 \leq r$이므로, $0 \leq r \le b$이다.
Part 2. $q$, $r$이 유일하게 존재한다.
어떤 두 정수 $t$, $u$에 대해 $a = bt + u$라 하자.
$a = bt + u = bq + r$에서 $b(t - q) = r - u$가 된다.
$r \not= u$라면 $0 \leq r \le b$, $0 \leq u \le b$ 에서 $-b \le r - u \le b$가 되고, 양 변을 $b$로 나누면 $-1 \le \frac{r - u}{b} \le 1$이다.
이때, $b(t - q) = r - u$ 에서 $\frac{r - u}{b} = t - q$이다. 따라서 $-1 \le t - q \le 1$인데, $t$, $q$ 모두 정수이므로 $t - q = p$또한 정수이고, $-1 \le p \le 1$인 정수 $p$는 $0$ 뿐이다. 따라서 $t - q = 0$ 이다.
다시 $b(t - q) = r - u$에서 $t - q = 0$이므로, $0 = r - u$에서 $r = u$인데, 이는 $r \not= u$에 모순이다. 따라서 전제조건인 $r \not= u$이 틀렸고, $r = u$이다.
$b(t - q) = r - u$에서 $r = u$이므로, $r - u = 0$에서 $b(t - q) = 0$이다. $b$는 양수이므로 $t - q = 0$이어야 한다. 따라서 $t = q$이다.
$a = bt + u$라 하면 $t = q$, $u = r$이므로, $a = bq + r$ 표현은 유일하다.