除法アルゴリズム

本講では、整数に対して一意な分解 b=qa+r（0\le r<|a| を満たす）を形式化する原理として、除法アルゴリズムを展開する。まず商と余りの存在を証明し、次にその一意性を示す。最後に、余りの意味を解釈し、理論を計算手続きとしての筆算による除法アルゴリズムと結び付け、さらに合同算術および計算機応用との自然な関連を予告する。

学習目標

本講を修了すると、学生は次のことができるようになる。

1. 識別する：整数除法における基本的概念および役割（被除数、除数、商、余り）と、厳密な場合としての可除性の概念。
2. 説明する：ユークリッド除法のアルゴリズム／定理の命題、余りを規定する条件（0\le r<|a|）および曖昧さを避けるためのその目的。
3. 適用する：具体例において、ユークリッド分解 b=qa+r を用いて q と r を決定し、余りの上界を確認する。
4. 分析する：被除数および除数の符号に応じた場合分けの扱いを検討し、ユークリッドの規約が余りを非負に保つ理由を正当化する。
5. 実行する：位取り表現に基づく機械的手続きとしての筆算による除法アルゴリズムを実行し、 q と r を得る。

内容索引:
除法と可除性
ユークリッド除法の定理
ユークリッド除法の証明
商と余りの解釈
筆算による除法アルゴリズム
結論
演習問題（例題・解答付き）

除法と可除性

算術において、可除性は「厳密な」場合を表す。すなわち、a\mid b は、b が a の倍数として正確に表されることを意味する。しかし、任意の二つの整数の間に常に可除性が成り立つわけではない。それでもなお、「ある数が別の数に何回含まれるか、そして正確に含まれない場合に何が残るのか」を問うことはできる。この文脈において除法アルゴリズムが現れ、任意の整数 b が a の倍数と「余り」の和として表されることを保証する。

例として、a=3 および b=16 を考える。3 は 16 を割り切らないことは明らかである。しかし、除法の操作に対して商と余りを見つけることは可能であり、実際

16 = 5\cdot 3 + 1

したがって、b=16 を a=3 で割ると（ここで b は被除数、a は除数である）、16/3 または 16\div 3 と表され、商として q=5、余りとして r=1 が得られる。一般に、除法アルゴリズムは、a\neq 0 を満たす任意の整数 a（除数）および b（被除数）に対して、次を満たす一意な整数 q と r が存在することを主張する。

b=qa+r,\qquad 0\le r<|a|

この例では 16=3\cdot 5+1 であり、条件 0\le r<|a| は 0\le 1<3 であるため満たされている。この定式化は、除数（または被除数）が負であり得る場合の曖昧さを避け、余りが常に非負であり、かつ除数の絶対値より厳密に小さいことを保証する。

ユークリッド除法の定理

除法アルゴリズムを適用した結果は、ユークリッド除法と呼ばれ、次の結果に基づいている。

定理： a,b\in\mathbb{Z} を a\neq 0 とする。このとき、次を満たす一意な q,r\in\mathbb{Z} が存在する。

b=qa+r,\qquad 0\le r<|a|.

整数 q を商、r を b を a で割ったときの余りと呼ぶ。

ユークリッド除法の証明

この証明は二つの部分に分かれる。まず商と余りが存在することを示し、次に、それらが存在するとして一意であることを示す。

存在

a,b\in\mathbb{Z} を a\neq 0 とし、d=|a| と定義する。このとき d>0 である。まず b\ge 0 の場合を証明する。すなわち、b=dq+r かつ 0\le r<d を満たす q,r\in\mathbb{Z} が存在することを示す。次に b<0 の場合を扱う。最後に、d を |a| に置き換えることで、0\le r<|a| を満たす形 b=qa+r を得る。

b\in\mathbb{Z} かつ b\ge 0 とする。このとき命題 P(b) を次のように定める。「b=dq+r かつ 0\le r<d を満たす q,r\in\mathbb{Z} が存在する」。P(b) がすべての b\ge 0 に対して成り立つことを、数学的帰納法によって示す。

基底の場合： b=0 のとき、q=0 および r=0 と取れば、0=d\cdot 0+0 かつ 0\le 0<d が得られる。したがって P(0) は真である。

帰納段階： k\ge 0 とし、P(k) が真であると仮定する。このとき、次を満たす q,r\in\mathbb{Z} が存在する。

k=dq+r,\qquad 0\le r<d.

両辺に 1 を加えると

k+1=dq+(r+1).

さらに 0\le r<d から r+1\le d が従う。したがって、r+1<d または r+1=d のいずれかの場合のみが起こり得る。

場合1： r+1<d のとき、q'=q および r'=r+1 と定める。このとき

k+1=dq'+r',\qquad 0\le r'<d.

場合2： r+1=d のとき、k+1=dq+d=d(q+1)+0 となる。q'=q+1 および r'=0 と定めれば、

k+1=dq'+r',\qquad 0\le r'<d.

いずれの場合においても、k+1=dq'+r' かつ 0\le r'<d を満たす整数 q',r' を構成できた。したがって P(k+1) は真である。以上より、帰納法によって P(b) はすべての b\ge 0 に対して成り立つ。

次に b<0 の場合を考える。このとき -b>0 である。前の結果を -b に適用すると、次を満たす q,r\in\mathbb{Z} が存在する。

-b=dq+r,\qquad 0\le r<d.

両辺に -1 を掛けると

b=-dq-r.

r=0 の場合、q_1=-q および r_1=0 と取れば、b=dq_1+r_1 かつ 0\le r_1<d が成り立つ。

r>0 の場合、q_1=-q-1 および r_1=d-r と定める。0<r<d であるから、0<d-r<d、すなわち 0\le r_1<d が成り立つ。さらに、

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

したがって、すべての b\in\mathbb{Z} に対して、b=dq_1+r_1 かつ 0\le r_1<d を満たす q_1,r_1\in\mathbb{Z} が存在する。

最後に、d=|a| であることを思い出そう。a>0 のとき、d=a であり、等式 b=dq_1+r_1 は b=aq_1+r_1 と書け、0\le r_1<|a| を満たす。

a<0 のとき、d=-a であり、b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1 となる。q=-q_1 および r=r_1 と定義すると、次を得る。

b=qa+r,\qquad 0\le r<|a|.

これにより、a\neq 0 を満たす任意の a,b\in\mathbb{Z} に対して、q および r の存在が示された。

一意性

q,q',r,r'\in\mathbb{Z} が存在して、次が成り立つと仮定する。

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

両式を減ずると、

a(q-q')=r'-r.

0\le r,r'<|a| であるから、|r'-r|<|a| が成り立つ。一方、左辺は a の倍数であり、したがって |a| の倍数でもある。絶対値が |a| より厳密に小さい |a| の整数倍は 0 のみである。実際、m\in\mathbb{Z} で |a| m \neq 0 ならば、\big| |a| m \big| \ge |a| となる。したがって r'-r=0、すなわち r=r' であり、これを b=qa+r に代入すると q=q' が従う。ゆえに、この分解は一意である。

商と余りの解釈

• 「余り」とは何か。 b=qa+r のとき、r=b-qa は b から倍数 qa を取り除いたときに「残る」ものである。言い換えれば、r は a の倍数の格子に b を合わせたときの剰余である。
• なぜ 0\le r<|a| を要求するのか。 この条件がなければ、組 (q,r) は一意ではない。実際、b=qa+r ならば、b=a(q+1)+(r-a) も成り立つ。条件 0\le r<|a| は、余りを固定された区間 \{0,1,2,\dots,|a|-1\} に制限し、同じ数に対する無限個の「再ラベル付け」を防ぐ。
• a が負の場合はどうなるか。 定理は変更なく成り立ち、余りは非負で |a| によって上から抑えられる。これは、いくつかのプログラミング言語がゼロ方向への切り捨てを用い、負の余りを生成する場合があるのに対し、数学では余りを「標準的」な代表とするために 0\le r<|a| の規約を採用する点で重要である。

  さらに、a>0 のとき、商は床関数に一致する。

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

筆算による除法アルゴリズム

ユークリッド除法に基づいて、数の位取り表現を利用することで、筆算による除法アルゴリズムを実装することができる。このアルゴリズムは、a,b\in\mathbb{Z} かつ a\neq 0 のもとで b\div a を計算したいときに、q と r の値を迅速に求めることを可能にする計算技法である。

これを説明するために、まずアルゴリズムの実行過程および起こり得る状況を示すいくつかの例を確認しよう。

1. 57\div 4 を計算したいと仮定する。ここで 57 は被除数、4 は除数である。これを行うために、次の計算手順を実行する。

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{除法の演算を書く。} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{被除数の左から、除数以上となる最初の接頭部分を}\\ &\text{分離する。この場合は 5 である。} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{$4$ を掛けて $5$ 以下となる最大の数を考え、}\\ &\text{それを等号の右に書く。これは 1 である。} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{結果を除数で掛け、選択した値から引く。} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{次の桁を選択して「下ろす」。} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{得られた最後の数で同じ手順を繰り返す。} \end{array}

   「下ろす」桁が尽きた時点でアルゴリズムは終了し、結果として商 q=14、余り r=1 が得られる。特に、余りは常に除数より小さくなる。

2. 132\div 5 を計算したいと仮定する。この場合、次の計算手順を実行する。

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{被除数の最初の接頭部分を分離し、}\\ & \text{5 を掛けてそれ以下となる自然数を探す。}\\ & \text{できない場合は、可能になるまで次の桁を加える。} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{前の段階が成立したら、通常どおりアルゴリズムを実行する。} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. 被除数の桁数が多い場合も、手順は同様に実行される。例えば、3521\div 12 を計算すると、次が得られる。

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. いずれかの数が負である場合、結果の表し方には二つの許容される形式が存在する。ただし、数論における標準的な形式は、余りが正であり、ユークリッド除法と整合的なものである。例えば、-598\div 21 を計算すると、次の二つの展開が得られ、いずれも恒等式として正しい。

   • 負の余りを用いる場合： これは、計算の初めに符号を除き、最後にそれを戻すことで得られる。

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     ここから次が得られる。

     598 = 21 \times 28 + 10

     次に、この等式全体を -1 倍すると、

     -598 = 21 \times (-28) - 10

     したがって、この表現では -598\div 21 の結果は、商 q=-28、余り r=-10 となる。

     さらに、等式全体を再び -1 倍すると、

     598 = (-21)\times(-28) + 10

     したがって、598\div (-21) の結果は、商 q=-28、余り r=10 である。

   • 正の余りを用い、ユークリッド除法と整合的な場合： 前の展開から次が得られる。

     -598 = 21 \times (-28) - 10

     次に、この等式の右辺に 0=21-21 を加えると、

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     したがって、ユークリッド除法と整合的に考えると、-598\div 21 の結果は、商 q=-29、余り r=11 となる。

   ユークリッド除法における慣習に関しては、正の余りをもつ結果のみがユークリッド的な商と余りに対応する。しかし、いずれの表現も正しい恒等式であり、異なる文脈では有用となり得る。筆算による除法アルゴリズムは負の余りを生じることがあるが、これは機械的に結果を得たり、追加の手順なしに代数的操作を行ったりするうえで実用的である。一方、ユークリッド除法と整合的な正の余りをもつ結果は、各剰余類の標準的（カノニカル）な代表（例えば \{0,1,\dots,n-1\}）を定めることを可能にし、整数を正確かつ曖昧さなくラベル付けすることを容易にする。なお、対称剰余など、規則を固定すれば同様に有効な他の代表の取り方も存在する。

結論

除法アルゴリズムは、任意の整数除法が一意に b=qa+r（0\le r<|a|）の形で表されることを保証し、負の数が関与する場合であっても商と余りを解釈するための標準的な基準を与える。筆算による除法アルゴリズムは、この分解を位取り表現に基づいて実装した実用的手続きに過ぎず、q と r を機械的に計算することを可能にする。最後に、このユークリッド的形式は曖昧さを回避するだけでなく、合同算術とも自然に結び付く。すなわち、余り r は、法 a による b の剰余類の標準的代表として機能し、数論における多くの手法や計算機応用の基盤となる。これらは今後の回で検討される予定である。

提案および解答付き演習

ユークリッド除法

1. （解答済み） 次を満たす q と r を求めよ。

   137 = 9q + r,\qquad 0\le r\lt 9.

   解答： 9 を掛けても 137 を超えない最大の数を探す。15\times 9 = 135 であり、16\times 9 = 144 であるから、求める商は q=15 である。次に余り r=137-9q を計算し、0\le r\lt 9 を確認する。計算すると次を得る。

   r=137-9\cdot 15=137-135=2.

   したがって、137=9\cdot 15+2 かつ 0\le 2\lt 9 である。

2. （解答済み） 次を満たす q と r を求めよ。

   2025 = 37q + r,\qquad 0\le r\lt 37.

   解答： 37 を掛けても 2025 を超えない最大の数を探す。37\times 54 = 1998、37\times 55 = 2035 であるから、求める商は q=54 である。次に余り r=2025-37q を計算し、0\le r\lt 37 を確認する。計算すると次を得る。

   r=2025-37\cdot 54=2025-1998=27.

   したがって、2025=37\cdot 54+27 かつ 0\le 27\lt 37 である。

3. 次を満たす q と r を求めよ。

   745 = 23q + r,\qquad 0\le r\lt 23.

4. 次を満たす q と r を求めよ。

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. 次を満たす q と r を求めよ。

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. 余りを固定した整数の探索。 a=12 とする。

   (a) 12 によるユークリッド除法の余りが r=5 となるすべての整数 b の集合を記述せよ。

   (b) 上記を満たす最小の整数 b\gt 1000 を求め、対応する商 q を決定せよ。

筆算による除法アルゴリズム

各場合について、筆算による除法アルゴリズムを適用し、商 q と余り r を計算せよ。アルゴリズムによって負の余りが得られた場合は、結果をユークリッド除法の形に変換せよ。

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.