ユークリッド互除法で最大公約数求められますか?苦手な人はチェック!
整数問題苦手な人でも
ユークリッド互除法で
最大公約数が求められる!
あなたは以下の事に当てはまってますか?
僕も受験時代、
ユークリッド互除法で
最大公約数を求める方法は
高1以来ずっと忘れていました。
このユークリッド互除法は
整数問題で最も使われる方法の
1つになってます。
これを見ているあなたは
ぜひともこの記事を読み進めて
使えるようになってください!
ユークリッド互除法の定理
定理は以上の画像になるのですが
具体的にどうなるか見ていきましょう。
例えば248と93について
となります。
このとき
248と93の最大公約数
93と62の最大公約数
これは一致するってことです。
まずは色んな数字で試してみましょう!
最大公約数の求め方
それでは具体的な例題で
最大公約数を求めてみます。
248と1829の最大公約数を求めよ。
最大公約数は素因数分解でも
求めることができますが、
大きい数の素因数分解はしんどいですね。
そんなときに
ユークリッド互除法が使えます。
となるので、
1829と93の最大公約数は243と93の最大公約数
243と93の最大公約数は93と62の最大公約数
93と62の最大公約数は62と31の最大公約数
よって求める数は、31
2つの整数をできる限り小さくしているんですね!
互除法を使った問題
さらに最大公約数の求め方を利用して
次の問題も解けるようになります。
例え文字が出てきても
同じように互除法が使えます。
解答を見てみましょう。
このように最大公約数の求め方を利用して抽象的な問題も解けるようになります!
最後に
いかがでしたか。
この記事でお伝えした
ユークリッド互除法の使い方は
とても大切な内容になります。
ですが数A以外で全く使わないので
意外と忘れがちなのです。
ここまで読んだあなたは
ぜひとも問題集で練習して下さい!
公式ライン限定!
『数学を実践レベルまで上げる勉強法』
を期間限定で無料配布中👇
数学で足を引っ張られてる人に向けて
今まで勉強してこなかった人でもできる
勉強法や計画の立て方をまとめました!
まずはボタンの記事を
ご覧ください(^^)