の最大公約数をと表す.
定理.(ユークリッドの互除法)
を整数として,をで割った余りをとする.
このとき,.
教科書の証明はなんだか文章ばかりで難しかった覚えがある.
今ならできるだろうか…?
(証明)
をで割った商をとするとと表せる.
右辺をみるとの公約数はの約数となっており,
の公約数になっていることがわかる.
またと変形するとの公約数はの約数となっており,
の公約数になっていることがわかる.
つまりの公約数の集合との公約数の集合は等しいので,
最大公約数は等しい.(証明終)
あっさり解決できた.少しくらいは簡単な整数論が身についているようだ.
このユークリッドの互除法は使いかたが問題である.
例えばの最大公約数を求める場合は,「どんどんスライドさせて割っていく」のである.
(割り算の原理)
(割る数と余りで割り算する.以下繰り返す.)
(割り切れたら終了)
よって最大公約数はである.
ひとまずユークリッドの互除法の使いかたはいいだろう.
ところで上の証明を見ると,結局は次の問題に帰着される.
問.
を示せ.
証明はとすれば,上の証明となんら変わらない議論で示せる.
これがいわゆる,ユークリッドの互除法の原理と呼ばれるものである.