ユークリッドの互除法とは？

ユークリッドの互除法の意味

2つの整数の最大公約数を効率よく求めるアルゴリズム。大きい方の数を小さい方の数で割った余りを求め、割る数と余りの組に対して同じ操作を余りが0になるまで繰り返すことで最大公約数を得る。

ユークリッドの互除法の具体例

48と18の最大公約数を求めるとき、48÷18＝2余り12、18÷12＝1余り6、12÷6＝2余り0となり、最後に割った数である6が最大公約数となる。

ユークリッドの互除法は試験でどう引っ掛けられる？

求まるのは最大公約数であって最小公倍数ではない（最小公倍数は2数の積÷最大公約数）。繰り返しの終了条件は「余りが0になったとき」で、答えはそのときの割る数。最後の余りそのものを答えにしないよう注意する。

ユークリッドの互除法と関連する用語

• アルゴリズム
• 再帰

ユークリッドの互除法が出た過去問

• 整数x，y（x＞y≧0）に対して，次のように定義された関数F(x,y)がある。F(231,15)の値は幾らか。ここで，x mod yはxをyで割った余りである。…

  正解：3

  要点：F(x,y)=F(y, x mod y)は互除法。答えは最大公約数

  この再帰関数はユークリッドの互除法そのもので、最終的に最大公約数を返す。実際に追うと231を15で割った余りは6、次に15を6で割った余りは3、次に6を3で割った余りは0となり、第2引数が0になった時点の第1引数3が値となる。231＝3×7×11、15＝3×5なので最大公約数3と一致する。

  出典：平成28年度 秋期 基本情報技術者試験 午前 問7（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であることとも一致します。

  出典：平成29年度 春期 基本情報技術者試験 午前 問6（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回となる。

  出典：令和1年度 春期 基本情報技術者試験 午前 問7（IPA）