9.2 最大公約数

整数 \(a\), \(b\) の公約数 (common divisor) とは、\(a\) と \(b\) の両方を割り切る整数を意味する。整数 \(a\), \(b\) の最大公約数 (greatest common divisor) を \(\operatorname{gcd}(a, b)\) と表記する。例えば \(\operatorname{gcd}(18, 24) = 6\) が成り立つ。

\(a\) と \(b\) が両方 \(0\) である場合を除けば、\(a\) と \(b\) の最大公約数は必ず存在する。最大公約数は \(a\) と \(b\) の関係や整数一般の性質を考える上で非常に重要であり、本章でも頻繁に利用される。

\(n \neq 0\) に対する次の事実は最大公約数の定義から直ちに分かる:

最後の等式は任意の整数が \(0\) の約数である事実から従う。

9.2.1 Euclid のアルゴリズム

最初に最大公約数を計算する方法を考えよう。Euclidユークリッド のアルゴリズム (Euclidean algorithm) は数千年前から知られている手続きであり、次の初等的な観察を利用する:

証明 除算定理 (定理 9.1.4) より、次の等式を満たす整数 \(q\), \(r\) が存在する:

ここで \(r = \operatorname{rem}(a, b)\) である。言い換えれば \(a\) は \(b\) と \(r\) の線形結合だから、補題 9.1.2 の \(2.\) より \(b\) と \(r\) の公約数は \(a\) の約数でもある。同様に \(r\) は \(a\) と \(b\) の線形結合 \(a - qb\) に等しいので、\(a\) と \(b\) の公約数は \(r\) の約数でもある。これは \(a\) と \(b\) の公約数が \(b\) と \(r\) の公約数に一致することを意味する¹。よって最大公約数も一致する。 ■

補題 9.2.1 を繰り返し使うと、二つの整数の最大公約数を簡単に計算できる。例えば、\(1147\) と \(899\) の最大公約数は次のように計算できる:

この計算から \(\operatorname{gcd}(1147, 899) = 31\) を得る。この事実は \(1147\) ガロンと \(899\) ガロンの容器で \(32\) ガロンを作れないことの証明で利用した。

一方で、Euclid のアルゴリズムを \(26\) と \(21\) に適用すると次の等式を得る:

先述したように、ここからは \(26\) ガロンと \(21\) ガロンの容器で \(3\) ガロンを作れるかどうかは分からない。しかし実は、最大公約数が \(1\) である事実は容器の容量以下の任意の量の水を容器に入れられることを意味する。その理由を説明するには、数論をもう少し学ぶ必要がある。

状態機械としての Euclid のアルゴリズム

Euclid のアルゴリズムは状態機械として簡単に形式化できる。状態集合は \(\mathbb{N}^{2}\) であり、任意の \(x\) と \(y > 0\) について次の遷移が定義される:

補題 9.2.1 より、遷移前後で最大公約数は変化しない。つまり述語

は状態 \((x, y)\) に関する保存不変条件である。この保存不変条件は初期状態 \((a, b)\) でもちろん成り立つ。よって不変条件の原理より到達可能な全ての状態で成り立つ。よって \(y\) が \(0\) になることがあれば、それは次の等式を意味する:

つまり、そのときの \(x\) が \(a\) と \(b\) の最大公約数である。

さらに、\(x\) と \(y\) は非常に速く \(0\) になると示せる。実際、状態 \((x, y)\) から \(2\) 回遷移すると第 \(1\) 要素が \(\operatorname{rem}(x, y)\) の状態となり、\(\operatorname{rem}(x, y)\) の値は \(x\) の半分以下である²。 つまり \(x\) は最初 \(a\) で \(2\) 回の遷移ごとに半分以下になるので、最大 \(2 \log a\) 回の遷移で最小値 ── \(\operatorname{gcd}(a, b)\) ── に達する。その後アルゴリズムは最大で \(1\) 回の遷移で停止する。まとめると、Euclid のアルゴリズムは最大で \(1 + 2 \log a\) 回だけ遷移して停止する³。

9.2.2 粉砕法

次の重要な定理からは実に様々な結果が得られる:

補題 9.1.2 からは、\(a\) と \(b\) の全ての線形結合は \(a\) と \(b\) の任意の公約数 (最大公約数を当然含む) で割り切れると分かる。線形結合の定数倍も線形結合だから、定理 9.2.2 より最大公約数の整数倍が線形結合だと分かる。つまり:

定理 9.2.2 の証明の概要を示す。これから具体的に \(s\) と \(t\) を求める。そのために、六世紀のインドに起源を持つ数学的ツールを利用する。これは当時の言葉で Kuṭṭakaクッタカ と呼ばれた。この単語は「粉々に砕く」を意味する。現在、この「粉砕法 (pulverizer)」は拡張 Euclidユークリッド のアルゴリズム (extended Euclidean algorithm) と呼ばれる。上述の Euclid のアルゴリズムに非常に近いからである。

例えば、\(259\) と \(70\) の最大公約数は Euclid のアルゴリズムで次のように計算できる:

粉砕法も同じステップを踏む。ただし、記録される情報が増える: \(\operatorname{gcd}(a, b)\) を計算する中で、途中で計算される剰余 (上記の例では \(49\), \(21\), \(7\)) が \(a\) と \(b\) の線形結合として記憶される。そうしておけば、最後に残る \(0\) でない剰余 (最大公約数) を \(a\) と \(b\) の線形結合で表せる。実際に実行した例を次に示す:

粉砕法のアルゴリズムは最初 \(x = a\), \(y = b\) とした状態から始まる。上図の最初の三列は通常の Euclid のアルゴリズムの実行を表す。最後の列では、各ステップにおける \(\operatorname{rem}(x, y) = x - \operatorname{qcnt}(x, y) \cdot y\) の値が \(a\) と \(b\) の線形結合の形で計算される。この計算をしておくと、最終的に計算される \(\operatorname{gcd}(a, b)\) が \(a\) と \(b\) の線形結合の形で得られる (上図の枠で囲んだ部分)。

粉砕法の動作と正しい理由はこれで理解できたと思う。まだ疑問に思っているなら、このアルゴリズムを状態機械として形式化して Euclid のアルゴリズムに対して示した不変条件を拡張することで正しさを検証する問題 9.13 を解くとよい。

粉砕法は Euclid のアルゴリズムに少量の計算を追加しただけなので、このアルゴリズムを使えば非常に大きな整数を高速に「粉砕」できる。本章の後半で見るように、粉砕法は高速に実行できるために暗号理論の分野で非常に有用なツールとなる。

容器に水を入れる問題に関する補題 9.1.6 は最大公約数を使って言い換えられる:

9.2.3 容器に水を入れる問題に対する完全な解答

系 9.2.3 からは、\(3\) が \(21\) と \(26\) の線形結合で書けると分かる: \(3\) が \(\operatorname{gcd}(21, 26) = 1\) の倍数だからである。粉砕法を使えば、次の等式を満たす整数 \(s\), \(t\) を求められる:

ここで係数 \(s\) の正負は求めてみるまで分からない。しかし、等式 \(\text{(9.5)}\) の \(s\), \(t\) を使えば係数 \(s^{\prime}\) が正である次の形をした線形結合を計算できる:

\(s^{\prime}\), \(t^{\prime}\) を計算するには、次の観察を利用する: \(s\) を \(21\) だけ大きくして \(t\) を \(26\) だけ小さくしても、値 \(s \cdot 21 + t \cdot 26\) は変化しない。よってこの操作を繰り返せば、係数 \(s^{\prime}\) が正であるような線形結合がいずれ得られる (もちろん、このとき \(t^{\prime}\) は負になる: そうでなければ式の値は \(3\) よりずっと大きくなってしまう)。

この結果を使うと、\(21\) ガロンと \(26\) ガロンの容器を使って \(3\) ガロンを作るアルゴリズムが得られる: 次のステップを \(s^{\prime}\) 回だけ繰り返せばよい:

1. \(21\) ガロンの容器を満杯にする。

2. \(21\) ガロンの容器に入っている水を \(26\) ガロンの容器に移す。もし \(26\) ガロンの容器が途中で満杯になったら、それを空にしてから \(21\) ガロンの容器に残っている水を \(26\) ガロンの容器に注ぎ切る。

この処理が終わるまでに、\(26\) ガロンの容器を空にする操作は \(-t^{\prime}\) 回だけ実行される。理由は次の通りである: 処理が終了するまでに外部から汲み入れた水の総量は \(s^{\prime} \cdot 21\) ガロンなので、\(26\) ガロンの容器を空にする回数が \(-t^{\prime}\) 未満だと等式 \(\text{(9.6)}\) より容器に \(3 + 26\) ガロン以上の水が処理終了時に残るものの、これは容器の容量 \(26\) ガロンを超えている。また、空にする回数が \(-t^{\prime}\) より多いと、処理終了時に容器に \(3 - 26\) 以下の水が残ることになるものの、これは不可能である。よって \(26\) ガロンの容器を空にする操作の実行回数は \(-t^{\prime}\) であり、このとき等式 \(\text{(9.6)}\) から \(26\) ガロンの容器には \(3\) ガロンだけ水が入っていると分かる。

驚くべきことに、このアルゴリズムを使うとき係数 \(s^{\prime}\) と \(t^{\prime}\) を事前に知っておく必要はない！ ループの本体を \(s^{\prime}\) 回だけ繰り返すのではなく、\(3\) ガロンが残った容器が得られるまで繰り返すだけで構わない: そうした場合でも操作は必ず終了する。もちろん、二つの容器に入っている水の量を追跡する必要はある。二つの容器が空の状態 \((0, 0)\) から始めて、このアルゴリズムを使って \(3\) ガロンを得るまでの完全な遷移を次に示す:

同じアルゴリズムは容器の容量、そして目標としている水の量に関わらず動作する！ つまり、次の操作を目標の水の量が得られるまで繰り返せばよい:

1. 小さい方の容器を満杯にする。

2. 小さい方の容器に入っている水を大きい方の容器に移す。もし大きい方の容器が途中で満杯になったら、それを空にしてから小さい方の容器に残っている水を大きい方の容器に注ぎ切る。

具体的な容量を考えたときと同じ議論を使えば、このアルゴリズムによって二つの容器の容量の最大公約数の整数倍が ── 容器の容量を超えない範囲で ── 大きい方の容器に入った状態を実現でき、それらが実現可能な水の量の全てだと分かる。賢くなる必要は全くない！

以上で、この「容器に水を入れる問題」に対する完全な解答が得られた:

9.2.4 最大公約数の性質

最大公約数に関する基本的な事実をまとめておく:

二整数の最大公約数がそれらの線形結合である事実を使って補題 9.2.6 を証明するのは良い練習問題だろう (問題 9.11)。

補題 9.2.6 は整数の素因数分解が一意である事実 (定理 9.4.1) からも簡単に示せる。ただ、これらの性質は第 9.4 節で素因数分解の一意性を示すときに使われるので、循環論法を避けるには別の方法で証明する必要がある。