📂整数論

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

アルゴリズム

定理

$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$の最小公倍数は以下の通りである。 $$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)
}