ユークリッドの互除法（考え方）

ユークリッドの互除法の使い方はシンプルですが、なぜ、その使い方で最大公約数が計算できるのか、原理について考えてみました。

はじめに、2つの自然数$${a,b}$$を考え、$${a\geqq b}$$とします。
aをbで割った時の商をq、余りをrとすると、次の様に書くことができます。

$${\large a=bq+r}$$

いま、aとbの最大公約数をGとして、上式の両辺をGで割ると、

$${\Large\frac{a}{G}=\frac{bq+r}{G}}$$

$${\Large\frac{a}{G}=\frac{bq}{G}+\frac{r}{G}}$$

Gはaとbの最大公約数なので、左辺のaはGで割り切れます。則ち左辺の

$${\Large\frac{a}{G}}$$

は自然数となり、等式の性質から、右辺も自然数にならなければいけません。
そこで右辺に着目すると、bはGで割り切れて自然数になります。また、qも自然数なので、

$${\Large\frac{bq}{G}=\frac{b}{G} \cdot q}$$

の項は自然数×自然数＝自然数になります。と言うことは、

$${\Large\frac{r}{G}}$$

の項も自然数にならなければいけませんね？ したがって、rはGで割り切れることがわかります。

したがってGはa,b,rの公約数といえます。しかし、Gがbとrの最大公約数であるかは分かりません。そこでさっきの式を見ながら、もう少し考えてみましょう。

$${\Large\frac{a}{G}=\frac{bq}{G}+\frac{r}{G}}$$

bとrの最大公約数をgとすると、gはbとrの公約数の中で最も大きい値ですから、gはGと等しいか、gはGより大きくならなければなりません。則ち

$${\large g\geq G}$$

同様に、

$${\large a=bq+r}$$

の両辺をbとrの最大公約数gで割ると

$${\Large\frac{a}{g}=\frac{bq}{g}+\frac{r}{g}}$$

$${\Large\frac{a}{g}=\frac{b}{g} \cdot q+\frac{r}{g}}$$

いま、

$${\Large\frac{b}{g},\hspace{10pt}\frac{r}{g},\hspace{10pt}q}$$

の項は全て自然数ですから、右辺は自然数になります。したがって、左辺の

$${\Large\frac{a}{g}}$$

も自然数となり、aはgで割り切れることが分かります。したがって、gはa,b,rの公約数であることが分かります。ここで、先程と同様に、次の式を見ながら考えてみましょう。

$${\Large\frac{a}{g}=\frac{bq}{g}+\frac{r}{g}}$$

aとbの最大公約数Gは、aとbの公約数の中で最も大きい値ですから、Gはgと等しいか、Gはgより大きくならなければなりません。則ち

$${\large G\geq g}$$

整理すると

$${\large g\geq G\hspace{5pt}且つ\hspace{5pt}G\geq g}$$

となるので、この2つの不等式を満たすには

$${\large G=g}$$

まとめると、aとbの最大公約数Gは、bとrの最大公約数gと等しいことになるのです。


最大公約数の計算手順

いま、2つの自然数a、bの最大公約数を求めるためにaをbで割って余りを出し、次の様に書きます。

$${\large a=bq+r}$$

aとbの最大公約数はbとrの最大公約数と等しいので、bをrで割って、

$${\large b=a_2,\hspace{5pt}r=b_2}$$

とすると

$${\large a_2=b_2 q_2+r_2}$$

同様に$${a_2}$$と$${b_2}$$の最大公約数は$${b_2,r_2}$$の最大公約数と等しいので$${b_2}$$を$${r_2}$$で割って余りを出して・・を繰り返します。

最終的に$${r_n=0}$$になった時の$${b_n}$$が$${aとb}$$の最大公約数となります。割り算を繰り返すことにより、元の数a,bよりもずっと小さな2つの自然数を比較することで所望の最大公約数を得ることができるのです。

実際に使ってみよう

今、$${a=8633,b=6319}$$
としてa,bの最大公約数を求めてみましょう。

$${8633=6319\times1+2314}$$
$${6319=2314\times2+1691}$$
$${2314=1691\times1+623}$$
$${1691=623\times2+445}$$
$${623=445\times1+178}$$
$${445=178\times2+89}$$
$${178=89\times2+0}$$

となり、8633と6319の最大公約数は89となります。
この場合、割り算を7回繰り返すことにより、最大公約数を求めることができました。

ユークリッドの互除法のアルゴリズムを用いて、最大公約数を計算する簡易ツールを作成しましたので、興味があれば覗いてみてください↓↓

http://megro-aquarius29.com/?p=1182

最後まで読んでいただき、ありがとうございます。