ユークリッドの 互 除法 図解

有名なアルゴリズム「ユークリッドの互除法」を使って最大公約数を求めるプログラムをつくります。キーボードから2つの整数を指定し、メソッドに渡して最大公約数を求めます。Javaプログラミングの参考になりそうなTipsやクイズのページです。 冒頭でも紹介した「不定方程式」ですが、簡単に復習すると、（未知数の数が式の数より多いため）解がひとつに定まらない（＝不定）方程式のことを言います。詳しくは第1回・第2回をご覧ください。そして、今回学ぶ”一次不定方程式”は、3x+5y=1,(x,yは整数）のような式の(x,y)の値を求めるものです。 ユークリッドの互除法をはじめて学習したときと思われる方は多いのではないでしょうか。ここではそして、ユークリッドの互除法を応用する上でポイントとなるこれは、他のところでも使える考え方なので、ぜひ理解してみてください。まず最初に、ユークリッドの互除法を知らない方や忘れてしまった方のために、”ユークリッドの互除法とは、どういうものか？”ということから始めましょう。例として、\( 56 \) と \( 36 \) の最大公約数を考えてみましょう。\( 56 \) を \( 36 \) を割ると\[ 56 \ \div \ 36 = 1 \cdots 20 \]となるので\( 56 \) と \( 36 \) の最大公約数は、\( 36 \) と \( 20 \) の最大公約数と同じであるということをユークリッドの互除法は言っているのです。そして、実際に最大公約数を求める場合は、割った数\( 36 \) と余りの \( 20 \) に対しても\[ 36 \ \div \ 20 = 1 \cdots 16 \]というふうに、割り算を行います。このように割り算を繰り返していくことで、数がどんどんと小さくなっていき、最終的に最大公約数を見つけられる、ということです。つまり、\( 56 \) と \( 36 \) の最大公約数は、ユークリッドの互除法を使うと\begin{align*}と割り算を繰り返すことで、\( 56 \) と \( 36 \) の最大公約数は \( 4 \) である、と求めることができるのです。では、なぜユークリッドの互除法が成り立ち、最大公約数が求められるのでしょうか。それを理解するために、次のようなタイル貼りの問題を考えていきます。（問題）縦\( 56 \)、横 \( 36 \) の長方形の敷地がある。いま、この敷地に正方形のタイルで隙間なく敷き詰めたい。隙間なく敷き詰められるタイルのうち、１辺の長さが最大のタイルを求めよ。（解説）縦\( 56 \)、横 \( 36 \) の長方形の敷地に対して、１辺が\( x \)の正方形のタイルで隙間なく敷き詰められると仮定します。まず、１辺の長さが\( x \)のタイルを横に敷き詰めていきましょう。すると、以下の図のように、横幅にピッタリと収まります。このように、端まで敷き詰めたとき、タイルを\( n \)枚使ったとすると\[ 36 = x \times n \]が成り立ちますので、また、縦についても、同様に考えるとさらに、２列目、３列目…とタイルを敷き詰めていきましょう。すると、以下の図のように、1辺が\( 36 \)の正方形の敷地を、1辺が\( x \)のタイルで隙間なく敷き詰められることがわかります。いま、１辺\( x \)のタイルで縦\( 56 \)、横 \( 36 \) の敷地が敷き詰められると仮定したので、まだタイルが敷き詰められていない縦 \( 20 \)、横 \( 36\) の長方形も１辺\( x \)のタイルで隙間なく敷き詰められなくてはなりません。つまりということが言えます。さらに、縦\( 20 \)、横\( 36 \)の長方形についても、タイルを敷き詰めていきましょう。すると、以下の図のように、1辺が\( x \)の正方形で1辺が\( 20 \) の正方形を敷き詰めることができることがわかります。このことから、さらに、残りの縦\( 20 \)、横\( 16 \)の長方形も１辺\( x \)の正方形で隙間なく敷き詰められなければなりません。つまりということになります。さらに、これまでやってきたようにタイルを敷き詰めていくことで、以下のような図を得ることができます。つまりということになります。このことから、さらに、縦\( 4 \)、横 \( 16 \) の長方形は１辺が \( 4 \) の正方形で敷き詰めることができます。また、１辺が\( 5 \) 以上の正方形では、縦\( 4 \)、横 \( 16 \) の長方形からはみ出します。よって、つまり、ここまでの流れをまとめると、以下のようになります。\( x \)は、\( 56 \)と\( 36 \)の公約数であるつまりということが言えるのです。ユークリッドの互除法を図で見ることで、その原理や仕組みが理解できたでしょうか。ここでは、復習の意味も込めて、ポイントとなるのはということです。まず、\( x \)が\( 56 \) と \( 36 \) の公約数であるとします。つまり、\( 56 \) も \( 36 \) も\( x \)で割り切れることになります。また、\[ 56 = 36 + 20 \]というようにそうすることによってということがわかります。つまりということがわかったのです。さらに、\( 36 \)についても同じように\[ 36 = 20 + 16 \]と分けることができますので、\( 16 \) も\( x \)で割り切れなければならない。\( 20 \)も同様に\[ 20 = 16 + 4 \]とでき、\( 16 \) も\( x \)で割り切れなければならない。また、ここまで来ると、数字も小さくなり、\( 16 \) と\( 4 \) の最大公約数は \( 4 \) であることが簡単にわかります。つまり、ここでも\( x \)は、\( 56 \)と\( 36 \)の公約数であるとなります。つまり\( 56 \)と\( 36 \)の最大公約数は\( 4 \) であるとわかります。この考え方を使うと、”不定方程式を解く際に、なぜユークリッドの互除法を使うのか？”ということがわかります。※詳細については、

この記事は、・ユークリッドの互除法の「やり方」は分かっているが、その【仕組み】を聞かれたら説明できない、、、というあなたへ向けて、・なぜユークリッドの互除法を使えば、最大公約数がもとまるのか、徹底解説していきます。・この記事で仕組みまで理解できれば、今までなんとなく解いていた整数問題の見方が変わってくるようになります。ぜひじっくりとご覧ください。※2019/06/20更新：確認問題を差し替えました。目次(タップした所へ飛びます)さて、整数問題では時々最大公約数を見つける必要がある場合に出くわします。「不定方程式を解く際に必要な特殊解」もその応用例ですね。この最大公約数を見つける数の組みが（12と20）のような小さな数の場合は、次の様な素因数分解で簡単に見つけることができます。→12=ところが、例えば(1219と583)の最大公約数を求めようとすると、かなり苦労します。素因数分解をしようにも、２でも３でも４、５、、、、となかなか割り切れる数が見つかりません。このような時に、ユークリッドの互除法を利用することで、簡単に最大公約数が見つかります。具体的には、大きい方の数（1219)を小さい方の数(583)で割って、1219÷⇔1219＝583×2 +53次に、割った数(583)を余りである(53)で割り、⇔583＝53×11割り切れたので、この商である「試しに、検算してみると1219÷53=23、一方で、583÷53=11 。ここで、23と11は互いに素（１以外に公約数を持たない）なので、確かに1219と583の最大公約数が53であることが確認できました。上記のように、非常に便利なこの「ユークリッドの互除法」ですが、どうしてこのように上手く最大公約数が見つかるのでしょうか。この項では、できるだけ丁寧にその仕組みを解説していきます。ここからは、任意の正の整数AとB（；ただしA＞Bの関係であるとします）さらにその最大公約数をGとします。まず、Aは当然Gを約数に持ちます。同様に、BもGを約数に持つことから、A＝GmB＝Gn  (m,nは互いに素な整数)とおく事ができます。ここで、最大公約数を求めるためにユークリッドの互除法で何をしていたか思い出してみると、大きい方の数字Aを小さい方の数字Bで割っていました。そこで、AをBで割った時の商と余りをそれぞれp,qとすると、A＝B×p＋q と書くことができます。さらに、割った数（ここではB）を余り（ここではq）でもう一度割ります。（文字が増えてきて、ややこしく感じてきたら、先ほど上で行った【1219と583の最大公約数を求めた手順】を見直して、対応させてみてください。）この時のBとqの最大公約数をHとすれば、B＝Hm'  、q=Hn' （m'とn'は互いに素）とおけます。ここで、A=B×p＋qに代入するとA=Hm'p+Hn'⇔A=(m'p+n')Hと変形できるので、(文字式が続きますが、もう少しだけ我慢してください。)次に、A＝B×p+qをq＝AーBpと移項して、はじめに設定したA＝GmとB＝Gnを代入します。すると、q＝GmーGnp⇔q＝G(mーnp)・・・となるので、・・・ここで、これは、すなわち【G=Hである】ということを意味します。はじめの例を使いながら整理すると、A(1219)とB(583)の最大公約数G(この値を求めたい)は、B（割る数:583）とq（余り:53）の最大公約数H(53)と等しい。従って、上で紹介した“大きな数を小さな数で割り、割った数をさらにその余りで割る”ことによって割り切れた商(＝53)が、元々の最大公約数である仕組みがわかったことになります。もし2回で割り切れず、もう一度割り算をする必要がある場合でも、Hと、“その次に割られる数(余りのq)”と“その余り”の最大公約数“I”が等しい・・・。といった風に、最終的にAとBの最大公約数G＝H＝I、となるので、この方法を余りが0になるまで繰り返すことでGが求まります。少し難しいですが、以上がユークリッドの互除法によって最大公約数が求まる仕組みです。ここで、上の仕組みの理解を固めるために、もう一問最大公約数を求める問題を解きます。先ほどの“ヤヤコシイ”文字式と照らし合わせながら、一つ一つ確認していきましょう。問2：「814」と「555」の最大公約数を求めよ。(一)：814÷555=1、、、259⇔814=555×1+259(二)：555÷259=2、、、37⇔555=259×2+37(三)：259÷37＝7、、、0⇔259=37×7ここで割り切れたので終了します。(三)より、(上で説明した、2回で割り切れない、3回割り算が必要な場合でした)さて、今回は文字式が多く一回で全て理解するのは大変だった人もいるかと思います。ぜひ何度も読み返して「人に仕組みを説明できる」レベルまでユークリッドの互除法を自分のものにしましょう！次回は、ユークリッドの互除法(応用編)として『不定方程式の特殊解の探し方と一般解の求め方・「＜関連：「 今回も最後までご覧いただきまして有難うございました。「スマホで学ぶサイト、スマナビング！」では皆さんのご意見や、記事のリクエスト、SNSでの反応などをもとに日々記事の改善、追加、更新を行なっています。記事のリクエストやご質問/ご意見はコメント欄までお寄せください。また、いいね！、B！やシェア、Twitterのフォローをしていただけると励みになります。 Twitterでフォローしようスマホで学ぶサイト、 スマナビング！ All Rights Reserved.

とおき、ユークリッドの互除法の各過程で得られた を満たす割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の約 5 倍繰り返せば、最大公約数に達する（最大公約数を求めるのに、実際、上の例で出てきた、1071 と 1029 の最大公約数を求める過程は、次のように表せる。 したがって、

.