こんにちは。horyです。
整数分野に「ユーグリッドの互除法」というものがあります。
私の個人的な考えになるのですが、原理を理解せずに用いている人が多いように感じます。
今回はユーグリッドの互除法の原理とともに、互除法を使った問題について記事に簡単にまとめました。
必要なら約数や倍数についてまとめた以下の式を読んでみてください。
ユーグリッドの互除法の原理
以下はユーグリッドの互除法の原理に関する問題です。
できなくても構いません。
問題の条件と方針
まずは、問題の条件を書き出してみます
方針としては「集合の一致」を用います。
- 集合X=｛AとBの公約数全体｝
- 集合Y=｛BとRの公約数全体｝
「XがYに属している」ことと「YがXに属している」ことを示せれば勝ちです。
集合についての記事はこちらにも書かれているので詳しいことを知りたい人はこちらの記事も併せて読んでみてください。
「XがYに属している（X⊂Y）の証明
正の整数cが集合Xに属すと考えます(c∈X)
(cはAとBの任意の公約数の一つ)
①に代入します。
上の形で表せるためcは集合Yの要素です。
(cはBとRの任意の公約数の一つ)
cは任意の公約数なので、「X⊂Y」が成立しました。
「YがXに属している（Y⊂X）の証明
正の整数dがYに属すと考えます(d∈Y)
(dはBとRの任意の公約数の一つ)
①に代入します。
上の形で表せるためdは集合Xの要素です。
(dはAとBの任意の公約数の一つ)
以上より、「X⊂Y」∧「Y⊂Y」が示されたので示せました。
これを応用して問題を解いていきます。
問題1 原理の応用
互除法の原理を応用した問題です。
普通に求めてもいいですが、大変なので原理を利用してみましょう。
原理を何回も使うと・・・
以上より、527と403の最大公約数は31です。
問題2_整数の組を求める
以下は整数の組を求める問題です。互除法を利用する場合とそうでない場合があります。
- （１）解を簡単に思いつく・・・そのまま利用
- （２）解を見つけるのがムズイ・・・互除法を利用
（１）解答・解説
この問題の解は簡単に思いつきます。
(x, y)=(8, 20)は一つの解です。そのまま利用します。
「①-②」を実行します
ここで、5と3は互いに素です(重要)。
(互いに素でないなら約分してください)
そのため、③が成り立つには・・・
- (x-8)・・・3の倍数
- (20-y)・・・5の倍数
kを整数とします。
（２）解答・解説
互除法を利用します。
「A=1293」・「B=640」と考えて原理を利用します。
「①～③」を「余り＝」の式に直します。
③’を変形すると…
これにより整数解の一つを求めることができました。
後は、（１）と同様に解くだけです。
ちなみに、1293と640が互いに素かどうかですが、原理を利用すれば互いに素であることが分かります。
