ユークリッドの互除法とは？ゆーくりっどのごじょほう
ユークリッドの互除法とは、余りを取る割り算だけで2つの正の整数の最大公約数を求めるアルゴリズム。「割られる数と割る数」の組を「割る数と余り」の組へ置き換える操作を繰り返し、余りが0になった時点で割る数として残っている値が最大公約数になる。
最終更新：2026-10-09
この語が出る過去問を解く →背景
最大公約数は両方を素因数分解すれば求まるが、桁数が増えると分解そのものが現実的な時間で終わらない。割り算の余りを取るだけで扱う数が急速に小さくなる性質を使えば、繰り返しの回数はごくわずかで済む。FEでは、繰り返し処理と条件分岐を読む練習題材として、擬似言語のトレース問題に繰り返し登場する。
具体例
48と18なら、48÷18＝2余り12、18÷12＝1余り6、12÷6＝2余り0となり、余りが0になった時点で割る数だった6が最大公約数。手計算でも3回で終わる。
試験での引っ掛け
求まるのは最大公約数であって最小公倍数ではない（最小公倍数は2数の積÷最大公約数）。繰り返しを止める条件は「余りが0になったとき」で、答えはそのときの余り（0）ではなく割る数のほうである。この取り違えが典型的な誤答になる。
関連用語
出た過去問
問題文で直接問われたものと、解説の中で触れられたものが含まれます。
出典：平成28年度 秋期 基本情報技術者試験 午前 問7（IPA）解説で登場
出典：平成29年度 春期 基本情報技術者試験 午前 問6（IPA）解説で登場
関数f(x, y)が次のとおり定義されているとき，f(775, 527)の値は幾らか。ここで，x mod yはxをyで割った余りを返す。 f(x, y): if…
正解：31
要点：剰余で再帰する関数はユークリッドの互除法＝最大公約数
この関数はユークリッドの互除法そのもので、最終的に2数の最大公約数を返します。実際にたどると775÷527の余りは248、527÷248の余りは31、248÷31は割り切れて余り0となり、yが0になった時点のx＝31が返ります。775=25×31、527=17×31なので、最大公約数が31であることとも一致します。
出典：平成31年度 春期 基本情報技術者試験 午前 問7（IPA）
次の流れ図は、2数A, Bの最大公約数を求めるユークリッドの互除法を、引き算の繰返しによって計算するものである。Aが876、Bが204のとき、何回の比較で処理は…
正解：11
要点：減算型互除法は等しくなるまでの比較回数を数える
大きい方から小さい方を引く操作を、両者が等しくなるまで繰り返す。876と204では、204を4回引いて60になり（比較4回）、次に60を204側から3回引いて24になり（比較7回目まで）、続いて60から24を2回引いて12（9回目まで）、24から12を引いて12（10回目）、最後に12と12が等しいと判定して終了する。よって比較の回数は11回となる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。