📂整数論

ユークリッドの互除法の証明

アルゴリズム

定理

$ r_i<r_{i+1}$に対して、漸化式$r_{i-1} = q_{i+1} \cdot r_{i} + r_{i+1}$を満たす$a: = r_{-1}$と$b:=r_{0}$を定義しよう。$r_{n+1} = 0$を満たす$n$に対して、$a,b$の最小公倍数は次のようになる。 $$ r_{n} = \gcd (a,b) $$ このアルゴリズムは多くとも$ 2 \log _2 (b) + 1 $回以内に答えを求めることができる。

説明

いわゆるユークリッドの互除法^{Euclidean algorithm}として知られるこのアルゴリズムは、最大公約数を非常に効率的に求められるようにしてくれる。いちいち素因数分解をしなくても答えを出すため、数が大きくなるほどいっそう真価を発揮する。

上でまとめられたアルゴリズムは純粋にユークリッドの方式をそのまま写しただけであり、コードはもっと簡単に書ける。

証明¹

$$ \begin{align*} a = r_{0} =& b \cdot q_1 + r_1 \\ b = r_{1} =& r_2 \cdot q_2 + r_3 \\ &\vdots \\ r_i =& r_{i+1} \cdot q_{i+1} + r_{i+2} \\ &\vdots \\ r_{t-1} =& r_t \cdot q_t \end{align*} $$ とする。与えられた条件である $$ r_{i-1} = r_i \cdot q_i + r_{i+1} \qquad , (r_i>r_{i+1}) $$ から、$r_{i-1}$と$ r_i$の約数は$r_{i+1}$の約数でもあることがわかる。したがって $$ \text{gcd}( r_{i-1} , r_i )=\text{gcd}( r_i , r_{i+1} ) $$ である。一方、$r_{t-1} = r_t \cdot q_t \qquad , (r_{t+1}=0)$を考えてみると $$ \text{gcd}( r_{t-1} , r_t )=\text{gcd}( r_t \cdot q_t , r_t ) = r_t $$ 今度は所要時間、すなわち所要回数を求めてみよう。その前に$\displaystyle r_{i+2} < {1 \over 2} r_i$であることを示さなければならない。

• $r_{i+1} \le {1 \over 2} r_i$の場合
  $$r_{i+2} < r_{i+1} \le {1 \over 2} r_i$$
• $r_{i+1} > {1 \over 2} r_i $の場合
  $$r_i = r_{i+1} \cdot 1 + r_{i+2}$$ であるから $$ r_{i+2} = r_i - r_{i+1} < r_i - {1 \over 2} r_i \le {1 \over 2} r_i $$ である。まとめると $$ r_{i+2} < {1 \over 2} r_i $$ であり、上の不等式によって $$ \begin{align*} b &= r_1 \\ &> 2 \cdot r_3 \\ &> 2^2 \cdot r_5 \\ &> \cdots \\ &> 2^k \cdot r_{2k+1} \end{align*} $$ である。まとめると $$ b > 2^k \cdot r_{2k+1} $$ 一方、$2^k \ge b$であるから$r_{2k+1} < 1$でなければならず、それはすなわち $$ r_{2k+1} = 0 $$ である。また、$t+1 \le 2k +1$であるから $$ t \le 2k $$ 言い換えれば、アルゴリズムを終えるのにかかる総回数は$t$以下であり、 $$ t \le 2k = 2(k-1) + 2 < 2 \log _2 (b) + 2 $$ であるから、所要回数は多くとも次のとおりである。 $$ 2 \log _2 (b) + 1 $$

■

実装

以下はユークリッドの互除法をRコードで書いたものである。一つ目はアルゴリズムをそのまま写したバージョンであり、下の方は無駄な部分を削ってきれいに整理したバージョンである。

gcd<-function(a,b)
{    
    if (b>a) {i=b; b=a; a=i;}
    i=2
     r=numeric(0)
    r[1]=b
    r[2]=a%%b
    while(r[i]!=0)
    {
        r[i+1]=r[i-1]%%r[i]
        i=i+1
    }
    return(r[i-1])
}
 
gcd <- function(a, b) {
  if (b>a) {i=b; b=a; a=i;}
  while(b) {
    temp = b
    b = a %% b
    a = temp
  }
  return(a)
}