Web教材一覧アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)

ユークリッドの互除法

学習のポイント

素数に関係するアルゴリズムで有名なユークリッドの互除法、それを拡張した拡張ユークリッドの互除法について学習します。

キーワード

アルゴリズム、最大公約数、ユークリッドの互除法、拡張ユークリッドの互除法


最大公約数(GCD:Greatest Common Divisor)とは、2つの正整数aとbを素因数分解してときの共通項です。例えば
   a=924(=2×2×3×7×11)
   b=360(=2×2×2×3×3×5)
の最大公約数Gは
   G=2×2×3=12
になります。

なお、最小公倍数(LCM:Least Common Multiple)は、aとbで割り切れる最小の整数のことです。
   a=G×(7×11)
   b=G×(2×3×5)
なので、最小公倍数Lは、
   L=G×(7×11)×(2×3×5)
となります。すなわち、
   L=a×b/G=924×360/12=27720
で計算できます。

ユークリッドの互除法

ユークリッドの互除法は、最大公約数を計算する効率的なアルゴリズムです。

アルゴリズム
正整数a、b(a>b)の最大公約数を求める手順を示します。
  ア aをbで割った剰余をrとする。
  イ rが0ならばbが最大公約数である。
  ウ rが0でないならば、a←b、r←bとして、アへ戻る。
プログラム
  function euclid(a, b) {
    r = a % b;    /* rはa/bの剰余 C言語なら a mod b と記述 */
    while (r > 0) {
      a = b;
      b = r;
      r = a % b;
    }
    return b;
  }
 再帰を用いた場合
  function euclid_recursive(a, b) {
    if (b == 0) gcd = a;
    else gcd = euclid_recursive(b, a % b); /* C言語では a mod b と記述 */
    return gcd;
  }
数値例
(a=924、b=360)
   a   b   r
  924 360 204(=924-2×360)   (ア)
  360 204 156(=360-1×204)
  204 156  48(=204-1×156)
  156  48  12(=156-3×48)
   48  12   0(=48-4×12)
        └─→最小公倍数=12
プログラムの改善
上のプログラムには、いくつかの改善点があります。
  • 引数として渡されたaとbの値が変化してしまいます。呼び出したプログラムのなかでaやbを用いることもあるので、一般的には、呼び出された側で新しい変数にして、影響を少なくするようにします。ここでは、引き渡される引数の名称を変えました。
  • a>b>0の制約がありますが、渡された数値の大きいほうをaとするように内部で置換したほうが、取り扱いを容易になります。また、aやbが負数のときにも使えるように、絶対値にしたほうがよいでしょう。
  • 剰余rを求めた結果が、r>b-r のときは、r=b-rと置き換えたほうが、rの値が小さくなるので、より容易に計算することができます。
     例えば、上のアでは、b=360、r=204ですので、r=360-204=48とするのです。
     これは、924-3×360=-48からも求められます。後述の「証明」からわかるように、整数商qは最大公約数に影響を与えないので、このようにしてもよいのです。
これらを考慮したプログラムを示します。
  function euclid(n1, n2) {
    var a, b, r;  /* これらの変数は関数内でのみ有効。他のプログラムには無影響 */
    a = Math.abs(n1);  /* n1の絶対値 */
    b = Math.abs(n2);
    if (b > a) {    /* b>a のときの置き換え */
      r = a; a = b; b = r;
    }
    r = a % b;
    while (r > 0) {
      if (r > b-r) r = b-r;  /* 剰余の修正 */
      a = b;
      b = r;
      r = a % b;
    }
    return b;
  }

トレースすると、下のようになり、1回少なく結果に達しています。
(a=924、b=360)
   a   b   r
  924 360 156(924-2×360=204、360-204=156)
  360 156  48(360-2×156=48)
  156  48  12(156-2×48=12)
   48  12   0(48-4×12)
        └─→最小公倍数=12
ユークリッドの互除法の証明
aをbで割ったときの商をq、剰余をrとすると、
   r=a-q×b
となります(a=924、b=360とすると、r=924-2×360=204)。
ここで、aとbの最大公約数 GCD(a,b) をgとすれば、aもbもgで割り切れるので、rもgで割り切れます(この段階では、gが24であることはわかっていないのですが、r=204(=17×24)はg=24で割り切れます)。すなわち、
   GCD(a,b)=GCD(b,r)   GCD(924,360)=GCD(360,204)
の関係があります。GCD(a,b) を求めるかわりに、GCD(b,r) を求めればよいし、しかも、r<b<aなので、GCD(b,r) を求めるほうが簡単です。
「b←a、r←a/bの剰余」の置き換えを繰り返すことにより、より小さい数の組み合わせになります。 そして、rが0になるまで繰り返されるのですから、最終的には、
   GCD(a,b)=GCD(b,0)
となります(GCD(360,204)=GCD(204,156)=GCD(156,48)=GCD(48,12)=GCD(12,0) )。
ここで、GCD(b,0) とは、bと0との最大公約数であり、0はどんな数でも割り切れるのですから、GCD(b,0) =b であることは明白です。すなわち、
   GCD(a,b)=b   GCD(924,360)=12
となります。
計算量
最大公約数の計算量では、剰余の計算回数が尺度になります。私は理解していないのですが、ラメ(Lame')の定理によれば、最悪の場合でも、剰余の計算回数bの桁数の5倍以下であることが証明されています(b=360は3桁、3×5=15回以下)。
 また、k回の剰余計算が必要となるとき、bはk番目のフィボナッチ数以上であることが証明されています(フィボナッチ数とは、F(k)=F(k-1)+F(k-2)、 F(1)=1、F(2)=1で定義される級数のこと。F(13)=233,F(14)=377)。

拡張ユークリッドの互除法

拡張ユークリッドの互除法は、自然数aとbを与えたとき、不定方程式
   ax+by=g (gはaとbの最大公約数)
となる整数(負の場合もある)xとyを求める方法です。

例えば、a=924,b=360とすると、g=12となり、
   924×(-7+30t)+360×(18-77t)=12
になります。このような、
   x=-7+30t
   y=18-77t  (tは任意の整数)
を求める方法です。

アルゴリズム

ax+by=gを
   a×x+b×yi=r   ①
と表記します。
 初期値を
   x=1,y=0、r=a(=924)
   x=0,y=1、r=b(=360)
とすれば、①は
 i=0のとき、a×x+b×y=r → a×1+b×0=a
 i=1のとき、a×x+b×y=r → a×0+b×1=b
となり、成立しています。

をri-1/rの整数部分、ri+1をその剰余とし、
   ri+1=ri-1-q×r  ②
   xi+1=xi-1-q×x  ③
   yi+1=yi-1-q×y  ④
と定義します。

i=1のときは、q=r/rの整数部分なので、q=924/360=2となります。
②③④から、
   r=r-q×r (924-2×360=204)
   x=x-q×x (1-2×0=1)
   y=y-q×y (0-2×1=-2)
となるので、これを①に代入すれば、
   a×x+b×y=924×1-360×(-2)=204=r
となり、①が成立しています。

i=kのときは
   xk+1=xk-1-q×x
   yk+1=yk-1-q×y
とすれば、
   a×xk+1+b×yk+1=(a×xk-1+b×yk-1)+q×(a×x+b×y
となり、
   a×xk-1+b×yk-1=rk-1
   a×x+b×y=r
ですから、
   a×xk+1+b×yk+1=rk+1
となり、数学的帰納法により、①が常に成立することが証明されます。

ここで、ri-1=0になるときのrがaとbの最大公約数であることは、先のユークリッドの互除法での説明からわかります。

そして、①の関係を保ちながら式の変形をしてきたので、xとyは、
   ax+by=g
を満足しています。
 後述のトレースにより、a=924、b=360のときは、x=-7,y=18になり、
   924×(-7)+360×(18)=12
となります。

不定方程式では、xとyの値はいくらでもあります。証明は省略しますが、上の計算で得られたxとyをx*、yをy*とし、最大公約数をgとしたとき、tを任意の整数として
   x=x*+(b/g)×t  (x=-7+30t)
   y=y*-(a/g)×t  (x=18-77t)
も、ax+by=gの解になります。
   924×(-7+30t)+360×(18-77t)
  =-6468+27720t+6480-27720t
  =12

プログラム

  function ex_euclid(a, b, gcd, x, y){
    r0 = a; r1 = b;
    x0 = 1; x1 = 0;
    y0 = 0; y1 = 1;
    while (r1>0) {
      q = Math.floor(r0/r1);
      r2 = r0 % r1;
      x2 = x0 - q*x1;
      y2 = y0 - q*y1;
      r0 = r1; r1 = r2;
      x0 = x1; x1 = x2;
      y0 = y1; y1 = y2;
    }
    gcd = r0;
    x = x0;
    y = y0;
  }

トレース
a=924,b=360としたときの経過を示します。

q   r0  r1  r2   x0 x1 x2   y0 y1 y2
2  924 360 204    1  0  1    0  1 -2
1  360 204 156    0  1 -1    1 -2  3
1  204 156  48    1 -1  2   -2  3 -5
3  156  48  12   -1  2 -7    3 -5 18
4   48  12   0    2 -7 30   -5 18-77
4   12   0   0   -7 30 30   18-77-77
     ↓   ↓        ↓  ↓       ↓  ↓
     g   終了        x  b/g       y  -a/g
基本解
   a    x   b    y   GCD
  924×(-7)+360×(18)=12
一般解
   b/g=x1= 30  x=-7+30t
  -a/g=y1=-77  y=18-77t

計算プログラム

1=ユークリッドの互除法(最大公約数と最小公倍数を求める)a>b>0
1=ユークリッドの互除法(改良版)a,bは任意
3=拡張ユークリッドの互除法(ax+by=最大公約数、xとyを求める)
方法= a=  b=


アルゴリズムへ