ユークリッドの互除法 とは

ユークリッドの互除法とは

ユークリッドの互除法とは、2つの自然数の最大公約数を求めるための古典的なアルゴリズムです。この方法は、古代ギリシャの数学者ユークリッドによって「原論」に記述され、現代でも広く使われています。互除法は、数学的にシンプルでありながら非常に効率的な方法であり、2つの数を互いに割り続けることで最大公約数を求めます。どのような方法か見てみましょう。

2つの自然数 a, b ( a ≧ b )について、a を b で割った余りを r とすると、a と b の最大公約数は、b と r の最大公約数に等しい。

このことを利用して割り算を繰り返し、2つの自然数の最大公約数を求めます。操作を繰り返して最後に割り切れた時の「割る数」が求める最大公約数となります。

1. a を b で割り，余り r を求める
2. b を r で割り、余り r₁ を求める
3. r を r₁ で割り、余り r₂ を求める …

このプロセスを余りが0になるまで続け…

4. 余りが0になったときの割る数が a と b の最大公約数となる

最大公約数を求めてみよう

例えば、252と105の最大公約数を求める場合を考えます。

252 ÷ 105 = 2 余り 42
105 ÷ 42 = 2 余り 21
42 ÷ 21 = 2 余り 0

この結果、21が最大公約数であることがわかります。 この方法は単純で、特に大きな数でも計算が比較的容易であるため、コンピュータサイエンスや暗号理論など、さまざまな分野で広く応用されています。

由来となったユークリッドとはどんな人物？

現在の数学の礎となった『原論』の著者であるユークリッドはどのような人物だったのでしょうか？