次に示すユークリッド互助法(方法1、方法2)で、正の整数a 、b の最大公約数は、それぞれm とn のどちらの変数に求まるか。
ここで、m mod n はm をn で割った余りを表す。
方法1
方法2
ア
m
m
イ
m
n
ウ
n
m
エ
n
n
答え ウ
【解説】
ユークリッドの互除法では、変数m とn でm mod n =0となったときの、n が最大公約数になる。
問題の流れ図(フローチャート)ではr =m mod n なので、r =0を計算したときのn が最大公約数になり、方法1の場合は、n であり、方法2の場合は、r =m mod n の計算のあとでr =0のチェックをする前にn →m を行っているのでm が最大公約数になる。(ウ)