除算アルゴリズム(整商と剰余、絶対値最小剰余)

 初等整数論講座の初回記事です。

除算アルゴリズム(整商と剰余、絶対値最小剰余)

 たとえば 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 」と決まります。何を当たり前のことを言っているのかと思われるかもしれませんが、数学ではこういうことも一応証明しておかなくてはならないのです。以上の事実を一般化すると次のような定理が成り立ちます。

[定理 A1] $a$ を整数、$b$ を $0$ ではない整数とするとき、
\[a=bq+r,\quad 0\leq r\leq\mid b\mid\]を満たす整数 $q,\:r$ が唯一存在します。

[定理A1 の証明]
 まず $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 が証明されました。

絶対値最小剰余(余りとして負の整数を採用することもあります)

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

 ≫ [初等整数論講座2] 整正数 N の k 進展開

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください