問題プレビューID: a73be035

問 2

与えられた正の整数 $x_0$ , $x_1$ （ $x_0 > x_1$ ）の最大公約数を，次の手順で求める。 $x_0 = 175$ , $x_1 = 77$ の場合，手順 (2) は何回実行するか。ここで，“ $A \rightarrow B$ ”は， $A$ を $B$ に代入することを表す。

〔手順〕 (1) 2 $\rightarrow i$ (2) $x_{i-2}$ を $x_{i-1}$ で割った剰余 $\rightarrow x_i$ (3) $x_i = 0$ ならば $x_{i-1}$ を最大公約数として終了する。 (4) $i + 1 \rightarrow i$ として (2) に戻る。

解説

ユークリッドの互除法の手順を $x_0 = 175$ ， $x_1 = 77$ で追う。

$i = 2$ ： $x_2 = 175 \div 77$ の剰余 $= 21$
$i = 3$ ： $x_3 = 77 \div 21$ の剰余 $= 14$
$i = 4$ ： $x_4 = 21 \div 14$ の剰余 $= 7$
$i = 5$ ： $x_5 = 14 \div 7$ の剰余 $= 0$

$x_5 = 0$ となったので手順 (3) で終了し，最大公約数は $x_4 = 7$ である。手順 (2) を実行した回数は $i = 2, 3, 4, 5$ の 4 回である。

したがって，正解は「イ」である。