나눗셈 정리

나눗셈 정리 (Division Theorem) 은 다음과 같습니다.

임의의 두 양의 정수 $a$, $b$에 대하여 $$ a = bq + r (0 \leq r < b) $$ 인 정수 $q$, $r$이 유일하게 존재한다.
너무 간단하고 당연해보이는 정리이지만 우선 이런 정리부터 증명하고 깔고 가야 다른 정리들을 깔끔하게 증명할 수 있습니다.
나눗셈 정리 증명

Part 1. $q$, $r$이 존재한다.
$a + b > 0$임은 쉽게 알 수 있다. (전제가 $a$, $b$ 모두 양수였으므로)
따라서 다음과 같은 집합 $S = \{ a - nb \mid n \in \mathbb{Z}, \, a - nb \geq 0 \}$은 공집합이 아니다. ($n = -1$일 때 원소 $a + b$가 있음)
$S$는 원소가 존재하고 자연수의 부분집합이므로 자연수의 정렬 원리 에 따라 최소 원소가 존재한다.
$S$의 최소 원소를 $\min(S) = r$이라 하면 어떤 정수 $q$에 대해 $a - bq = r$이라 할 수 있다.
$r$의 크기를 따져야 하는데, $r \geq b$이면 $a - b(q + 1) = r - b \geq 0$에서 $r - b$도 $S$의 원소가 되어서 $r$이 최솟값이라는데에 모순이므로 $r < b$이다.
또, $S$의 정의에 의해 $0 \leq r$이므로, $0 \leq r < 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 < b$, $0 \leq u < b$ 에서 $-b < r - u < b$가 되고, 양 변을 $b$로 나누면 $-1 < \frac{r - u}{b} < 1$이다.
이때, $b(t - q) = r - u$ 에서 $\frac{r - u}{b} = t - q$이다. 따라서 $-1 < t - q < 1$인데, $t$, $q$ 모두 정수이므로 $t - q = p$또한 정수이고, $-1 < p < 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$ 표현은 유일하다.

베주 항등식 등을 증명하는데에 사용됩니다.
모듈러 연산 으로 나타내면 $a \equiv r \pmod{b}$라고 할 수 있습니다.