スマホオンライン家庭教師ライフです！
こんにちは！
今回は勉強のお話
ユークリッドの互除法の解説
「ユークリッドの互除法」について詳しく解説します！
高校数学Aで習うところですね
そもそもユークリッドの互除法とは
そもそもユークリッドの互除法とは
自然数a,bについて、aをbで割った余りをrとすると
aとbの最大公約数はbとrの最大公約数に等しい
この定理を使って最大公約数を求めていくことをいいます
例えば
「319と143の最大公約数を求めよ」
って言われたら面倒臭いですよね
そういう時にユークリッドの互除法を使うことで
ちょっと楽に解くことができるようになるんです
でもこの定理が分かりにくいですね
そういう時は実際の数に置き換えて考えてみましょう
実際の数で考えてみる
aを319、bを143にすると
余りのrは33になりますね
だからさっきの定理に置き換えてみると
319と143の最大公約数は143と33の最大公約数に等しい
ってことになりますね
で、ここからが互除法の本気
これを無限に続けることができるんです
319と143の最大公約数を求めるには
143と33の最大公約数を求めればいいってことですが、
この143と33をさらにさっきの定理のa,bに置き換えて考えられるんです
aを143、bを33にすると
余りのrは11になりますね
てことは
143と33の最大公約数は33と11の最大公約数に等しい
これが言えますね
そうしたら
319と143の最大公約数は143と33の最大公約数に等しくて、
143と33の最大公約数は33と11の最大公約数に等しい
ということになる
じゃあ319と143の最大公約数を求めるには、
結局33と11の最大公約数を求めればいいってことですね
33と11の最大公約数は11
だから319と143の最大公約数も11になる
こうやって、大きい数同士の最大公約数も
ユークリッドの互除法を使うと求められるようになるんです
すごいね！
ユークリッドの互除法を使って不定方程式を解く
ユークリッドの互除法は
最大公約数を求めるために使うのが基本ですが、
他の問題にも応用することができます
それが、「31x+17y=1」といった不定方程式
例えば、
「31x+17y=1の解を１つ求めよ」
という問題
普通は連立方程式になってるけど、
この問題は式が１つしかない
自力だとむずいですね
分からないものが２つ（xとy）あったら、
式も２つ必要になるので
こういう問題でユークリッドの互除法を使うことができます
ユークリッドの互除法を使えば、1を使って色々な数を表現できるようになる
ポイントは、
「31と17は最大公約数が1になる」
ということ
31と17を互除法で小さくしていくと、最後は1になるんです
逆に言えば、
1を31と17で表現できる
実際に解いてみる
どういうことやねん？って思いますよね
実際にやってみましょう
31と17を互除法で小さくしていきます
31=17•1+14（31と17の最大公約数は17と14の最大公約数に等しい）
17=14•1+3（17と14の最大公約数は14と3の最大公約数に等しい）
14=3•4+2（14と3の最大公約数は3と2の最大公約数に等しい）
3=2•1+1（3と2の最大公約数は2と1の最大公約数に等しい）
（何してるん？って思うかもしれませんがとりあえず続き読んでね！）
で、できた4つの式を変形します
3=2•1+1（2•1を移行して）
1=3−2•1・・・①
14=3•4+2（3•4を移行して）
2=14−3•4・・・②
17=14•1+3（14•1を移項して）
3=17−14•1・・・③
31=17•1+14（17•1を移項して）
14=31−17•1・・・④
はい、①〜④の４つの式ができましたね
これを使って、「1を31と17で表現します」
①の式1=3−2•1の2に、②を代入します
すると・・・
1=3−(14−3•4)•1
になりますね
整理すると・・・（整理の仕方は動画で！）
1=3•5+14•(−1)
更にこの式の3に③を代入します
すると
1=(17−14•1)•5+14(−1)
になる
整理して
1=14•(−6)+17•5
近づいてきましたね
これの14に④を代入しましょう
1=(31−17•1)•(−6)+17•5
整理して
1=17•11+31•(-6)
はい！1を17と31で表現できました！
変形すると
31•(−6)+17•11=1
これを31x+17y=1と比べると
そのままx=−6 y=11になりますね！
こうやって、ユークリッドの互除法を使って
方程式を解くこともできるようになるんです
まとめ
・ユークリッドの互除法は大きい数同士の最大公約数を求めることができる
・「互いに素である２つの数の最大公約数は1」ということを使えば1を色々な数で表現できるようになる
・なので、ユークリッドの互除法を使って不定方程式を解くこともできるようになる
質問等あったらコメントください！
コメント