【数の構成】ユークリッドの互除法のふつうの証明

ユークリッドの互除法について、前回、正方形を使って視覚的・直観的に証明する方法をみましたが、計算式を使ったふつうの証明についてもいちおう確認しておきます。

いま、ＡとＢの最大公約数・GCDを 「Ｇ1」 とします。すると、AとBはそれぞれ、G1との関係において以下のように表せます。

また、AとBは、互除法の剰余の関係において、以下のように表せますので、これを変形して上式をあてはめると、

ここから、AとBの最大公約数G1は、剰余の r にも含まれている（ r の約数である）ことがわかります。

一方、互除法の次ステップであるBと剰余 r の最大公約数を「G2」とすると、同様に以下となりますので、これを(1)に代入して、

ここから、Bと r の最大公約数G2は、Aにも含まれている（Aの約数である）ことになります。

AとBの最大公約数「G1」は、r にも含まれていることから、Bと r の公約数でもあります。従って、G1はBと r の最大公約数であるG2自身か、少なくともその約数であることになります。

一方、Bと r の最大公約数「G2」は、Aにも含まれていることから、AとBの公約数でもあります。よって、G2はAとBの最大公約数であるG1自身か、少なくともその約数であることになります。

上の二つが同時に成り立つのは、「G1＝G2」 のときだけです。従って、AとBのGCDは、Bと r の最大公約数とイコールであり、以下それを繰り返し続きますので、互除法のアルゴリズムで最後に残ったGCDは、最初の2数のGCDと同じ数です。

互除法生成マシン

ところで、例によって、この互除法の手順を関数に入れて、はじめの2数を指定するとGCDを算出するツールを作ってみました。

通常の余り付き割り算の表記の並びは、「A÷B＝Q‥R」ですが、互除法では余りしか使わないので、QとRを入れ替えて「A-B-R-Q」としておきます。こうしておくと、被除数・割り数・余りは、図のように左斜め下に数値を機械的に流してやればいいので、簡単です。

なんということはない、単純なツールですが、互除法の計算があっという間にできて、なかなか重宝です。

以下、これを使って、もう少し互除法の話を広げます。