ユークリッドの互除法とは？ゆーくりっどのごじょほう
ユークリッドの互除法とは、二つの整数の最大公約数を、大きい方を小さい方で割った余りへ置き換える操作を、余りが0になるまで繰り返して求めるアルゴリズム。1回ごとに数が急速に小さくなるため計算量はO(log min(a,b))に収まり、素因数分解を経由して共通因数を探す方法とは桁違いの差がつく。
最終更新：2026-10-06
この語が出る過去問を解く →背景
最大公約数を素直に求めようとすれば両方を素因数分解することになるが、素因数分解は桁数が増えると現実的な時間では終わらない。割り算の余りに置き換えても最大公約数は変わるという性質を使えば、分解を経ずに答へ届く——大きな数を扱う場面で唯一実用になる道筋として、紀元前から同じ手順が使われ続けている。応用情報ではアルゴリズムのトレース問題として出るほか、拡張版が公開鍵暗号の鍵生成に使われる文脈でも触れられる。
具体例
gcd(1071,462)は、1071 mod 462＝147、462 mod 147＝21、147 mod 21＝0と進んで21が答になる。拡張ユークリッドの互除法はここに係数の追跡を加えたもので、RSAの鍵生成でeの逆元となる秘密鍵dを求める計算に使われ、OpenSSLなどの実装が内部で回している。
試験での引っ掛け
引き算を繰り返す版と余りを使う版があり、前者は2数の差が大きいと極端に反復回数が増える点が問われる。最小公倍数を求めるときも注意が必要で、a×b÷gcdは正しいが先に掛けると桁あふれしやすいため、a÷gcd×bの順に計算する。トレース問題では、割られる数と割る数の入れ替えを1回ごとに正しく行えているかが得点を分ける。
関連用語
出た過去問
出典：平成29年度 春期 応用情報技術者試験 午前 問6（IPA）解説で登場
次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x,y)はxをyで割った余りを返す。
正解：aとbの最大公約数
要点：剰余を繰り返して余り0で止める処理は最大公約数を求める
xをyで割った余りをtとし、x←y、y←tを繰り返してy=0で止める処理は、ユークリッドの互除法そのものである。終了時のxには、a と b の最大公約数が残る。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。