ユークリッドの互除法とは？
ゆーくりっどのごじょほう
ユークリッドの互除法とは、二つの整数の最大公約数を効率よく求めるための計算アルゴリズムです。
ユークリッドの互除法とは、二つの正の整数の最大公約数（GCD）を求める古典的なアルゴリズムです。古代ギリシャの数学者ユークリッドが著書『原論』に記したことでその名がつき、現在も広く利用されています。
アルゴリズムの仕組みは「二つの整数a、bがあるとき（a≧b）、aをbで割った余りをrとすると、aとbの最大公約数はbとrの最大公約数に等しい」という性質を繰り返し利用することです。余りが0になったとき、その時点の割る数が最大公約数となります。
具体的な手順は次のとおりです。
- aをbで割り余りrを求める
- rが0なら、bが最大公約数
- rが0でなければ、a←b、b←rとして手順1に戻る
たとえば252と105の最大公約数を求めると、252÷105＝2余り42、105÷42＝2余り21、42÷21＝2余り0となり、最大公約数は21です。この方法はひたすら割り算を繰り返すだけなので計算が速く、コンピュータサイエンスや暗号理論（RSA暗号など）においても基礎的な役割を果たしています。人類最古のアルゴリズムの一つであり、数学の美しさを示す例として教育の場でも重視されています。
使い方・例文
分数の約分をするとき、分子と分母の最大公約数をユークリッドの互除法で素早く求めてから割ると、手計算でも効率的に簡単な分数に直せます。
この用語をシェア
最終更新: