Euclidの互除法 関連問題
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
1529388と419832の最大公約数を求めよ。という問題に対して次のような解法が知られています。
(i) 大きい方の数を小さい方の数で割る。
1529388÷419832＝3あまり269892
(ii) (i)の割る数を(i)の余りで割る。
419832÷269892＝1あまり149980
(iii) (ii)の割る数を(ii)のあまりで割る。
269892÷149980＝1あまり119952
(iv) (iii)の割る数を(iii)のあまりで割る。
149980÷119952＝1あまり29980
(v) (iv)の割る数を(iv)のあまりで割る。
119952÷29980＝4あまり0
これで、1529388と419832の最大公約数が29988であることがわかります。
実際、
，
，
です。約数に大きな素数を含む場合、素因数分解が難しいことがありますが、上記の解法では容易に最大公約数を求めることができます。この解法を(ユークリッドの)互除法と言います。
2数a，b (
)があるとき、aをbで割って商がs，あまりがrだとします。
です。
です。 (＊)
次に、
なので、(＊)のaをbに，bをrにして、(＊)を繰り返します。
繰り返すにつれて、a，b，rは次第に小さくなり、有限回で
になります。
になったときのbが最大公約数です。
a，bの最大公約数をmとします。
，
となる互いに素な整数の組k，lが存在します。
より、
∴ 
は整数なので、rはmの倍数です。
なので、mはb，rの最大公約数です(mよりも大きな最大公約数があるとすれば、mはa，bの最大公約数になりません)。
(＊)を繰り返すと、各回で
であるため、(＊)のa，b，rはどんどん小さくなり、有限回(＊)を繰り返したところで最終回にmの倍数aを
で割り、割り切れるので
となります。
ユークリッドの互除法で157と68の最大公約数を求めてみます。
157÷68＝2あまり21 ･･･①
68÷21＝3あまり5 ･･･②
21÷5＝4あまり1 ･･･③
5÷1＝5あまり0
となり、最大公約数は1になります。つまり、157と68は互い素、ということです。
③より、
･･･④
②より、
，これを④に代入すると、
･･･⑤
①より、
，これを⑤に代入すると、
これより、不定方程式：
の特殊解を、
，
と求めることができます。
a，bが互いに素(
とします)なとき、不定方程式：
の特殊解を互除法を用いて求めることができます。
互除法を繰り返して、mをnで割ってあまりが1になったとき、商がsだとして、
，
ここで互除法の途中経過をm，nに順次代入してゆき、a，bが出てくるまで繰り返せば、
の形になったところで、特殊解
，
が得られます。
なお、互除法が面倒な場合、連分数展開、という簡便な方法が知られています。早大理工93年[1]に出題されましたが、
のように、連分数で表しながら、出てきた分数の逆数を作って分子を1にしてゆき、分子に1が出てくるまで続けます。この操作は互除法と同じものです。ここで、一番内側に出てきた
を除いた連分数を元に戻してゆきます。
このときに出てくる30と13が元の不定方程式の特殊解になっています。詳しくは、高木貞治著「初等整数論講義」p.129，p.130を参照してください。
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
数学基礎事項TOP 数学TOP TOPページに戻る
【広告】ここから広告です。ご覧の皆さまのご支援ご理解を賜りたく、よろしくお願いいたします。
【広告】広告はここまでです。
各問題の著作権は
出題大学に属します。©2005-2023(有)りるらる 苦学楽学塾 随時入会受付中！理系大学受験ネット塾苦学楽学塾(ご案内はこちら)ご入会は、
まず、こちらまでメールを
お送りください。