16688922

【ユークリッドの互除法】センター試験に役立つ最大公約数の求め方を解説!

はじめに

最大公約数を求める方法と聞かれてあなたは何と答えますか?
割り算を逆に書いて、小さい数からどんどん割っていくというのが真っ先に思い浮かぶと思います。

それでは、3355と2379の最大公約数を求めてみましょう。
このように大きい数の最大公約数を求めるとき、2でも割れない、3でも、5でも…と繰り返していくのは非常に時間がかかってしまいます。
そんな悩みを解決することができるのが「ユークリッドの互除法」という方法です。
どんなに大きな数字になっても少ない手順で最大公約数を求めることができる、とても便利な方法です。

この記事ではユークリッドの互除法を使った最大公約数の求め方、どうして最大公約数が求まるのかといった基本的なところから、センター試験で頻出の整数問題への応用まで解説します。

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

16716628

ユークリッドの互除法を知らないあなたも、まずは実際にどんな解き方をするのか見てみましょう。
実際に3355と2379の最大公約数を求めてみます。

16716242

このように
小さい数で大きい数を割る
あまりで割る数を割る
さらにあまりで割る数を割る…
と割り切れるまで続けます。そして最後の割る数が最大公約数となるのです。

ユークリッドの「互除法」とは「割り切れるまであまりで互いに割り(除法)続ける」という意味なんですね。

どうしてユークリッドの互除法で最大公約数が求まるのか:証明

16716629

どうしてユークリッドの互除法で最大公約数が求まるのでしょうか。
直感的に理解するのはなかなか難しい計算方法なので、正確に証明してみます。

ユークリッドの互除法を証明する前に、

16690931

ということを証明します。

16691210

ということがわかりました。
今証明したのは、
「割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する」
ということです。
言い換えると
「ユークリッドの互除法の操作を何回行っても、割られる数と割る数は一致する」
ということになります。
割り切れたときには、割る数が最大公約数なのは自明です。
よって、「割り切れるまでユークリッドの互除法を続けたときの最後の割る数が最大公約数である」ということが言えるのです。

16716272

ユークリッドの互除法の整数問題への応用

さて、ユークリッドの互除法は最大公約数を求める方法である、ということが感覚的にも理屈的にもわかっていただけたんじゃないかなと思います。

実は互除法にはもう1つ、整数問題の解を見つけるのに役立つという便利な使い方があるのです。
むしろ大学入試で頻出なのはこちらといっても良いでしょう。
まずは例を見てみましょう。

16691991

この問題を解くのにユークリッドの互除法は一見結びつかないかもしれません。
しかし、このax+by=1の形を解くのに実はユークリッドの互除法が大活躍するのです。

11と8について互除法で計算してみましょう。

16692002

このように互除法の計算式をそれぞれあまりについて整理してみます。(右側の式)
これをどんどん代入していくと、解が求まるようになっているのです。

16691934

これは与えられた式にx=3,y=-4を代入した式ですね。
よって、(x,y)=(3,-4)が求める答えになります。

今回のように、入試では
「ax+by=1を満たす整数(x,y)を求めよ」
といったような問題が出ることがあります。
その時には闇雲に解くのではなく、ユークリッドの互除法を有効活用しましょう!

Studyplus slogo@2x
学習記録をつけて勉強をもっと効率的に!
受験生の3人に1人が使っているStudyplusで、勉強が続く!
無料会員登録
Pc@2x

センター試験を解いてみよう

16716625

さて、それでは実際の入試問題でユークリッドの互除法がどのように使われるかを見てみましょう。

平成28年度センター試験数学1A第4問

16716478

独立行政法人大学入試センターHPより引用

92x+197y=1
は正に先ほど見たax+by=1の形ですね。
ユークリッドの互除法を用いて解いてみましょう。

16716531

これにより(x,y)=(15,-7)が題意を満たすことがわかりました。
しかし、この問題では「xの絶対値が最小のもの」という条件がついています。この解が本当に絶対値が最小かどうかを確かめるためには、一般解を求めなければいけません。
一般解を求めるためには、求めた一つの解を式から引いてみましょう

17195920

16716581

92×15+197×(-7)=1より92×150+197×(-70)=10ですね。
これを92x+197y=10から引くと、同様に解くことが出来ます。

16716603

16716604

最後に

今回はユークリッドの互除法の計算方法、証明、整数問題への応用と見てきました。
特にユークリッドの互除法を使った整数問題は、センター試験でもかなり高い頻度で出題される超重要科目です。
解を見つけるためのポイントは、「互いに割り続けることであまり1を作ること。」
ぜひユークリッドの互除法の使い方をマスターして、入試に役立ててください!

Studyplus slogo@2x
学習記録をつけて勉強をもっと効率的に!
受験生の3人に1人が使っているStudyplusで、勉強が続く!
無料会員登録
Pc@2x
この記事を書いた人
14720503
現役で東京大学理科2類に合格しました。いまは教養学部後期課程の4年生です。 得意科目は数学と化学、物理で、理系科目を中心に執筆していますので参考にしていただけると嬉しいです。

関連するカテゴリの人気記事

14930700?w=120

【文系大学受験】数学問題集おすすめ一覧〜センターから東大受験まで〜

14926323?w=120

東大生が教える数学3(数三)の勉強法とオススメ参考書3選!

15622206?w=120

因数分解とは?因数分解の公式と解き方を慶應生が教えます!【問題付き】

15702659?w=120

東大生が教える連立方程式の解き方〜中学数学からセンターまで〜

14702207?w=120

【大学受験 数学勉強法】理系の苦手を潰す!問題集・参考書の選び方も解説

16020625?w=120

三平方の定理が一瞬で理解できる!公式・証明から計算問題まで解説

関連するキーワード

スマホアプリで
学習管理をもっと便利に
Foot bt appstore
Foot bt googleplay