나눗셈 알고리즘

정수론에 쓰이는 나눗셈 알고리즘을 정리해 둔다.

차례가 잘 정해진 성질(Well-Ordering Property)

공집합이 아닌 자연수 집합의 모든 부분집합 $ S\subset \mathbb{N}\;(S\not=\phi)$는 최소 원소를 가진다. 다시 말하면 $\forall b\in S$에 대하여 $a\leq b$인 원소 $a$가 존재한다. 이것은 자연수가 가진 고유한 성질로 증명없이 받아들이는 공리로 생각하자.

수학적 귀납법 원리(Priciple of Mathmatical Induction)

$S\subset \mathbb{N}\;\;(S\not=\phi)$에서

(1) $1 \in S$

(2) $k \in S \Rightarrow k+1\in S$

을 만족하면 $S=\mathbb{N}$이다.

증명$S\not=\mathbb{N}$라고 가정하자.

$\mathbb{N}-S\not = \phi$이므로 최소 원소가 존재한다. 최소 원소를 $m$이라고 하자.

가정 (1)에서 $1 \in S$이므로 $m\not= 1$이다. $m>1$이므로 $m-1\in \mathbb{N}$이다.

$m-1<m$이고 $m$은 $\mathbb{N}-S$의 최소 원소이므로 $m-1 \in S$이다.

가정 (2)에 따라  $m-1 \in S$이면 $m\in S$이므로 모순이다.

$\therefore\;\;S=\mathbb{N}$

가정 (2)를 $\{1,2,\cdots,k\}\subseteq S \Rightarrow k+1\in S$를 바꾸면 강한 수학적 귀납법이다.

정리 1-1 아르키메데스 성질(Archimedean property)

$\forall a,b \in \mathbb{N}$에 대하여 $na \geq b$인 양의 정수 $n$이 존재한다.

증명 명제가 거짓이라고 가정하자. 즉, 모든 자연수 $n$에 대하여 $na\leq b$인 어떤 자연수 $a,b$가 있다고 하자.

이제 아래와 같은 집합을 생각하자.

$$S=\{b-na|n\in \mathbb{N}\}$$

$S$는 모두 자연수로 이루어져 있으므로 최소 원소가 존재한다.

그 원소가 $b-ma$라고 하자.

$b-(m+1)a \in S$이다. 그런데 $b-(m+1)a=b-ma-a<b-ma$이므로 모순이다.

따라서 아르키메데스 성질은 참이다.

정리 1-2 나눗셈 알고리즘 (Division Algorithm)

두 정수 $a,b\;\;(b>0)$가 주어지면 아래를 만족하는 정수 $q$와 $r$이 유일하게 존재한다.

$$a=qb+r \quad 0 \leq r<b$$

$a$를 $b$로 나누었을 때, $q$를 몫(quotient) $r$은 나머지(remainder)로 부른다.

증명 아래와 같은 집합을 생각하자.

$$S=\{a-xb|x\in \mathbb{Z} ;a-xb\geq 0\}$$

$b\geq 1$이므로 $|a|b\geq|a|$이다.

$$a-(-|a|)b=a+|a|b\geq a+|a| \geq0$$

$x=-|a|$로 생각한다면 $a-xb \in S$이므로 $S\not= \phi$이다.

이제 $S$의 최소 원소를 $r=a-qb$라고 하자. $0 \leq r$은 당연하므로 $r<b$임을 보이면 된다.

만약 $r\geq b$라고 하면

$$a-(q+1)b=(a-qb)-b=r-b \geq 0$$

이므로 $r-b \in S$이다. 이것은 $r$이 최소 원소라는 가정에 모순이다.

따라서, $q,r$이 존재한다. 이제 유일하게 존재함을 증명하기 위해 아래와 같이 다른 표현이 있다고 가정하자.

$$a=qb+r=q^{\prime}b+r^{\prime}$$

$$r^{\prime}-r=b(q-q^{\prime})$$

$$|r^{\prime}-r|=b|q-q^{\prime}|$$

$0 \leq r, r^{\prime} <b$이므로 $0 \leq|r^{\prime}-r|<b$이다.

따라서, $0 \leq |q-q^{\prime}|<1$이므로 $|q-q^{\prime}|=0$이다.

$\therefore\;\;q=q^{\prime},\;\;r=r^{\prime}$

 

따름정리

두 정수 $a,b$가 주어지면 아래를 만족하는 정수 $q$와 $r$이 유일하게 존재한다.

$$a=qb+r \quad 0 \leq r<|b|$$

정수를 정수로 나눌 때, 언제나 몫과 나머지는 유일하게 존재한다.