| 第１種情報処理技術者試験 |
1998年度 ＝ 平成10年度 |
午前 |
問10 |
次に示すユークリッドの互除法（方法１、方法２）で、正整数a、bの最大公約数は、mとnのどちらの変数に求まるか。ここで、m mod nはmをnで割った余りを表す。
|
| 方法１
| 方法２
|
| ア
| m
| m
|
| イ
| m
| n
|
| ウ
| n
| m
|
| エ
| n
| n
|
ウ
ユークリッドの互除法は、二つの整数を互いに除算して求めた余りが0になるまで繰り返すことによって、最大公約数を求める手法です。最大公約数は、余りが0になったときの除数です。
ア 方法１
余りrが0のときに、〔m mod n → r〕が行われているため、除数nが最大公約数です。
イ 方法２
余りrが0のとき、〔n → m〕と〔r → n〕が行われているため、除数mが最大公約数です。
したがって、正解はウです。
