未分類

ユークリッドの互除法で最大公約数を簡単に求める方法と実戦での使い方

ユークリッドの互除法は世界最古のアルゴリズムとも言われており、主に最大公約数を求めるために使われることで有名です。

今回は、ユークリッドの互除法で最大公約数を求める方法と、実践的な問題での使い方を説明します。

ユークリッドの互除法とは、次のような定理です。

[box04 title="ユークリッドの互除法"]自然数a,\,bについて、abで割ったときの余りをrとすると、abの最大公約数は、brの最大公約数に等しい。[/box04]

証明

abで割ったときの商をqとすると、a=bq+r\tag*{①}

よって

r=a-bq\tag*{②}

abの最大公約数をmbrの最大公約数をnとする。

①より、naの約数でもある。よって、nabの公約数でもある。よってn\leqq m

同様に、②よりmrの約数でもある。よって、mbrの公約数でもある。よってm\leqq n

したがって、m=n\quad \blacksquare

ユークリッドの互除法は、式だけを見ていても何のことか分かりづらいので、次のように覚えましょう。

2つの数があるとき、片方の数から、残りの数を整数倍したものを引いても最大公約数は変わらない。

ある2つの数があり、最大公約数が知りたいときには、片方の数から片方を好きなだけ整数倍して引くことで、片方の数を小さくすることが出来ます

これを繰り返していくことで、いつかは2つの数が同じになります。それが2つの数の最大公約数です。

ユークリッドの互除法の使い方

実際にやってみます。

391,\,299の最大公約数を求めます。2つの数の組の最大公約数を

(391,\,299)

と書くことにします。

まず、片方から片方の整数倍を適当に引きます。このとき、整数倍は適当で構いません。

とりあえず、391から普通に299を引くとちょうど良さそうです。

391-299 = 92

これで、2つの数の組が(391,\,299)から(299,\,92)に変わりました。次は、299から923倍して引くと良さそうです。

299-92\times3=23

2つの数の組が(92,\,23)に変わりました。92から233倍して引くと

92-23\times 3=23

ですから、(23,\,23)です。2つの数が同じになったので、これで終了です。最大公約数は23です。

慣れてくると、このカッコの組だけを繋げて

\begin{aligned} (391,\,299)&=(299,\,92)=(92,\,23)\\&=(23,\,23)=23 \end{aligned}

と求めることが出来るようになります。

このときに、両方の数を整数倍して足し算・引き算をしてしまうと、その結果が最大公約数とは限らなくなってしまうので注意してください。両方の数を整数倍して足し算・引き算するのは拡張ユークリッドの互除法といい、これも重要な手法です。

整数問題を得意にするコツ

整数問題が苦手という人はとても多いです。その原因のひとつは、何でもかんでも文字で置いてしまい、ゴチャゴチャして何をしたら良いのかわからなくなることにあります。

もちろん、式を整理したり、特徴を掴むために文字で置くことはとても重要です。しかし、あまりにも簡単なものにも文字を使いすぎてしまうと、かえって式が見えづらくなってしまい、本末転倒です。この匙加減は難しいところですが、慣れが重要です。

ユークリッドの互除法の使い方と例題

例題として、次の問題を考えてみます。

a,\,bは自然数で、a>bとする。

(1) aa-bの公約数をkとする。kbの約数であることを示せ。

(2) abが互いに素であるとき、aa-bは互いに素であることを示せ。

最初にこれを見たときに、これはユークリッドの互除法だな、と直ちに見抜きます。よって、2つの数を足し算、引き算して次の数を作ります。

解答

(1) a-(a-b)=bより、aa-bの公約数kは、bの約数でもある。

(2) (1)より、aa-bの約数はabの約数でもあり、abは互いに素なのでaa-bも互いに素。

ユークリッドの互除法を使うことに気づけば、これだけシンプルに答案を書くことが出来ます。時間にして30秒もかかりません。(1)は、aa-bからbを作るには、単純にa-(a-b)をすればよいことに気づけば一発です。(2)は、(1)の結果から直ちに導けます。

解答は2行で終わるのですが、実はこれを生徒にやってもらうとかなり苦労するようです。実際の生徒の答案です。

実際の生徒の答案

(1) p,\,qを整数として、aa-bの公約数はkなので

a=kp,\,a-b=kq

とおける。a-b=kp-b=kqより

b=kp-kq=k(p-q)

したがってkbの約数である。

数学的には全く正しいのですが、一言で言えば大袈裟すぎます。結局やっていることはa-(a-b)=bを計算していることと変わりないからです。

文字で置く練習としてやってみる分には構いませんが、この習慣しか身についていないと、式を見通す力が身につかず、より難しい問題になったときに困ります。問題の見通し力をつけるには、文字で置かずとも、どこが最大公約数を作っているのかという2数の関係が見えるようになることが重要です。

案の定、この生徒は(2)(1)を活かしきれず、遠回りな解答を作ってしまっていました。(1)で時間と頭を使いすぎてしまい、(2)に回せなかったことが原因のひとつです。

難しい問題に対し、自ら文字を導入して計算をやりきる力も大切です。しかし、それと同じぐらい、文字で置かなくても関係が見える力も大切です。これは車輪と同じく、お互いにどちらも必要な能力です。整数問題が苦手な人は、このどちらかの力が欠けています(多くの場合、後者です)。

整数問題が苦手な人は、ぜひ文字で置かずとも公約数が見えるように練習してみてください。

  • この記事を書いた人
  • 最新記事

岡田

ラディカル高校数学管理人の岡田です。地方公立高校から一浪して東京大学理科一類に合格。現在工学部在学中。都内で塾講師として高校数学を教え、100人以上の生徒を見てきました。自分の経験を活かして高校数学をわかりやすく教える活動をしています!

-未分類