정수론, 그 여섯 번째 이야기 | 나눗셈 정리

나눗셈 정리는 아래의 명제를 말한다.

 

주어진 정수 $a, b$에 대하여, $b > 0$ 이면 다음을 만족하는 유일한 정수 $q, r$이 존재한다. $$a = qb + r,\;\;0 \leq r < b$$     이 때 $q$를 몫, $r$을 나머지라고 한다.

 

변수 $q, r$은 각각 quotient 와 remainder의 머리글자이다. 위 정리는 다음과 같이 증명할 수 있다.

 

Proof : 

집합 $S$를 다음과 같이 정의하자. $$S = \left \{ a - xb : x \in \mathbb{Z},\;a-xb \geq 0 \right \}$$

우리는 정수 $b > 0$임을 알고있으므로, $b \geq 1$이고, 이는 $|a|b\geq|a|$ 임을 의미한다.

따라서 $a - (-|a|)b = a + |a|b \geq a + |a| \geq 0 \Rightarrow S \neq \varnothing$

 

그러므로 $S$는 정렬성의 원리에 의해 최소원소 $\mathrm{min}S = r$ 을 가진다.

$S$의 정의에 의해, $$\exists q \in \mathbb{Z}\;s.t\;a-qb=r,\;r\geq 0$$ 이제 $r < b$ 임을 보이자.

 

귀류법을 사용하여, $r \geq b$ 라고 가정하자. 이 때, $$a - \left ( q + 1 \right )b = \left ( a - qb \right ) - b = r - b \geq 0$$ 가 성립하므로, $a - \left ( q + 1 \right ) \in S$ 인데, 이는 $\mathrm{min}S = r$ 임에 모순.

따라서, $r < b$가 성립하고, $a - qb = r$이므로 $a = qb + r,\;\;0\leq r < b$인 정수 $q, r$이 존재한다.

 

이제 $r, q$의 유일성을 보이자. 귀류법을 사용하여 $a$가 서로 다른 두 가지 형태로 표현될 수 있다고 가정하자. $$a = qb + r = q'b + r',\;\;0\leq r, r' < b$$ 그러면 $r'-r=b\left ( q - q' \right )$ 가 된다.

두 부등식 $0 \leq r' < b$와 $-b < -r \geq 0$을 더하면 $-b < r'-r < b$가 성립하므로 $-b < b \left ( q - q' \right ) < b$

따라서 $-1 < q - q' < 1$인데, $q - q' \in \mathbb{Z}$이므로 $q - q' = 0 \Rightarrow q = q'$

또한, $r'-r=b\left ( q-q' \right ) = 0 \Rightarrow r = r'$ 이므로 서로 다른 두 가지 표현방식임에 모순.

따라서 $a = qb + r$인 정수 $q, r$은 존재한다면 유일하다.

 

 

$\therefore$나눗셈 정리는 참이다.

 

나눗셈 정리는 차후 여러가지 정리들을 증명하는 과정에서 주요하게 사용된다.

그 증명과 결과를 기억해둘 필요가 있다.

 

또, 위의 정리로부터 아래와 같은 따름정리를 얻을 수 있다. 

 

$a, b$가 정수이면, $b \neq 0$일 때 아래 식을 만족하는 유일한 정수 $q, r$이 존재한다. $$a = qb + r,\;\;0\leq r<|b|$$

 

Proof : 

$b > 0$인 경우에는 나눗셈정리와 동치이므로, $b < 0$인 경우에서만 보이면 충분하다. 이 때, $|b| > 0$ 이므로, 다음을 만족하는 정수 $q', r'$이 유일하게 존재한다. $$a = q'|b| + r',\;\;0\leq r < |b|$$ 이 때, $b$가 음수일 때 이므로 $|b| = -b$가 성립하고, $q = q', r = r'$이라고 하면 아래의 식이 성립한다. $$a = qb + r,\;\;0\leq r < |b|$$

따라서 위의 따름정리는 성립한다.

 

 

 

이외에도 나머지 $r$이 $v \leq r < u$를 만족할 때, $u - v = |b|$이기만 하면 $$a = qb + r,\;\;v \leq r < u$$ 인 정수 $q, r$이 유일하게 존재하는데, 이에 대한 증명은 독자에게 맡기겠다.