ユークリッドの互除法

だらだら前置き（急いでいる人は飛ばして下さい）

実を言うと私が現役だった頃と数学のカリキュラムが大幅に変わっていて、習っていない単元も多く（そのくせベクトルや数列がなくなった）、ユークリッドの互助法も知りませんでした。なので現在進行形で勉強しつつ、理解したことをまとめていきます。（需要あるのか？）

正直、今の数学教育ってテクニックの詰め込みばかりで、数学の一番の面白さ、分かる楽しさを感じられるのかな？と疑問に思ったりします。ここでは理解することを目的として解説してみます。（細かいミスがあっても目を瞑って下さい）

ユークリッドの互助法

WikipediaのGIFアニメを一分間ほどご覧下さい。あれが全てです。（終）

嘘です。でも、あのアニメが一番イメージしやすいと思うので是非見てみて下さい。

ここから例題です。適当に作ってみました。

整数の積で、2×3×5×7×11=2310 などとして作るだけなので簡単です。

公約数を持つ２つの整数、公約数を持たない（互いに素）２つの整数の二通り作れば例1、例2のような問題が出来るので是非やってみて下さい。（例2はよくばりすぎて後悔しました）

次に、ユークリッドの互助法を用いて一次不定方程式を解いてみます。

静止画だと分かりづらいな。動画にしたい。（するとは言ってない）

次に具体例を解いていきましょう。

単純作業なのですが、数字が大きくなると手順が増えて計算も煩雑になります。何のためにやっているか常に意識しておくことが大事。手順に振り回されないようにしましょう。（すごい大変だった）

問題を作るときは無理のない数を選びましょう。

ユークリッドの互助法を行ったり来たり（分割したり戻したり）することで一次不定方程式を解くなんて考えついた人天才ですね。

大変だったけど結構楽しめました。自分で問題作って解いてみるのお薦めです。