ユークリッドの互除法・最大公約数
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
互除法a=bq+rにおいて、aとbの公約数の集合とbとrの公約数の集合が完全に一致する、という事実がこのアルゴリズムを支えている。dがaとbを割るならr=a−bqも割り、逆にdがbとrを割るならa=bq+rも割る、という双方向の関係から、gcd(a,b)=gcd(b,r)が成り立つ。余りは操作のたびに必ず小さくなるので、有限回で0になり、そこで手前の値が最大公約数になる。
こんなときに使う
- 最大公約数を求める問題、または不定方程式の前提として互除法を使う
- 連続する整数（差が1）は互いに素であることを利用する
手順
- 1. 大きいほうを小さいほうで割り、商と余りを求める
- 2. 割る数と余りの組で同じ操作を繰り返す
- 3. 余りが0になったときの割る数が最大公約数
例題
gcd(126,98)を求めよ。
解答
- 126=98・1+28
- 98=28・3+14
- 28=14・2+0
- ∴ gcd(126,98)=14
別解・ほかの見方
- 互除法を逆にたどれば、ax+by=gcd(a,b)を満たす特殊解が構成できる（1次不定方程式の解法に直結）
落とし穴
- 余りが0になる直前の値ではなく、直後の割る数を最大公約数と勘違いする
なぜ大事か
gcdを動かす道具。連続整数の互いに素の議論で必ず使う
東大での出方
連続整数の互いに素の証明、1次不定方程式の解法で必ず使う基礎技術。
確認問題
- gcd(84,36)を互除法で求めよ
前提になるノード
このノードを前提にするノード
「整数」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。