医学生Gの数学ノート

スキマ時間で読める数学の記事を数学塾講師経験のあるメンバーがお届けします！

#20 ユークリッドの互除法と連分数

〜高1

　こんにちは、医学生Gです。今回はタイトル通りユークリッドの互除法について説明していきたいと思います。ユークリッドの互除法は習ったときはわかった気になっても、時間が経ってしまったら忘れてしまう人も多いかと思います。

あ、ちなみにこの方がEuclidさんです。

f:id:sarugorirag:20191118114131j:plain — Wikipediaから拝借しました。Euclid statue(@Oxford University)

紀元前を生きた天才数学者で、特に幾何学・力学(物理)においてはEuclidさんが全ての基礎を作ったといっても過言ではないでしょう。

それでは誰が作ったのかも分かりましたし、ユークリッドの互除法（Euclid's algorithm）についてしっかりと学んでいきましょう！

1)最大公約数どうやって求める？(ユークリッドの互除法)

　最大公約数を求めるときはユークリッドの互除法を使います。やってることは単純で、ただ割り切れるまで割り算をするだけです。

例）2400と440の最大公約数を求める

③2400=440×5+200 (2400÷440=5 あまり 200)

②440=200×2+40 (440÷200=2 あまり40)

①200=40×5 (200÷40=5)←ワリキレタ！

割り切れた最後の商である40が最大公約数です。

このことを図で考えてみましょう！

f:id:sarugorirag:20191114013033p:plain

③2400は440と200で作ることができる。

②440は200と40で作ることができる。

①200は40で作ることができる。

(丸がついた番号は先ほどの割り算の番号に対応しています。)

　つまり、200は40で割り切れるし、200と40から作られる440も40で割り切れます。そして最後に440と200から作られる2400も40で割り切れることになります。

　よって、2400と440の最大公約数は40となります。

2)連分数を用いた最大公約数の求め方

実際に行う計算は1)と全く同じですが、こんな形でも考えられるよ　という参考程度にご覧ください。

例）2400と440の最大公約数を求める

割り切れるまで下のように分子が１の正則連分数を作っていきます。

　　※正則連分数とは連分数のうち、分子が全て１になるもののことです。

③ $\displaystyle\frac{440}{2400}=\frac{1}{\frac{2400}{440}}=\frac{1}{5+\frac{200}{440}}$

② $=\displaystyle\frac{1}{5+\frac{1}{\frac{440}{200}}}=\frac{1}{5+\frac{1}{2+\frac{40}{200}}}$

① $\displaystyle\frac{1}{5+\frac{1}{\frac{1}{2+\frac{1}{\frac{200}{40}}}}}=\frac{1}{5+\frac{1}{2+\frac{1}{5}}}$

小さくて見にくいですが①の最後で $\frac{200}{40}=\frac{1}{5}$ と割り切れたのでストップ！！

この割り切れる直前の分母が最大公約数になります。

1)の図と照らし合わせると繋がるかもしれませんね。約分するときは連分数を用いると半分遊びみたいで面白いです。

ちなみに正則連分数を経由すると、分母と分子の公約数が分かりにくい分数でも確実に約分することができます。

$\frac{440}{2400}$ を約分すると...

$\displaystyle\frac{440}{2400}=\frac{1}{5+\frac{1}{2+\frac{1}{5}}}=\frac{1}{5+\frac{5}{10+1}}=\frac{1}{5+\frac{5}{11}}=\frac{11}{55+5}=\frac{11}{60}$

　※このテクニックを必要とする問題が数検で出題されたことがあるらしいです。

3)不定方程式への応用

整数の単元でよく見る問題ですよね。ユークリッドの互助法の、最大の活躍の場かもしれません。

$1613x-504y=3$ を例に解いていきましょう。

　やり方としては(x,y)の組を1つ見つければ解けます。でも、実際はパッと見て見つからない方が多いと思いますので、その時に使うのが互除法です。

　下のように余りの部分にBやらCやらと新キャラが出てきますので、この新キャラが出る順番に注目すると後で楽になります。

一見ややこしく見えるかもしれませんが、焦らずゆっくり確認してみてください。

では実際に新キャラに注目しながら互除法をやっていきます。

① $1613(\cdots A)=504(\cdots B)×3+101(\cdots C)$

② $504(\cdots B)=101(\cdots C)×4+100(\cdots D)$

③ $101(\cdots C)=100(\cdots D)×1+1$

つまり、

④ $101(\cdots C)-100(\cdots D)×1=1$

ここから、１番新しいキャラを1つずつ古いキャラに交換していきます。

まず②を用いて１番新しい新キャラであるDをBとCで表します。

$101(\cdots C)-(504(\cdots B)-101(\cdots C)×4)×1=1$

Cをまとめます。

⑤ $101(\cdots C)×5-(504(\cdots B)×1=1$

次に、①を用いて⑤のCをAとBで表します。

$(1613(\cdots A)-504(\cdots B)×3)×5-(504(\cdots B)×1=1$

Bをまとめます。

⑥ $(1613(\cdots A)×5-504(\cdots B)×16=1$

これで式がAとBだけになったので終わりです。

ここまできたら、あとはウイニングランですね。

まだ「=1」ですので、「=3」にするために⑥の両辺を３倍します。

⑦ $1613×15-504×48=3$

$1613x-504y=3$ から⑦を引きます。

$1613x-504y-(1613×15-504×48)=3-3$

整理すると

$1613(x-15)-504(y-48)=0$

ここで1613と504は互いに素なので、整数kを用いて

$x-15=504k$

$y-48=1613k$

よって答えは

$\begin{cases}x=504k+15\\y=1613k+48\end{cases}\$ （kは任意の整数）

　注意する点としてはkが自然数とか実数ではなく整数であるという点と、文字はx,yを別々の文字で表すのではなく必ず1つの文字(今回はk)で表すということです。

　今回はユークリッドの互除法についての説明と、それを用いる不定方程式の解き方をまとめました。最初にも述べたように忘れやすい単元の1つだと思いますので、この記事を通してしっかり復習してもらいたいと思っています。

　今回の内容は以前出した#15.5の2020年度入試予想問題　でも登場していますので、再度解いてみるのもいいかと思います。この記事を読んで１問でも多くの問題が解けるようにしましょう。