## 定義 最大公約数(greatest common divisor, gcd)は、2つの整数 a, b をともに割り切る整数(共通の約数)のうち最大のものを指す。a, b が両方とも 0 でない限り常に存在し、gcd(a, b) と書く。gcd を計算する古典的な方法が互除法(Euclid's Algorithm)で、gcd(a, b) = gcd(b, rem(a, b))(b ≠ 0)という関係を繰り返し適用することで、たかだか 1 + 2 log a 回の適用で計算が終わる。この関係は、a を b で割った商 q と余り r について a = qb + r が成り立つとき、b と r の共通の約数は必ず a の約数でもあり、逆に a と b の共通の約数は必ず r の約数でもある、という事実(除法定理)から従う。互除法をさらに拡張したものが拡張互除法(Pulverizer、6世紀インド起源の kuttak に由来する古い名称を持つ)で、単に gcd(a, b) の値を求めるだけでなく、gcd(a, b) を a, b の整数線形結合 sa + tb として明示的に表す係数 s, t を、互除法の各ステップで得られる余りを a, b の線形結合として逐次書き換える「簿記」によって構成的に求める。この事実(gcd(a, b) が必ず a, b の整数線形結合になり、逆に a, b の整数線形結合として表現できる整数は必ず gcd(a, b) の倍数である)は、水入れ問題(water jug problem、a, b ガロンの容器を使って c ガロンを作れるかという問題)を「c が gcd(a, b) の倍数であるとき、かつそのときに限り実現できる」という形で完全に解くために使われる。さらに、gcd は合同算術における乗法逆元の存在条件(gcd(k, n) = 1 と Zn での k の可逆性が同値)や、算術の基本定理(素因数分解の一意性)の証明の土台にもなる基礎的な道具である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]], ch.8 §8.1〜§8.2) ## 横断的知見 - 第21章(漸化式)は、互除法の反復回数が最大になる入力は連続する2つのフィボナッチ数であると明言しており、第8章の未解決の問いに残っていた「フィボナッチ数と互除法の最悪計算量の関係」に直接答える。第8章はこの改善(log_φ(a)への改善)をProblem 8.14として示唆するにとどめ証明を扱わなかったが、第21章はフィボナッチ数列 f(n) = f(n-1) + f(n-2) 自体を線形漸化式の典型例として特性方程式 x^2 = x + 1 から解いており、その根 (1±√5)/2 の一方である黄金比φが、互除法の最悪計算量の底として自然に現れる理由(フィボナッチ数の増大率そのものがφ^nのオーダーであること)を裏づける。ただし第21章はこの互除法との接続を一文で触れるのみで、log_φ(a)という具体的な上界の証明は依然として与えていない。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] §8.1〜§8.2, [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.3.1) ## 未解決の問い - 互除法の遷移回数の厳密な上界がlog_φ(a)(φは黄金比)に改善できることの証明は、第8章・第21章のいずれにも含まれない。フィボナッチ数の増大率(第21章のBinetの公式 f(n) = φ^(n+1)/√5 + o(1))と互除法の反復回数の関係を厳密に結びつける証明を扱う他ソースがあれば、この点を横断的知見として確認したい。 - gcd の計算には Binary GCD(2 除算と減算のみを使う手法)というハードウェア上でより高速な代替アルゴリズムが Problem 8.16 で紹介されているが、本文の主題ではない。実務上の高速化手法(Binary GCD、拡張二進 GCD 等)を扱うソースがあれば、互除法との性能比較を横断的知見に加えたい。 ## 関連 - [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] — 整除性・互除法・Pulverizer・水入れ問題への応用 - [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] — フィボナッチ数列の閉じた形(Binetの公式)と互除法の最悪計算量の接続 - [[合同算術]] — gcd(k, n) = 1 と Zn における乗法逆元の存在が同値であることの土台 - [[素数]] — 算術の基本定理の証明で gcd と線形結合の性質が使われる - [[公開鍵暗号方式]] — RSA の秘密鍵生成で拡張互除法(Pulverizer)が使われる - [[漸化式]] — フィボナッチ数列を線形漸化式として解く手法を扱う姉妹concept ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 8, §8.1〜§8.2. - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 21, §21.3.1.