ユークリッドの互除法とは、2つの整数の最大公約数を見つけるための方法で、以下の手順で見つけます。
整数との最大公約数を見つけるには、
2.のように割る数を余りで割ることを繰り返し、余りがになったときの割る数がとの最大公約数となります。
- との大きい方を小さい方で割り、余りを求めます。
- かの割る数になった方をで割り、余りを求めます。
例としてとの最大公約数を求めてみます。
まずはを計算すると
となります。
次は割る数のを余りので割って
となります。
割る数を余りで割ることを繰り返すと
で割ったとき余りがになるのでとの最大公約数はであるとわかります。
おおまかな最大公約数が求められる仕組みは以下のようになります。
整数との最大公約数をとすると、
となります。
をで割ったとき、商が、余りがであったとすると
と書くことができ、より左辺がの倍数ならば右辺もの倍数でなければならないこと、がの倍数であることからもまたの倍数であることがわかります。
また、で割ったときの余りなのでとなります。
をで割ったとき、商が、余りがであったとすると
と書くことができ、より左辺がの倍数ならば右辺もの倍数でなければならないこと、がの倍数であることからもまたの倍数であることがわかります。
また、で割ったときの余りなのでとなります。
次にをで割ったときのことを考えると、商が、余りがであるとすると
となり、上記よりとはの倍数なので、もまたの倍数ということになります。
また、で割ったときの余りなのでとなります。
このことから互除法の手順を繰り返すと余りはの倍数かつ前の手順による割り算の余りより小さい(ただし、以上の)整数となるので、いずれ余りはになります。
回目の余りでになったとすると、このときの割る数は1つ前の手順での割り算での余りでこれが最大公約数となります。
ここで最大公約数以外で割り切れてしまうことはないのか?と思うかもしれませんが、最大公約数でしか割り切れないことは以下のように確かめることができます。
上記と同じような流れで整数との最大公約数をとして、をで割ったときの商が、余りがであったとするとより
となり、余りはの倍数、すなわちを約数に持つことがわかります。
このことからはの公約数であることがわかります。
このことからはの公約数であることがわかります。
次にとの最大公約数を以外の整数であると考えると、のように
と書くことができます。これをに代入すると
となり、はの約数でもあるから、もまたの公約数であることがわかります。
ここで、とについてであるとすると、はとの最大公約数であるにも関わらず、より大きいという公約数があるということになり矛盾します。
今度はであるとすると、はとの最大公約数であるにも関わらず、より大きいという公約数があるということになり矛盾します。
したがって、という仮定が間違っていることよりであり、はの最大公約数であるということがわかります。
この結論を互除法で登場したすべての割り算に対して適用すれば、であるを除くの最大公約数はなので、より大きい数で割り切れることはなく、またはの倍数なのでより小さい数はそもそも登場しないため、互除法で余りがになるのは必ず割る数がのときであることがわかります。
Share: