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

基礎知識

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

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

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

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

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

ユークリッドの互除法

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

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

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

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

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

証明

a を b で割った商を 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*}

よって、 R はG_1 で割り切れることとなり、 G_1 は b と R の公約数（最大公約数かどうかは不明）となるので、 b と R の最大公約数を G_2 とすると、

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

が成り立ちます。

また、b と R の最大公約数を G_2 としたことにより、 b と R は互いに素な自然数 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*}

よって、 a はG_2 で割り切れることとなり、 G_2 は a と b の公約数（最大公約数かどうかは不明）となるので、

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

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

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

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

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

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

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

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

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

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

例題 : 1815と693の最大公約数を求めよ

マスマスターの思考回路

素因数分解を行うと、
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*}

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

マスマスターの思考回路

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

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

いかがでしたか？

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

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

【基礎】整数の性質のまとめ

基礎知識

整数

プロフィール

-このサイトの記事を書いている人-

某国立大工学部卒のwebエンジニアです。
学生時代に塾講師として勤務していた際、生徒さんから「解説を聞けば理解できるけど、なぜその解き方を思いつくのかがわからない」という声を多くいただきました。
授業という限られた時間の中ではこの声に応えることは難しく、ある程度の理解度までに留めつつ、繰り返しの復習で覚えてもらうという方法を採らざるを得ないこともありました。
本ブログでは「数学の問題を解くための思考回路」に重点を置いています。
それらを通じて自らの力で問題を解決する力が身につくお手伝いができれば幸いです。

検索

この記事の目次

関連記事

サイドメニュー