ユークリッドの互除法とは、2つの自然数の最大公約数を求めるためのアルゴリズムである。ユークリッドの互除法は、ユークリッドが古代ギリシャで発明したものとされており、現在でも広く使われている。
ユークリッドの互除法のアルゴリズムは以下のようになる。
- 2つの自然数a, bを選ぶ。
- aをbで割った余りrを求める。
- もしrが0ならば、bが最大公約数であるため、アルゴリズムを終了する。
- rが0でない場合、bをrで置き換え、2に戻る。
このアルゴリズムは、aとbの値の大小に関わらず、必ず最大公約数を求めることができる。また、アルゴリズムの実行回数は最大でもaとbの最大公約数の桁数分程度であり、非常に効率的である。
例えば、a=54, b=24とすると、以下のようにアルゴリズムを実行することができる。
- a=54, b=24
- 54を24で割った余りは6。
- 6が0でないので、bを6で置き換える。
- a=24, b=6
- 24を6で割った余りは0。
- 余りが0なので、b=6が最大公約数である。
よって、54と24の最大公約数は6となる。
ユークリッドの互除法は、最大公約数を求めるだけでなく、2つの自然数の公約数を全て求めることもできる。具体的には、ユークリッドの互除法の途中で求めた余りを用いて、以下のように公約数を求めることができる。
- 2つの自然数a, bを選ぶ。
- aをbで割った余りrを求める。
- もしrが0ならば、bが最大公約数であるため、アルゴリズムを終了する。
- rが0でない場合、bをrで置き換え、2に戻る。
- アルゴリズムを終了したら、bが最大公約数である。
- 最大公約数をdとした場合、aとbの公約数はdの約数である。また、aとbの公約数は、アルゴリズムを逆順に適用して得られる余りの列の最後の数の約数である。
例えば、a=54, b=24とすると、以下のようにアルゴリズムを実行することができる。
- a=54, b=24
- 54を24で割った余りは6。
- 6が0でないので、bを6で置き換える。
- a=24, b=6
- 24を6で割った余りは0。
- 余りが0なので、b=6が最大公約数である。
- 求めた余りの列は6, 0である。よって、aとbの公約数は6の約数である6, 3, 2, 1であり、アルゴリズムを逆順に適用することで、aとbの公約数を全て求めることができる。
ユークリッドの互除法は、最大公約数のほか、最小公倍数を求める際にも活用される。最小公倍数は、2つの自然数a, bの積を最大公約数で割ったものであるため、最大公約数が求まれば最小公倍数も簡単に求めることができる。
ユークリッドの互除法は、現代のコンピューターや電卓でも最大公約数を求める際に広く使用されている。また、これまでの例では2つの自然数を対象としていたが、3つ以上の自然数の最大公約数を求める場合にも応用が可能である。