[mathjax]
正の整数 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 は等しいといえます。