“ユークリッドの互除法”の公式とその証明です！
ユークリッドの互除法
公式
ユークリッドの互除法・2つの自然数の最大公約数を求める方法
・自然数aとbについてaをbで割ったときの余りをrとしたとき、aとbの最大公約数はbとrの最大公約数に等しい。これを繰り返し余りが0となったときの除数がaとbの最大公約数。
証明
代入による証明
証明
2つの自然数aとb(a>b≧0)において、aをbで割ったときの商をq、あまりをrとすると
\(a=bq+r\) ①
またaとbの最大公約数をgとすると
\(a=a’g\) ②
\(b=b’g\) ③
と表せる。
①に②、③を代入すると
\(a’g=b’gq+r\)
⇒ \(r=g(a’-b’q)\)
\(a’-b’q\)は整数であるためｂとrは公約数gをもち、また①よりgより大きな公約数を持たないためbとrはgを最大公約数に持つ。
つまりaとbの最大公約数はbとrの最大公約数に等しい。
これを繰り返し行うことでユークリッドの互除法が成り立つ。
つまり
自然数aとbについてaをbで割ったときの余りをrとしたとき、aとbの最大公約数はbとrの最大公約数に等しい。これを繰り返し余りが0となったときの除数がaとbの最大公約数。
問題
Q
\(80\)と\(108\)の最大公約数を求めよ．
A
\(108\div80=1余り28\)
ユークリッドの互除法より
\(80\)と\(28\)の最大公約数と\(80\)と\(108\)の最大公約数は等しい．
\(80\div28=2余り24\)
以下同様に
\(28\div24=1余り4\)
\(24\div4=6余り0\)
よってユークリッドの互除法より
\(80\)と\(108\)の最大公約数は4となります．
まとめ
ユークリッドの互除法は高校数学ではあまり約に立つことは少ないかもしれませんが，大きい数字の最大公約数をより簡単に求めることができます．
