除算アルゴリズム（整商と剰余、絶対最小剰余）

除算アルゴリズム

たとえば $17$ を $3$ で割り算すると
\[17\div 3=5\ 余り\ 2\]
となります。しかし、このような形は一般的な問題を考えるときに扱いにくいので、数論ではこれを
\[17=3\times 5+2\]
という形で記述します。余りを正数に限定した場合は「$17$ を $3$ で割る」という記述方法はこれ以外にありません。今度は $17$ を $-3$ で割ってみます。
\[17=(-3)\times (-5)+2\]
これも余りを正数のみと決めている場合は他の表し方は存在しません。$17$ を $-3$ で割れば「商は $-5$、余りは $2$」と決まります。何を当たり前のことを言っているのかと思われるかもしれませんが、数学ではこういうことも一応証明しておかなくてはならないのです。以上の事実を一般化すると次のような定理が成り立ちます。

【証明】まず $b\gt 0$ である場合を考えます。$b$ の倍数を小さいほうから順に並べていくと
\[\cdots,\:-3b,\:-2b,\:-b,\:0,\:b,\:2b,\:3b,\:\cdots\]
となるので、
\[qb\leq a\lt (q+1)b\]
を満たす整数 $q$ が唯一つ存在します。すなわち
\[0\leq a-bq\lt b\]
が成り立ちます。ここで $r=a-bq$ とおくと
\[a=bq+r\quad (0\leq r\lt b)\]
となります。次に $b\lt 0$ の場合を考えます。$b$ の倍数を小さいほうから順に並べていくと
\[\cdots,\:3b,\:2b,\:b,\:0,\:-b,\:-2b,\:-3b,\:\cdots\]
となるので、
\[qb\leq a\lt (q-1)b\]
を満たす整数 $q$ が唯一つ存在します。すなわち
\[0\leq a-bq\lt -b\]
であり、$r=a-bq$ とおくと
\[a=bq+r\quad (0\leq r\lt -b)\]
となります。$-b=\mid b\:\mid$ なので、
\[a=bq+r\quad (0\leq r\lt\mid b\mid)\]
となって定理A1 が証明されました。

現代整数論の風景 新品価格 ￥2,700から (2019/8/8 06:50時点)

絶対最小剰余

以上の議論は $0\leq r\lt\mid b\:\mid$、すなわち余りを $0$ または正数に限定していましたが、場合によっては「負の余り」を考えたほうが都合の良い場合もあります。たとえば $17/div 3$ を
\[17=3\times 6-1\]
と書けば、余りの絶対値が小さくなるので、ユークリッドの互除法などの計算では効率が良くなります。このような余りを絶対値最小剰余とよび、定理 A1 の $r$ の条件は
\[\mid r\mid\leq\frac{b}{2}\]
と書き直されます。この条件を満たすために、具体的な計算においては、商 $q$ は $a/b$ に近いほうをとるように注意します。$17/div 3$ の場合、$17/3 = 5.666/cdots$ なので、商は $5$ ではなく $6$ を選択して
\[17=3\times 6-1\]
と表すことになります。

除算に関連する記号と定義

数論における除算に関する定義や記号をまとめておきます。

$a=bq+r$ において $r=0$、すなわち $a=bq$ と表せるときに「$a$ は $b$ で割り切れる」といい、$b|a$ という記号で表します。このとき $a$ を $b$ の倍数（multiple）、$b$ を $a$ の約数（divisor）とよびます。また $b,\:q$ を $a$ の因数（factor）とよびます。

$a=bq+r$ において $r\neq 0$ のとき、「$a$ は $b$ で割り切れない」といい、$b\mid \hspace{-.67em}/a$ という記号で表します。$r$ のことを $a$ の剰余（remainder）とよびます。