ユークリッドの互除法とたわむれる

正の整数 a, b があって、a を bで割ったときの商 q と余り r の関係を式にすると次のようになります。

$$a = bq + r  (0 ≦ r < b) ・・・①$$

ここで、a と b の最大公約数を m とします。そして式①を変形して、

$$r = a – bq ・・・②$$

この式の右辺の第一項には a、第二項には b が因数として含まれているため、右辺全体として a と b の最大公約数 m の倍数になっています。つまり、a と b の最大公約数 m は r の約数でもあるわけです。式にしてみると次のような感じでしょうか。

$$r = mα$$

次に、b と r の最大公約数を n とします。そして、上記の議論から a と b の最大公約数 m も b と r の公約数であることが分かっているので、公約数としては n は最大公約数なので、次のように言えます。

$$m ≦ n・・・③$$

ここで、 b と r の最大公約数 n を意識しながら式①を見てみると、右辺は 第一項に b、第二項に r を因数として含むため、右辺全体として n の倍数になっていることがわかります。これをあえて式にしてみると次のようになります。

$$a = nβ$$

つまり、b と r の最大公約数 n は、a と b の公約数でもあるとわかりました。a と b の公約数としては、m が最大公約数なので、次の関係が成り立ちます。

$$n ≦ m・・・④$$

そして、式③と式④からじつは、

$$m = n$$

となります。


$$a = bq + r  (0 ≦ r < b) ・・・①$$

まとめると、正の整数 a, b の割り算の式①の関係が成り立っているとき、a と b の最大公約数 m と b と r の最大公約数 n は等しいといえます。