ユークリッドの互除法とは？ゆーくりっどのごじょほう
ユークリッドの互除法とは、2数の最大公約数を、大きい方を小さい方で割った余りに置き換える操作の繰り返しで求める古典的アルゴリズム。アルゴリズムのトレースのほか、拡張版が公開鍵暗号の鍵生成に使われる。
最終更新：2026-10-07
この語が出る過去問を解く →具体例
gcd(1071,462) は 1071 mod 462＝147、462 mod 147＝21、147 mod 21＝0 となり21。計算量は O(log min(a,b)) で、両者を素因数分解して共通因数を探す方法より桁違いに速い。
試験での引っ掛け
引き算を繰り返す版と余りを使う版があり、前者は2数の差が大きいと極端に遅くなる。最小公倍数は a×b÷gcd で求まるが、先に掛けると桁あふれしやすいので a÷gcd×b の順に計算する。
関連用語
出た過去問
出典：平成29年度 春期 高度試験 午前Ⅰ 問3（IPA）解説で登場
次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x,y)はxをyで割った余りを返す。
正解：aとbの最大公約数
要点：ユークリッドの互除法は余りの繰返しで最大公約数を求める
xをyで割った余りをとり、yを新しいx、余りを新しいyとする操作を余りが0になるまで繰り返すのはユークリッドの互除法である。終了時のxには最後に割り切れたときの除数が入っており、これがaとbの最大公約数になる。例えばa=12、b=18なら計算を追うと6が残る。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。