数学2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られています。このユークリッドの互除法を拡張することにより、$$ax+by=c$$の形をした、2変数の連立一次方程式の整数解を求めることができます。ユークリッドの互除法のアルゴリズムまずはアルゴリズムを説明して、具体例を見てから、数学的証明を与えます。最大公約数」が等しくなることを利用しています。アルゴリズムは以下のようになります。返すa,bの大小関係は考慮していません。あったとしても、一度gcdを再帰的に呼び出したら、gcd(b,a)と順番が入れ替わることに注意してください。最大公約数を例として考えてみます。それではユークリッドの互除法を用いて求めてみましょう。計算量ユークリッドの互除法をのステップを2回行ったあとを考えると、gcd(a,b)のa,bはもともとの半分以下になっているはずです。式が成り立つ事を示しましょう。\tag{2}$$の2つを証明することで示すことができます。$$のように表すことができるとします。(qは商、rは余りです)。任意の公約数をmとします。(1)の式が成立するはずです。次に(2)を考えます。任意の公約数をmとします。(2)の式が成立するはずです。以上より示されました。ax+by=gcd(a,b)$$の形をした、2変数の連立一次方程式の整数解を求めることができます。以下のアルゴリズムです。最大公約数を例として考えてみます。16$$それでは拡張ユークリッドの互除法を用いて求めてみましょう。返すこれで終了しました。同様に最大公約数になり、今回は16です。16$$が成り立つので、これらは解になっています。数学的考察なぜ先程のアルゴリズムで求まるのかを考えてみましょう。以下の2式を考えます。gcd(a,b)$$のようになりました。この形は、(3)の式とよく似ているので、再帰的に求めることができます。\tag{5}$$のようになります。求めることができます。見てもらえば分かるように、再帰的な呼出しをするにつれて小さくなっていきます。gcd(a,b)$$のようになります。コメントをキャンセルメールアドレスが公開されることはありません。*次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。上に表示された文字を入力してください。