すみろぐ_Sumi-Log_ 数学の時間第1回『ユークリッドの互除法』

数学の時間第1回『ユークリッドの互除法』

ということで、始めてみます。
個人的に気になっていることをその回のテーマにして、色々考えてみたり。新課程になって入った"整数"や、"複素平面"という分野などにも考えてみようと思います。

最初は新課程によって新しく入った"ユークリッドの互除法"について。

ユークリッドの互除法とは？

まずは、Wikipediaによる説明を引用します。

ユークリッドの互除法（ユークリッドのごじょほう）は、2 つの自然数または整式の最大公約数を求める手法の一つである。

2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

新課程によってこのユークリッドの互除法が数学Aに入り、よく分からないまま演習問題を解く人が多いかと思います。それに、この説明を読んでも「？？？」となる人も少なからずいるのではないかな・・・？
2つの自然数or整式の最大公約数を求めて何が得するか、というのは後述。
後半については、結構わかりにくいので、単純に2つの自然数の最大公約数を求めるという例を出します。

と、その前に。任意の負でない整数a,b(b≠0)に対して、
a=bQ+R (0≦R<b)
となる(Q,R)がただ1組存在します。この時、aは「割られる数」、bは「割る数」と呼ばれています。
また、Qは「aをbで割った時の商」、Rは「aをbで割った時の余り」といいます。
この考え方は、整式などにも応用できます。数IIに収録されていますね。
特に整式の因数分解などの場合では、÷という記号は用いてはいけないと思います。
できるだけ分数で表したりする努力をしておくといいと思います。
では、例に移りましょう。

ユークリッドの互除法を用いて最大公約数を求めてみる

まず、どういう手順を踏めば2数の最大公約数(以下G.C.D.と略記します)を求められるか、を説明しましょう。
行う操作は、2数を比べて大きい方の数を、小さい方の数で割るだけです。
この時、無理に小数で求めてはいけません。先ほど示した、a=bQ+Rの形で表します。
すると、大きい数を小さい数で割った余りRが得られますが、この余りRと元の2数の小さい方の数の大小を比べて、大きい方の数を小さい方の数で割ります。
そうすると、さらに余りR'が得られます。同様の手順を繰り返し、大きい方の数が小さい方の数の倍数、すなわち余りが0になれば終了です。その時の割る数が2数のG.C.D.となります。

ということで、1023と1349のG.C.D.を求めてみます。
1349=1023×1+326
1023=326×3+45
326=45×7+11
45=11×4+1
11=1×11+0
ということで、1023と1349のG.C.D.は1です。実際に考えてみると、1023=3×11×31,1349=19×71なので、確かに1023と1349のG.C.D.が1であることが分かります。

じゃあどこで役に立つの？

ユークリッドの互除法は、基本的には不定方程式の解を求めるのに役立ちます。
ここでは、2952と1368を例にとります。ユークリッドの互除法を用いると、G.C.D.は72と求まります。これは自分で確認してみてください！
ところで、2952x+1368y=72という式があったとします。これを満たす組(x,y)はどうやって求めるでしょう？解法としては、定数項である72を消去するために、この式を満たす(x,y)を1組求めます。こんな感じですね。

こうすることで、(x-a)が1368の倍数、(y-b)が2952の倍数となって、一般解を求めることができる訳ですね。じゃあ、この(a,b)はどうやって求めるか。そこで出てくるのがユークリッドの互除法なのです。
ユークリッドの互除法を用いてG.C.D.=72を求める過程を利用すると、72は以下のように表せます。
72=1368-216×6
　=1368-(2952-1368×2)×6
　=1368×13+2952×(-6)
よって、(a,b)=(-6,13)であることがわかりますね。
数学を進めていく上では、不定方程式は避けては通れない道なので、解法の一つとして、この「ユークリッドの互除法を利用して、不定方程式の解の一つを求める」という方法を紹介しました。

また、分数を約分する時にもユークリッドの互除法を利用することもできます。1368/2952という分数を既約分数(これ以上約分できない分数)にしようとしたとき、1368と2952をそれぞれ素因数分解しようとしますよね。この時に、G.C.D.が分かっていればいい訳です。今回、G.C.D.=72で、1368=19×72,2952=41×72なので、
1368/2952=19/41
と既約分数の形に直すことができます。
整数問題に出会った時、もしかしたらこれを使うと最短ルートだったりするかもしれない時があるので、頭の片隅にでも置いておけば便利なんじゃないかなあという感じのツールだと思います。

新課程によって新しく入った分野について考える

旧課程(私たちが履修)→新課程(現在の高校一年生が履修)によって、数学の範囲は結構大きく変更がありました。
まず、数学IAの範囲が拡大。数Iには"データの分析(相関関数など)"が入ったり、数Aには確率に"条件付き確率"が旧数Cから移動し、完全に新しく、"作図"や"整数"が入りました。また、旧数Cが消滅した影響で、"行列"が完全に高校課程からなくなり、数IIIには"複素平面"や"2次曲線(極座標含む)"が入りました。さらに、発展扱いにされていた積分法の"曲線の長さ"も追加。
全体的に見ても、圧倒的に学ぶ範囲が拡大しています。
しかしデータ分析って入れる必要あったんでしょうかね？FOCUS GOLDなどを見てみたら、四分位数とか色々書いてありましたが、まだ私は熟読していないのでよく分かりませんゴメンナサイ・・・。

私は間違いなく2浪はできない身なので、さっさと受験終わらせたいのですが、こういう新課程について考えることも好きです。「これはいらんだろー」とか、「へえ！これが入ったのか！」とか、新課程に関して調べてみて、意外な発見をすると面白かったりするものです。

2年後のセンター試験は、テスト的なもので、こういう新課程からの分野も入っていて、選択式になっているのだろうなあという風に思いますが、数IIBには、第5・6問が情報処理的なものなので、それほど驚いてはいないですね。
今後受験のためにセンター試験を控える方もいると思いますが、気に病むことはないです。
しっかりおさえるところをおさえて、演習を重ねていくと、予想以上に点数が取れたりするものですよ！

ということで、第1回は終了です。自分が持っている問題集などで、色々演習を重ねて理解を深めてみてください。「この記事のここが分からない・・・」といった疑問点などがあれば、コメントか電子メールでどうぞ！可能な限りで回答しようと思っています。

関連記事