📂整数論

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

アルゴリズム

定理

$ 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)
}