正解は「ウ」です。
ユークリッドの互除法は,「m を n で割った余り r を求め,n を新しい m,r を新しい n として,余りが 0 になるまで繰り返す」アルゴリズムです。余りが 0 になったとき,そのときの除数が最大公約数になります。
具体的に a=12,b=8 で追跡します。
- 方法 1:m=12,n=8 のとき r=12mod8=4。ループ 1 で r=0 なので n→m(m=8),r→n(n=4),r=8mod4=0。ループ 1 で r=0 となり終了します。このとき最大公約数 4 は n に入っています。
- 方法 2:m=12,n=8 のとき r=12mod8=4,n→m(m=8),r→n(n=4)で r=0。再びループ 2 で r=8mod4=0,n→m(m=4),r→n(n=0)となり終了します。このとき最大公約数 4 は m に入っています。
このように,方法 1 では割り算の結果をループの前後で n に残すため最大公約数は n に,方法 2 では除数 n を先に m へ移すため最大公約数は m に求まります。
よって,方法 1 は n,方法 2 は m となり,「ウ」が正解です。