Division Algorithm

Division Algorithm

Theorem 1. (Division Algorithm) Let $a, b \in \mathbb{Z}$, with $b \neq 0$. Then $! \exists q, r \in \mathbb{Z}$ such that $a = qb + r (0 \leq r <|b|)$.

임의의 정수를 나누었을 때 그 표현의 유일성을 보장해주는 정리이다. 또한 나머지의 범위가 제한되어있는데, 정수라는 점을 고려할 때 임의의 모든 정수는 나머지가 $0, 1, ..., |b|-1$인 경우들로 각각 나눠서 모두 표현할 수 있다. 

Proof. Let $b > 0$, and let $S := \{a - xb \geq 0 \, | \, x \in \mathbb{Z}\}$. Since $b \geq 1$, $0 \leq a + |a| \leq a + |a|b$= $a - (-|a|)b$. Thus $S \neq \emptyset$. 
By Well-Ordering Principle, there is the least element $r \in S$. Then $\exists q \in \mathbb{Z}$ such that $r = a - qb$. Suppose that $r \geq b$. Then $0 \leq r - b = r - (q + 1)b \in S$, but $r - (q+1)b \leq r \bigotimes$. Thus $0 \leq r < b = |b|$. 
Let $b < 0$. Then $\exists q', r \in \mathbb{Z}$ such that $a = q'|b| + r (0 \leq r < |b|)$. Noting that $|b| = -b$, we may take $q = -q'$. Then we have $a = qb + r (0 \leq r < |b|)$.
Assume that $a$ has two representations of the form, say, $a = qb + r = q'b + r'$, where $0 \leq r, r' < |b|$. Then $r - r' = (q' - q)b \Longrightarrow |r - r'| = |q' - q||b|$.
Since $-|b| < r' \leq 0 \leq r < |b|$, $|r - r'| < |b|$. Then $|r - r'| = |q' - q||b| < |b| \Longrightarrow 0 \leq |q' - q| < 1 \Longrightarrow |q' - q| = 0 \Longleftrightarrow q = q' \Longrightarrow r = r'$. Thus the representation of $a$ is unique. $\blacksquare$