Euclidの互除法とは与えられた2つの自然数の最大公約数を求めるアルゴリズムである。
世界で最初のアルゴリズムとも言われていて知らない人はそんなにいないと思う。
最大公約数を求めるための自然な発想は素因数分解だと思われるが素因数分解を高速で解くアルゴリズムは知られていない。一方でEuclidの互除法は速いと言われている。
速い、といってもどのぐらい速いのかはあまり知られていないのでは。
実はLaméの定理というのがある。
-----
定理（Lamé）
与えられた自然数を$a,b$とし$ 0 < |a| \leq |b|$とする。
このときEuclidの互除法は高々
\frac{ \log |b| }{ \log \phi } +1
回の操作で終了する。ただし$phi$は黄金比である。
-----
$\frac{ 1 }{ \log \phi } \sim 4.78$ ぐらいなので大体$b$の桁数の5倍程度の回数で求めることができる。
面白いことに、Euclidの互除法で一番手間がかかるのはFibonacci数列の連続する2項を選んだときである。
例えば、89と55を選ぶと
89 = 55*1 + 34
55 = 34*1 + 21
34 = 21*1 + 13
21 = 13*1 + 8
13 = 8*1 + 5
8 = 5*1 + 3
5 = 3*1 + 2
3 = 2*1 + 1
2 = 1*2 + 0
より 89と55の最大公約数は1であり、計算回数は9回である。
Euclidの互除法の計算結果にはFibonacci数列の項が次々と現れることもわかる。
定理に突然現れる黄金比も、Fibonacci数列が関わっているとなると寧ろ自然である。
