数学A

意外と忘れがち!ユークリッド互除法で最大公約数を簡単に求められる!

投稿日:2020年12月16日 更新日:

整数問題苦手な人でも

ユークリッド互除法で

最大公約数が求められる!

 

あなたは以下の事に当てはまってますか?

  • ユークリッド互除法の使い方が分からない
  • 最大公約数の求め方を忘れてる
  • 整数問題全般が苦手

 

 

 

私も受験時代、

ユークリッド互除法で

最大公約数を求める方法は

高1以来ずっと忘れていました。

 

このユークリッド互除法は

整数問題で最も使われる方法の

1つになってます。

 

これを見ているあなたは

ぜひともこの記事を読み進めて

使えるようになってください!

 




ユークリッド互除法の定理

定理は以上の画像になるのですが

具体的にどうなるか見ていきましょう。

 

例えば$248$と$93$について

$248=93\cdot2+62$

$93=62\cdot1+31$

となります。

 

このとき

$248$と$93$の最大公約数

$93$と$62$の最大公約数

これは一致するってことです。

 

avatar

まずはどうなっているのか確認しましょう!

 

最大公約数の求め方

 

それでは具体的な例題で

最大公約数を求めてみます。

 

例題

$248$と$1829$の最大公約数を求めよ。

 

 

 

最大公約数は素因数分解でも

求めることができますが、

大きい数の素因数分解はしんどいですね。

 

そんなときに

ユークリッド互除法が使えます。

 

解答

$1829=248\cdot7+93$

$248=93\cdot2+62$

$93=62\cdot1+31$

$62=31\cdot2$

となるので、

1829と93の最大公約数は243と93の最大公約数

243と93の最大公約数は93と62の最大公約数

93と62の最大公約数は62と31の最大公約数

よって求める数は、31

 

 

 

avatar

考える2つの整数をできる限り小さくしていきます。

 





 

互除法を使った問題

 

さらに最大公約数の求め方を利用して

次の問題も解けるようになります。

 

例題

$2n+17$と$3n+18$の最大公約数が$5$となるような最小の自然数を求めよ。

 

 

 

例え文字が出てきても

同じように互除法が使えます。

 

解答を見てみましょう。

解答

$3n+18=(2n+17)\cdot1+(n+1)$

$2n+17=(n+1)\cdot2+15$

となるので、

$3n+18$と$2n+17$の最大公約数は

$n+1$と$15$の最大公約数と等しい.

よって$n+1$と$15$の最大公約数が$5$となるには

$n+1=5$

となるときが最小の自然数$n$になるので、

$n=4$

 

avatar

このように最大公約数の求め方を利用して抽象的な問題も解けるようになります!

 

最後に

いかがでしたか。

 

この記事でお伝えした

ユークリッド互除法の使い方は

とても大切な内容になります。

 

ですが数A以外で全く使わないので

意外と忘れがちなのです。

 

ここまで読んだあなたは

ぜひとも問題集で練習して下さい!

 

 

 

 

 

-数学A

執筆者:

はじめまして。としです。

塾講師歴6年で培った経験から、数学が全くできない高校生が、試験で点を取るための勉強法を発信します。

「難問よりも基本に忠実」がモットー。

数学が原因で自分の行きたい学部の選択肢が狭まり、大学で本当にやりたいことができない人を無くすために発信していきます!

『Ctrl+D』
でお気に入り登録お願いします!