ユークリッドの互除法とは？
ユークリッドの互除法とは、2数の最大公約数を、大きい方を小さい方で割った余りに置き換える操作の繰り返しで求める古典的アルゴリズム。応用情報では、アルゴリズムのトレース問題や、拡張版が公開鍵暗号の鍵生成に使われる例として出る。
応用情報技術者試験の過去問では1回出題されています。
ゆーくりっどのごじょほう
ユークリッドの互除法の意味
2数の最大公約数を、大きい方を小さい方で割った余りに置き換える操作の繰り返しで求める古典的アルゴリズム。応用情報では、アルゴリズムのトレース問題や、拡張版が公開鍵暗号の鍵生成に使われる例として出る。
ユークリッドの互除法の具体例
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 の順に計算する。
ユークリッドの互除法と関連する用語
ユークリッドの互除法が出た過去問
次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x,y)はxをyで割った余りを返す。
正解：aとbの最大公約数
要点：剰余を繰り返して余り0で止める処理は最大公約数を求める
xをyで割った余りをtとし、x←y、y←tを繰り返してy=0で止める処理は、ユークリッドの互除法そのものである。終了時のxには、a と b の最大公約数が残る。
出典：平成29年度 春期 応用情報技術者試験 午前 問6（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。