読者です 読者をやめる 読者になる 読者になる

ユークリッドの互除法について

a,bの最大公約数を{\rm gcd}(a,b)と表す.

定理.(ユークリッドの互除法
a, b(a \geq b)を整数として,abで割った余りをrとする.
このとき,{\rm gcd}(a,b)={\rm gcd}(b,r)

教科書の証明はなんだか文章ばかりで難しかった覚えがある.
今ならできるだろうか…?

(証明)
abで割った商をqとするとa=bq+rと表せる.
右辺をみるとb,rの公約数はaの約数となっており,
a,bの公約数になっていることがわかる.
またr=a-bqと変形するとa,bの公約数はrの約数となっており,
b,rの公約数になっていることがわかる.
つまりa,bの公約数の集合とb,rの公約数の集合は等しいので,
最大公約数は等しい.(証明終)

あっさり解決できた.少しくらいは簡単な整数論が身についているようだ.
このユークリッドの互除法は使いかたが問題である.

例えば73, 17の最大公約数を求める場合は,「どんどんスライドさせて割っていく」のである.
73=17 \times 4 + 5(割り算の原理)
17=5 \times 3 + 2 (割る数と余りで割り算する.以下繰り返す.)
5=2 \times 2 + 1
2=2 \times 1(割り切れたら終了)
よって最大公約数は1である.

ひとまずユークリッドの互除法の使いかたはいいだろう.
ところで上の証明を見ると,結局は次の問題に帰着される.

問.
{\rm gcd}(a,b)={\rm gcd}(a-b,b)を示せ.

証明はa=(a-b)+bとすれば,上の証明となんら変わらない議論で示せる.
これがいわゆる,ユークリッドの互除法の原理と呼ばれるものである.