Apendix 2 ユークリッドの互除法
f-denshi.com  最終更新日: ***

1.最大公約数の定義

[1] 最大公約数の定義です。

整数 a、d があたえられて、
a=d・q

となるような整数q が存在するとき、d を a の約数、あるいは a は d の倍数であるといいます。
さらに、整数 b があたえられ、d が b の約数でもあるとき、すなわち、

b=d・q’

となるq’が存在するとき、d は a と b の公約数であるといいます。
また、a、b の公約数のうちで最大のものを最大公約数といい、

(a、b)

と書きます。

2.ユークリッドの互除法

[1] 最大公約数を求めるアルゴリズムは以下のとおりです。

ユークリッドの互除法

正整数a、b(a>b)が与えられたとき、以下の方法で最大公約数が求められる。
 (ただし、b=r0と記し、各ステップの割り算の商を正の整数、q1、q2、・・・、qn+1 とした)

[第0ステップ] 
    aをr0(=b)で割り、
             a=q10+r1    (0<r<r0
  とする。

[第1ステップ] 
    r0をr1で割り、
             r0=q21+r2    (0<r2<r1
  とする。   

    ・・・・・・・・・・・・・・・・・・

[第kステップ] 
    rk-1をrkで割り、
             rk-1=qk+1k+rk+1 (0<rk+1<rk
  とする。

  これを繰り返すと、r0>r・・>rk・・・>0 なので、いつか必ず、

[第nステップ] 
    rn-1はrnで割りきれ、
             rn-1=qn+1n       

  となる。このとき、rnはaとbの最大公約数である。すなわち、

    (a、b)=rn

  である。

[2] 証明は次の命題を繰り返し用いて行います。       

命題   

正整数a、b(a>b)が与えられたとき、aをbで割った商をq、余りをrとする。すなわち、

      a=qb+r   (0≦r<b)
とすると、

      (a、b)=(b、r)      

証明→[#]             

[3] この命題をユークリッドの互除法の第0ステップに適用すれば、

(a、b)=(r0、r1

第1ステップ、・・・、第n−1ステップと順に適用すれば、

(r0、r1)=(r1、r2)=・・・=(rn-1、rn)=rn

がわかります。すなわち、

(a、b)=rn

であることがわかります。

[4] ユークリッドの互除法のプロセスを逆に辿ると、非常に重要な次の定理を得ます。

定理

整数 a、b が与えられ、a と b の最大公約数を d とする。このとき、

Xa+Yb=d

をみたす整数 X、Y が存在する。

(証明)

ユークリッドの互除法で第0から第(n−1)ステップまでを変形すると

1 =a  +q1b
2 =b  +q21
3 =r1  +q32
     ・・・・・・・・
n-1=rn-3+qn-1n-2
n =rn-2+qnn-1   

となりますが、各右辺を下の式に順に代入してr1、r2、・・・rn-1を消去していくと、

2 =b  +q2(a+q1b)
3 =(a+q1b)+q3(b+q2(a+q1b))
  =(1+q2q3)a+(q1+q1q2+q3)b
      ・・・・・・・・
     ↓
n =(qi の積と和)a+(qi の積と和)b

を得ます。qi の積と和はもちろん整数ですから定理が証明されたことになります。

[5] 具体的に見てみましょう。定理によると、a=182、b=21 が与えられると

最大公約数 d=7 ⇒  182X+21Y=7 となる整数 X、Y が存在する

が成り立ちます。ユークリッドの互除法で182と21の最大公約数を求める過程は、

182=8・21+14    → 14=182-8・21  ・・・@
 21=1・14+7    →  7=21−1・14  ・・・A
 14=2・7

となり、d=7がわかります。さらに、@をAに代入して、

7=21−1・14
 =21−1・(182−8・21)
 =-1・182+9・21

すなわち、X=-1、Y=9 が方程式 182X+21Y=7 解の一組として求まります。

 このプロセスは辺の長さが182×21の長方形を埋め尽くす正方形のうちで、一辺の長さが最大のものを求めるアルゴリズムと同じになっています。右の図を参照に考察してください。






 [目次へ]


命題の証明