division algorithm(除法アルゴリズム)

簡単に教えろ
#

ある整数($0, \space 1, \space 2, -7, \space 9998 $とか)を考えると、必ず割ることができる。

割ることができるというのは $$ 10 = 5 \times 2 + 0 \\ 7 = 5 \times 1 + 2 \\ 99 = 100 \times 0 + 99 \\ $$ のような形に必ず表すことができるということ。

しかも $$ ? = □ \times ○ + △ $$ の$○$と$△$は$?$と$□$が決まっていれば必ず一通りに決まる。

上に挙げたように個々の具体的な例は計算をして比較的かんたんに確かめることができるが、困ったことに整数は無数に存在するので、本当にすべての整数に対してある法則が成り立つのか？
といったことを確かめるためには特定の数に依存しない数の性質や数学的帰納法を駆使する。

数学的帰納法の数学的な知識の要求が低い分かりやすそうな記事を探したが見当たらなかった。
ご存知でなく、興味があれば検索しよう。

division algorithm
#

任意の整数$a, \space b \in \Z, \space b > 0$に関して $$ a = bq + r \quad (0 \leqq r < b) $$ を満たす$q,\space r \in \Z$の組が一意に存在する。

証明
#

まず$q, \space r$の存在を証明する。

$$ S=\{ a - bk| \space k \in \Z \land a-bk \geqq 0 \} $$ という集合を考える。

$0 \in S$であれば$a -bk =0 \iff a=bk \iff k=a/b$なので$b$は$a$を割り切る。
よって、$q = a / b, \space r = 0$とすれば$a = bq + r$である。

そのような例としては
$a = 6, \space b=2$のとき$ 6 = 2 \cdot 3 + 0$ などがある。

$0 \notin S$の場合について考える。

このとき$S \neq \empty$なのでまずそのことを示す。

$a=0$の場合は$k=0$のときに$0 \in S$なので場合分けを考える必要はない。

$a > 0$の場合、例えば$a - b \cdot 0 \in S$である。
$a < 0$の場合、$a - b(2a)$を考えると、$ a- b(2a)=a(1-2b) \in S$である。

$a-b(2a)$であって、$a-ba$を考えないのは、後者の場合$b=1$のときに$ a- ba = a-a = 0 \implies 0 \in S$となってしまうため。

したがって、$S \neq \empty$である。

よって、🔗整列原理(Well-Ordering Principle)より$S$は最小元をもつ。

$S$の最小元を$r= a - bq$とすると、変形して $$ a = bq + r $$ とすることができ、$r \geqq 0 \space \because r \in S$である。

$r < b$であることを背理法で示す。
$r > b$と仮定する。

$a - b(q+1)$を考えると、 $$ a - b(q+1)= a- bq -b = r -b > 0 \space \because r > b \iff r - b > 0 $$ である。

よって、$a - b(q+1) \in S$となるが、これは$r = a-bq$が$S$の最小元であることに反する。

よって、$r \leqq b$であるが、$a - b(q+1) = r-b \leqq 0 \space \because r \leqq b$に着目すると、$0 \notin S$なので$r \neq b$である。

したがって$r < b$である。
以上で$q, \space r$の存在は証明された。

次に$q, \space r$の組の一意性を示す。

$a, \space b$に対して $$ a = bq + r \quad (0 \leqq r < b) $$

$$ a = bq^{\prime} + r^{\prime} \quad (0 \leqq r^{\prime} < b) $$ が成り立つとする。

$r \leqq r^{\prime}$と仮定する($r > r^{\prime}$の場合は入れ替えて議論すれば良い)と、両式より $$ bq+r = bq^{\prime} + r^{\prime} \\ bq - bq^{\prime} = r^{\prime} -r \\ b(q-q^{\prime}) = r^{\prime} -r $$ となるが、これは$b$が$r^{\prime} -r$を割り切ることを意味している。

ここで仮定より、$0 \leqq r^{\prime} -r \leqq r^{\prime} < b $である。

状況を整理すると、割られる数$r^{\prime} -r$が割る数$b$より小さいということだが、これがなりたつのは$r^{\prime} - r =0$のときのみである。¹

よって、$r^{\prime}=r$と一意性が示される。