수학생 Juicy

나눗셈 정리 (Division Algorithm)

$ a $가 양의 정수이고, $ b $가 임의의 정수이며, 다음 식을 만족하는 정수 $ q $와 $r$은 유일하게 존재한다.

$$ b=qa+r  ,  ~~~~0\leq r< a $$

나눗셈 정리를 증명하기 전에 알아야할 기본적인 원리가 존재하는데, 정수론에서 자주 이용되는 아르키메데스의 원리이다.

아르키메데스의 원리를 알았으니, 나눗셈 정리를 증명해보자.

pf) $b\geq 0$이면 아르키메데스의 원리에 의하여 $na>b$를 만족하는 양의 정수 $n$이 존재한다. (예를들어, $n=b+1$) 이제, $q+1$을 $na>b$를 만족하는 최소의 양의정수 $n$이라 하면,

$$(q+1)a>b\geq qa$$

가 성립하고, $r=b-qa$로 잡으면, $b\geq qa$에서 $r=b-qa\geq 0$, 또한 $(q+1)a=qa+a>b$에서 $r=b-qa<a$이다. $b<0$인 경우도 같은 방법으로 보일 수 있다. $q$, $r$의 유일성을 증명하기 위하여

$$b=qa+r=q_{1}a+r_{1}, ~~~~0\leq r, r_{1}<a$$

라 가정하면, $r\leq r_{1}$ 또는 $r_{1}\leq r$이므로 편의상 $r_{1}\leq r$이라 하면

$$0\leq r-r_{1}<a$$

이다. $(q_{1}-q)a=r-r_{1}$이므로 $a\mid r-r_{1}$이고 $r-r_{1}>0$이면 $a\leq r-r_{1}$이 되어 $0\leq r-r_{1}<a$ 에 모순이다. 따라서 $ r-r_{1}=0 $, 즉 $r=r_{1}$이 되며, 또 $(q-q_{1})a=0$에서 $q=q_{1}$을 얻는다.