ユークリッドの互除法

ユークリッドの互除法の例

ユークリッドの互除法では，以下の重要な性質を使って最大公約数の計算を行います。

重要な性質：

割り算の等式: a = bq + r において

「aとbの最大公約数」 = 「bとrの最大公約数」

例

390と273の最大公約数を求める

a=390, b=273とすると

390=273・1+117

であり、q=1, r=117

「390とb273の最大公約数」 = 「273と117の最大公約数」

273と117の最大公約数を求める

a=273, b=117

273=117・2+39

q=2, r=39

「273と117の最大公約数」 = 「117と39の最大公約数」

117と39の最大公約数を求める

a=117, b=39

117=39・23

よって、117と39の最大公約数は 23 となり、

390と273の最大公約数は 23 になる。

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

以降、最大公約数(Greatest Common Division) を gcd という記号で表し、aとbの最大公約数を gcd(a, b) と表す。

aをbで割った商をq, 余りをrとすると (0 < r < b)

a = bq+r ・・・①

aとbがGの公約数を持つ時

a = Ga', b = Gb' ・・・②

②を①に代入すると

G(a'-b'q) = r となり、

r' = a'-b'q とすると

r = Gr' ・・・③

②, ③ より、aとbの公約数は、bとr の公約数となる・・・④

次に、bとrがGの公約数を持つ時

①より、aもGの倍数となる

すなわち、bとrの公約数は、aとb の公約数となる・・・⑤

④、⑤より、a,bとb,r は全く同じ約数をもち、最大公約数も同じになる。

以上より、

「割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する」(ユークリッドの互除法証明終了)

実装

xとyの最大公約数を返す関数

Python(ループを使う)

def gcd(a, b):
    while b != 0:
        a, b = b, a%b # 割る数を割られる数、割られる数を余りに変える
    return a

Python(再帰関数を使う)

def gcd(a, b): # a(割られる数), b(割る数)
  if b==0: return a # 余りが0だった場合、割る数が最大公約数
  return gcd(b, a%b) # b(割る数), a%b(余り)

解説すると、

関数gcdは 割られる数(第一引数)と割る数(第二引数)から最大公約数を返す関数

第一引数に割る数、第二引数に割られる数を指定しても、最大公約数は同じになる

すなわち、

gcd(a,b) = gcd(b, a%b) の関係が成り立つ