Lrkby3xy7okgzl69k4r15neajgpjy1z2ojvo0q2em8mqxd3dlbvrvbwpwzmd458a

【ユークリッドの互除法】やり方&証明を解説!センター試験にも役立つ!

この記事は最終更新日から1年以上が経過しています。内容が古くなっているのでご注意ください。

はじめに

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

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

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

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

Nmavrqmo3pmedjbwr7z6alqd1znwyo6bz7knyx8xvlqk92eb4vrpgkj05gbjgm70?w=430

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

Gr1deekzx9vp658dz2xy71pdglajyypreabnnv0wqebrmwjeo3mrq4lgbkl6wz4l?w=430

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

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

ユークリッドの互除法の証明

Kllxrwjq1b5gpdmbylazdex0qvvknezbx6qyxr8zwlp7eogj923k6mnr4w1b9qmo?w=430

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

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

Qvg9wjvqwlmwkd1b8yrpz4jmne3ang5wjddovzp0r5xk7ldg2go96qebxjml6wzj?w=430

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

P9emmoxz9wr5q0zy8jalk42dg6wgym1e3wjynx7veo3vdpj1qlmmbpkreb7vrzqd?w=430

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

Nmavrqmo3pmedjbwr7z6alqd1znwyo6bzwbnyx8xvlqk92eb4vrpgkj05gbjgm70?w=430

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

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

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

Mldxd0dmwrz61ekpqxj7ble82lkgoamerbeoqpxz3v9odyb0w5agjn4vmrrn2pj3?w=430

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

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

Ode1kq7q1ypnmrkb06dz58xajx3my9gq64valvwg9gowvdelqbrz4pek2j4ygnrj?w=430

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

Xpdjjzmwzmqo19dlvrbl4kjnwgegnp7ewoka76b2xdprpayv805e3kxqjzolwg2l?w=430

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

今回のように、入試では
「ax+by=1を満たす整数(x,y)を求めよ」
といったような問題が出ることがあります。
ユークリッドの互除法のやり方さえわかっていれば、闇雲に当てはめる必要なく、計算で求めることができます。とても便利ですね!

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

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

Rwzpnb94wldr05endjpmyeowkxqpokzj19eyx7rjb28zzvqv3a6bmklgg1yj6z4v?w=430

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

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

Xpdjjzmwzmqo19dlvrbl4kjnwgegnp7m13wa76b2xdprpayv805e3kxqjzolwg2l?w=430

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

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

Qvg9wjvqwlmwkd1b8yrpz4jmne3ang571pqovzp0r5xk7ldg2go96qebxjml6wzj?w=430

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

Gwamrp8bzqy4jar9ldbemxg7p6e3nzkrm24yjkowzrvd0kl52qnv1wgmxp9empvw?w=430

R58e4ngwyndjzw2o4epq73bdz1vjyj5zqb8nmgeqk0x9rakbrl8m56lxvp6ev20m?w=430

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

Mldxd0dmwrz61ekpqxj7ble82lkgoam2zxroqpxz3v9odyb0w5agjn4vmrrn2pj3?w=430

0165gbexk9a28lmvq46dmwgn50kzo8qekrqaxglbbjzpreqv3wy7prd1ojojevb4?w=430

最後に

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

Studyplus slogo@2x
学習記録をつけて勉強をもっと効率的に!
受験生の3人に1人が使っているStudyplusで、勉強が続く!
無料会員登録
Pc@2x
この記事を書いた人
Mldxd0dmwrz61ekpqxj7ble82lkgoakxzd4nqpxz3v9odyb0w5agjn4vmrrn2pj3?w=72
Studyplus編集部です。あなたの勉強を後押しできるようなメディアにしていきたいという想いで運営しています。「役に立つ」と思ったら是非シェアをお願いいたします。

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

Pa2kwyap4zyke0exqmvwkw3qdrlvyrewg1ln85zmpdobgbj627xr1gn9ljz4l7vd?w=120

平方根(ルート)の計算や問題の解き方を完璧に理解しよう!

Ejy6kgm58bzjvqr9kbq4v1xrepl7nlde2gxnmwlg6oa2kyedgwdx0znjp3pq5jwr?w=120

因数分解のやり方・公式と解き方のコツ教えます!高校レベルまで対応!

Ode1kq7q1ypnmrkb06dz58xajx3my9gkjbqalvwg9gowvdelqbrz4pek2j4ygnrj?w=120

二次方程式の解の公式・因数分解による解き方を解説!解の公式をマスター

5e63jkknj6me2rzq4jgp0my5qg1wnnmo823adw7bxrokpbz89vaxledlv3erzvow?w=120

【直角三角形】辺の長さ・角度・合同条件などの公式を詳しく解説!

Gzpjdpzkep6oar3qnd2glbexbqymyp9gxppo5r9kmjj8dv4xwgw01v7lpz2klrv6?w=120

部分分数分解の公式とやり方を解説!

Rwzpnb94wldr05endjpmyeowkxqpokzaykkyx7rjb28zzvqv3a6bmklgg1yj6z4v?w=120

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

関連するキーワード

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