ユークリッドの互除法

ユークリッドの互除法

最大公約数 (GCD: Greatest Common Divisor) の計算方法として、ユークリッドの互除法というアルゴリズムがよく知られているので紹介します。

以下では、整数 a, b に対して ab で割った余りを a \bmod b と書きます。プログラム言語ではしばしば a % b と書きます。

a, b を正の整数としても一般性を失わないのでそのようにします。

アルゴリズム

  1. 必要であれば値を取り換えて a > b とします
  2. r = a \bmod b を計算します
  3. r0 であれば b が最大公約数となります
  4. r0 でなければ b, r を新たな a, b として手順の最初に戻ります

証明

a, b の公約数の集合と b, a \bmod b の公約数の集合が等しいことを示せば、両者の最大公約数が一致し、上記のアルゴリズムで GCD が計算できるとわかります。

da, b の任意の公約数とすると、ある整数 m, n を用いて a = md, b = nd と書けます。 r = a \bmod b と置くとある整数 s を用いて r = a - sb と書けます。 r = md - snd = (m - sn) d より rd で割り切れます。すなわち db, r = a \bmod b の公約数です。

逆に d'b, r = a \bmod b の任意の公約数とすると、ある整数 m', n' を用いて b = m'd', r = n'd' と書けます。 a = sb + r より a = sm'd' + n'd' = (sm' + n') d' となり ad' で割り切れます。すなわち d'a, b の公約数です。証明終わり。

具体例

a = 30, b = 18

  1. 30 \bmod 18 = 12
  2. 18 \bmod 12 = 6
  3. 12 \bmod 6 = 0

最大公約数は 6 です。実際に 30 = 5 \times 6, 18 = 3 \times 6 です。

a = 39, b = 35

  1. 39 \bmod 35 = 4
  2. 35 \bmod 4 = 3
  3. 4 \bmod 3 = 1
  4. 3 \bmod 1 = 0

最大公約数は 1 です。なお ab の最大公約数が 1 (1 以外の共通因数を持たない) の場合に ab は互いに素であるといいます。

コード

python での実装例を下記に示します。

計算量

ユークリッドの互除法の計算量は O(\log_{2} n) になります。

  1. a \bmod b = r_1
  2. b \bmod r_1 = r_2
  3. r_1 \bmod r_2 = r_3

手順の過程において r_1 \geq 2r_2 であった場合は 2r_3 \leq 2r_2 \leq r_1 となります。一方で r_1 < 2r_2 であった場合は r_3 = r_1 \bmod r_2 = r_1 - r_2 に注意すると r_1 < 2r_2 = 2(r_1 - r_3) となり、整理して 2r_3 < r_1 となります。

r_2 がいずれの場合も 2r_3 \leq r_1 となり、手順を二回行うと余りが \frac{1}{2} より小さくなるため、繰り返す手順の回数は 2\log_{2} b で抑えられます。

より精密な評価として ラメの定理 (必要な回数は、小さい方の b の桁数の 5 倍で抑えられる) が知られています。

例えば b が 9 桁の数である場合に、前者は 2\log_{2} b < 2 \log_{2} 10^{10} = 20 \log_{2} 10 < 68 となり、後者は 5 \times 9 = 45 となります。

d = \gcd(a, b)a, b の整数係数多項式として表す

a, b を正の整数としたときに a, b の最大公約数 d = \gcd(a, b) に対して

    \[d = xa + yb\]

となる整数 x, y を求めることができるでしょうか。

実はすでにユークリッドの互除法の手順に x, y を求める方法が含まれています。例えば a = 39, b = 35 の場合に最大公約数を求める手順の中で前のステップの値を次のステップに順次代入していくことで計算できます。

  1. 39 - 35 = 4
  2. 35 - 8 \times 4 = 3
  3. 35 - 8 (39 - 35) = 3
  4. -8 \times 39 + 9 \times 35 = 3
  5. 4 - 3 = 1
  6. (39 - 35) - (-8 \times 39 + 9 \times 35) = 1
  7. 9 \times 39 - 10 \times 35 = 1

より x = 9, y = -10 となります。

コード

python での実装例を下記に示します。

“ユークリッドの互除法” への1件の返信

コメントは受け付けていません。