高校数学マスマスター

学校や塾では教えてくれない、元塾講師の思考回路の公開

基礎知識

【整数】ユークリッドの互除法の証明と例題

数学の基礎

ある二つの自然数の最大公約数を求めるための方法として、ユークリッドの互除法というものがあります。

もちろん、ユークリッドの互除法を使わずとも、素因数分解を行えば最大公約数を求めることはできます。

しかし、最大公約数を求めたい二つの自然数が大きければ大きいほど計算の手間がかかりますので、そのような場合にはユークリッドの互除法が役に立つことになります。

ここではユークリッドの互除法の証明とその例題を扱います。

ユークリッドの互除法

ユークリッドの互除法とは次のことをいいます。

  1. ab で割った余り r_1 を求める。
  2. br_1 で割った余り r_2 を求める。
  3. r_1r_2 で割った余り r_3 を求める。
    \cdots
  4. この操作を繰り返し、余りが 0 となったときの割る数が ab の最大公約数となる。

ユークリッドの互除法の証明

上のような手順で最大公約数が求められるということは信じがたいですね。

なぜこの手順で最大公約数が求められるのかを証明してみましょう。

証明

ab で割った商を Q, 余りを R とすると、

(1)   \begin{eqnarray*} a &=& bQ + R \end{eqnarray*}

と表すことができます。

また、a, b の最大公約数を G_1とすると、互いに素な自然数 a', b' を用いて、

    \begin{eqnarray*} \begin{cases}     a = a'G_1 \\     b = b'G_1 \\   \end{cases} \end{eqnarray*}

と表すことができ、これらを(1)式に代入すると、

    \begin{eqnarray*} a'G_1 &=& b'G_1Q+R \\\\ R &=& b'G_1Q -a'G_1 \\\\ &=& G_1(b'Q -a') \\\\ \end{eqnarray*}

よって、 RG_1 で割り切れることとなり、 G_1bR の公約数(最大公約数かどうかは不明)となるので、 bR の最大公約数を G_2 とすると、

(2)   \begin{eqnarray*} G_1 \leqq G_2 \\\\ \end{eqnarray*}

が成り立ちます。

また、bR の最大公約数を G_2 としたことにより、 bR は互いに素な自然数 b'', R' を用いて、

    \begin{eqnarray*} \begin{cases}     b = b''G_2 \\     R = R'G_2 \\   \end{cases} \end{eqnarray*}

と表すことができ、これらを(1)式に代入すると、

    \begin{eqnarray*} a &=& b''G_2 Q + R'G_2 \\\\ &=& G_2(b'' Q + R') \\\\ \end{eqnarray*}

よって、 aG_2 で割り切れることとなり、 G_2ab の公約数(最大公約数かどうかは不明)となるので、

(3)   \begin{eqnarray*} G_1 \geqq G_2 \\\\ \end{eqnarray*}

(2), (3)式を同時に満たすのは、

(4)   \begin{eqnarray*} G_1 = G_2 \\\\ \end{eqnarray*}

のときだけであることから、ab で割った余りを R とするとき、ab の最大公約数と bR の最大公約数が一致することがわかります。

そして、同様にして bR で割った場合を考え \cdots といったように、一連の操作を繰り返していくと、余りの定義から余りは割る数より必ず小さくなるので、有限回の操作で余りは0となり繰り返しの操作は終了となります。

そして、余りが 0 となったときの割る数が a, b の最大公約数であることとなります。

以上により、ユークリッドの互除法によって、最大公約数が求まるということが証明されました。

ユークリッドの互除法の例題

上の証明は難易度が高いと思いますが、現実的には互除法の操作を適切に行うことができればひとまず十分かと思います。

ユークリッドの互除法を用いて実際に最大公約数を求めてみましょう。

例題 : 1815693の最大公約数を求めよ

マスマスターの思考回路

素因数分解を行うと、
1815 &=& 3^1 \cdot 5^1 \cdot 11^2
693 &=& 3^2 \cdot 7^1 \cdot 11^1
であることから、最大公約数は 3^1 \cdot 1^1 = 33 となります。
これをユークリッドの互除法で求めましょう。

    \begin{eqnarray*} 1815 &=& 693 \cdot 2 + 429 \\\\ 693 &=& 429 \cdot 1 + 264 \\\\ 429 &=& 264 \cdot 1 + 165 \\\\ 264 &=& 165 \cdot 1 + 99 \\\\ 165 &=& 99 \cdot 1 + 66 \\\\ 99 &=& 66 \cdot 1 + 33 \\\\ 66 &=& 33 \cdot 2 + 0 \\\\ \end{eqnarray*}

よって、1815693の最大公約数は 33 となります。

マスマスターの思考回路

余りが 0 となったときの割る数が求めたい最大公約数であり、最初に素因数分解により確認した最大公約数33に一致してることがわかりますね。

ユークリッドの互除法の説明の終わりに

いかがでしたか?

ユークリッドの互除法を用いることにより最大公約数を求められることがおわかりいただけたかと思います。

ユークリッドの互除法は最大公約数を求めることができるだけでなく、不定方程式の解を求める際にも利用価値が高いので、ぜひ身につけておきましょう。

twitter はじめました!

中学生・高校生の方向けに、数学に関する相談、質問を受け付けています。
長期休暇中の課題について、数学の勉強方法についてなど、出来る範囲でお答えします。

ご応募いただいた内容はwebサイトの記事にする可能性がありますのでご了承ください。

-基礎知識
-