나눗셈 정리와 그 증명법 알아보기

목, 나머지, 배수, 약수 알아보기

$q$, $r$을 각각 $b$를 $a$로 나눈 몫과 나머지라 한다. 두 정수 $a$, $b$에 대해서 $a$가 $b$를 나눈다는 것은 $b=ac$를 만족시키는 $c$가 존재할때이다. 기호로 $a|b$ 라 나타낸다. 이때 $b$를 $ a$의 배수, $a$를 $b$의 약수라 한다.

 

나눗셈 정리란?

임의로 주어진 양의 정수 $a$와 정수 $b$에 대해서 $b=aq+r$ ($0 \leq r < a$)를 만족시키는 정수 $q, r$이 유일하게 존재한다.

 

증명방법

(1) 존재성 증명

집합 $S= \{ b-na | n \in Z, b-na \geq 0 \}$ 는 공집합이 아니고 $S \subset N \cup \{ 0 \}$이므로 집합 $S$에는 최소 원소가 존재한다. (정렬성의 원리)

 

최소원소를 $r$이라 하면 $r \in S $이므로 적당한 정수 $q$에 대해서 $r=b-aq$의 꼴로 표시된다. 따라서 $b=aq+r$이고 $r \geq 0$을 만족한다.

 

이제 $r \geq a$라 가정하면 $b-(q+1)a = r-a \geq 0$이므로 $b-(q+1)a \in S$이다. 하지만 $b-(q+1)a < r$이므로 $r$이 $S$의 최소 원소임에 모순이다. 따라서 $r<a$ 를 만족한다.

 

(2) 유일성 증명

$q, r$가 유일함을 보이자.

정수 $q_1$과 $r_1$이 $b=q_1a + r_1$ ($0 \leq r_1 <a$)를 만족시킨다 하자. 이때 $aq_1 +r_1 = aq+r$로 부터 $a(q_1-q)=r-r_1$이다. 만약 $q_1 \neq q$라 하면 $|a| \leq |q_1-q| \cdot |a| = |a(q_1-q)| = |r-r_1|<|a|$ 가 되어 모순이다. 따라서 $q_1 = q$, $r_1 = r$이다. 따라서 $q$, $r$은 유일하게 존재한다.