テスト結果

除算アルゴリズム

◎ 任意の整数 $a$ と自然数 $b$ $(b>0)$に対して、

$$ a=qb+r ~~~~(0\leqq r<b) $$

となる整数 $q,r$ が一意的に(ただ一組だけ)存在する。

この $a=qb+r \ (0\leqq r<b)$ を除算アルゴリズムの式と呼ぶ。

例えばある２つの実数 $A$ と $B$ があるとして、 $A<B$ のとき、 $A$ 以上 $B$ 未満の区間を $[A,B)$ と表すことにする。

実数をある自然数 $b$ の大きさで等間隔に分けることを考えた場合、この表記法によって実数全体は、

$$ ...,[-3b,-2b),[-2b,-b),[-b,0),[0,b),[b,2b),[2b,3b),... $$

のように分割することができる。これは数直線で表した場合、

このように値 $b$ で分割された数直線が想像できるが、この数直線上で例えば $[-b,0)$ の区間とは、

図のように $-b$ を含み($●$)、$0$を含まない($○$)実数の区間である。これによって、実数の数直線が大きさ $b$ によって区切られた形になる。

より一般化した式で表せば、実数 $x$ の全範囲が、次のような式で表現できる無数の区間に分けられたことになる。

$$ qb\leqq x <(q+1)b $$

ある整数 $a$ は、これらの区間の中のただ一つに属することになる。例えば $a$ が$[2b,3b)$の区間にあるとしたとき、数直線上では次のようなイメージで表され、

$a=2b+r$ であり、$a-2b=r$ である。

特に、$a=2b$ の場合、$r=0$ である。

$a\leqq 3b$ の場合は次の区間 $[3b,4b)$ に $a$ が入る。

こうして、これらの $qb\leqq x <(q+1)b$ で表される区間のただ一つに $a$ は存在するので、

$a-qb=r$ とした時の $0\leqq r<b$ となる $q$ 、$r$ が存在する。

◎ この $q$、$r$ はただ一組に限る。

そのことを背理法で証明する。

仮に $a$ の除算アルゴリズム式の表し方が２通りあったとしよう。

$$ \begin{align} a & = qb+r ~~~~~~ (0\leqq r<b) & \cdots(1) \ a & = q'b+r' ~~~~ (0\leqq r'<b) & \cdots(2) \end{align} $$

$$ a &= qb+r ~~~~~~(0\leqq r<b) &\cdots(1) \ $$

$$ a &= q'b+r' ~~~~(0\leqq r'<b) &\cdots(2) $$

(1)と(2)で $a$ の値は同じなので、

$$a=qb+r=q'b+r'$$

これを変形して、

$$ \begin{align} qb-q'b &= r'-r \ (q-q')b &= r'-r & \cdots(3) \end{align} $$

ここでの $q,q',r, r'$ は各々整数であるから、$q-q', r'-r$ も整数である。仮に $(q-q')=A$ とすれば、$Ab=r'-r$ となり、$(r'-r)$ は $b$ の倍数となるから $b$ で割り切れるはずである。

しかし仮定によって $r$ も $r'$ も $b$ より小さい整数であるから

$$|r'-r|<b$$

$b$ より小さい整数で $b$ で割り切れる数は $0$ しかありえない。よって、$r'-r=0$ であり、$q-q'=0$ である。

これはすなわち $q=q'$、$r=r'$ に他ならず、(1)と(2)は全く同じ式である。よって除算アルゴリズム式 $a=qb+r \ (0\leqq r<b)$ における $q$,$r$ はただ一組に限る。

なお、この証明では $q$ と $q'$、$r$ と $r'$ の大小関係が明示されていないが、式(3)を次のように書いても結果は同じなので問題は無い。

$$ b|q-q'|=|r-r'| $$