ユークリッドの互除法

2019年12月6日数学最大公約数, 競プロ, ユークリッドの互除法, 拡張ユークリッドの互除法

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。

このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られています。

Input: gcd(48,32)
Output: 16

アルゴリズム

ユークリッドの互除法 (gcd(a,b)):

  1. b が 0 ならば、a を返す
  2. b が 0 でなければ、gcd(b, b%a) を返す

※ 原理としては単純で、「 a と b の最大公約数」と「 b と b割るaの余り の最大公約数」が等しくなることを利用しています。

※ a,bの大小関係は考慮していません。最初の入力が b>a であったとしても、一度gcdを再帰的に呼び出したら、gcd(b,a)と順番が入れ替わることに注意してください。

計算量

  • \(O(\log \min(a,b))\)

ユークリッドの互除法をのステップを2回行ったあとを考えると、gcd(a,b)のa,bはもともとの半分以下になっているはずです。

よって2回ごとに最悪でも半分になることを考えると、計算量は \(O(\log \min(a,b))\) になります。

C++ での実装例

※ gcd はC++17 から標準ライブラリに追加されています。以下は C++14 での例です。

ユークリッドの互除法の気持ちと正当性

アルゴリズムを理解するために、具体例を見てから、数学的証明を与えます。

具体例

48, 32 の最大公約数を例として考えてみます。まずは素因数分解を用いて求めてみると、

$$ 48 = 2^4\times 3$$

$$ 32 = 2 ^5$$

となるので、最大公約数は 16 になります。

それではユークリッドの互除法を用いて求めてみましょう。

  1. gcd(48,32) = gcd(32, 48%32)
  2. gcd(32,16) = gcd(16, 32%16)
  3. gcd(16,0) = 16

これで 16 が求まりました。

数学的証明

以下の式が成り立つ事を示しましょう。

$$gcd(a,b) = gcd(b,b\%a)$$

これは、

$$gcd(a,b) \le gcd(b,b\%a)\tag{1}$$

$$ gcd(a,b) \ge gcd(b,b\%a) \tag{2}$$

の2つを証明することで示すことができます。

以下、\(a \ge b\)として考え、

$$ a = qb + r $$

のように表すことができるとします。(qは商、rは余りです)。

まず(1)を考えます。
a,b の任意の公約数をmとします。これが b, b%a の公約数でもあれば 、(1)の式が成立するはずです。

実際に、b は m の倍数で、

$$ b\%a = r = qb – a$$

から b%a も m の倍数です。

次に(2)を考えます。
(1)の逆で、b, b%a の任意の公約数をmとします。これが a, b の公約数でもあれば 、(2)の式が成立するはずです。

実際に、b は m の倍数で、

$$ a = qb +r $$

から、a も m の倍数です。

以上より示されました。

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

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

$$ ax+by=gcd(a,b)$$

の形をした、2変数の一次方程式の整数解を求めることができます。

練習問題