横画面推奨!
モバイル機器の場合、数式が見切れる場合があります。

2022年8月21日

ユークリッドの互除法 最大公約数を求める方法

 ユークリッドの互除法とは、2つの整数の最大公約数を見つけるための方法で、以下の手順で見つけます。

整数ABの最大公約数を見つけるには、
  1.  ABの大きい方を小さい方で割り、余りr1を求めます。
  2.  ABの割る数になった方をr1で割り、余りr2を求めます。
2.のように割る数を余りで割ることを繰り返し、余りが0になったときの割る数がABの最大公約数となります。

 例として168792の最大公約数を求めてみます。
まずは792÷168を計算すると
792÷168=4 120
となります。

次は割る数の168を余りの120で割って
168÷120=1 48
となります。

割る数を余りで割ることを繰り返すと
120÷48=2 2448÷24=2 0
24で割ったとき余りが0になるので168792の最大公約数は24であるとわかります。

 おおまかな最大公約数が求められる仕組みは以下のようになります。
 整数ABの最大公約数をGとすると、
(1)A=Ga, B=Gb(a,b:)
となります。
ABで割ったとき、商がk1、余りがr1であったとすると
A=Bk1+r1
と書くことができ、(1)より左辺がGの倍数ならば右辺もGの倍数でなければならないこと、BGの倍数であることからr1もまたGの倍数であることがわかります。
また、Bで割ったときの余りなので0r1<|B|となります。
 次にBr1で割ったときのことを考えると、商がk2、余りがr2であるとすると
B=r1k2+r2
となり、上記よりBr1Gの倍数なので、r2もまたGの倍数ということになります。
また、r1で割ったときの余りなので0r2<r1となります。

 このことから互除法の手順を繰り返すと余りはGの倍数かつ前の手順による割り算の余りより小さい(ただし、0以上の)整数となるので、いずれ余りは0になります。
n回目の余りrn0になったとすると、このときの割る数は1つ前の手順での割り算での余りrn1でこれが最大公約数Gとなります。


 ここで最大公約数以外で割り切れてしまうことはないのか?と思うかもしれませんが、最大公約数でしか割り切れないことは以下のように確かめることができます。
 上記と同じような流れで整数ABの最大公約数をGとして、ABで割ったときの商がk、余りがrであったとすると(1)より
(*)A=Bk+rr=BkA=G(bka)
となり、余りrGの倍数、すなわちGを約数に持つことがわかります。
このことからGA,B,rの公約数であることがわかります。
 次にBrの最大公約数をG以外の整数Gであると考えると、(1)のように
B=Gb, r=Gr(b,r:)
と書くことができます。これを()に代入すると
A=Gbk+Gr=G(bk+r)
となり、GAの約数でもあるから、GもまたA,B,rの公約数であることがわかります。

ここで、GGについてG>Gであるとすると、GBrの最大公約数であるにも関わらず、より大きいGという公約数があるということになり矛盾します。
今度はG<Gであるとすると、GABの最大公約数であるにも関わらず、より大きいGという公約数があるということになり矛盾します。

したがって、GGという仮定が間違っていることよりG=Gであり、GA,B,rの最大公約数であるということがわかります。

 この結論を互除法で登場したすべての割り算に対して適用すれば、0であるrnを除くA,B,r1,r2,,rn1の最大公約数はGなので、Gより大きい数で割り切れることはなく、またr1,r2,,rn1Gの倍数なのでGより小さい数はそもそも登場しないため、互除法で余りが0になるのは必ず割る数rn1Gのときであることがわかります。
Share:
share
◎Amazonのアソシエイトとして、当サイト「数学について考えてみる」は適格販売により収入を得ています。
Powered by Blogger.

Blog Archive

PR

blogmura_pvcount
ブログランキング・にほんブログ村へ