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

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

 

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

 

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

 

Proof : 

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

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

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

 

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

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

 

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

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

 

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

두 부등식 $0\le r^{\prime }<b$와 $-b<-r\ge 0$을 더하면 $-b<r^{\prime }-r<b$가 성립하므로 $-b<b(q-q^{\prime })<b$

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

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

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

 

 

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

 

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

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

 

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

 

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

 

Proof : 

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

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

 

 

 

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