整数の性質の問題

ユークリッドの互除法では、次の性質をくり返し使います。

$a$ を $b$ で割った商を $q$、余りを $r$ とすると $a=bq+r$ であり、
$$\gcd (a,b)=\gcd (b,r)$$
が成り立ちます。

1 回目 $667$ を $437$ で割ると、
$$667=437\times 1+230$$
となります。よって $\gcd (667,437)=\gcd (437,230)$ です。

2 回目 $437$ を $230$ で割ると、
$$437=230\times 1+207$$
となります。よって $\gcd (437,230)=\gcd (230,207)$ です。

3 回目 $230$ を $207$ で割ると、
$$230=207\times 1+23$$
となります。よって $\gcd (230,207)=\gcd (207,23)$ です。

4 回目 $207$ を $23$ で割ると、
$$207=23\times 9$$
となり、割り切れます。したがって $\gcd (207,23)=23$ です。

以上より、
$$\gcd (667,437)=\gcd (437,230)=\gcd (230,207)=\gcd (207,23)=23$$
です。

（確かめ）$667=23\times 29$、$437=23\times 19$ であり、$29$ と $19$ は互いに素なので、最大公約数は $23$ です。

答え: $23$

ユークリッドの互除法を用いる。
$667=437\times 1+230$
$437=230\times 1+207$
$230=207\times 1+23$
$207=23\times 9+0$
余りが $0$ になったときの除数が最大公約数なので、最大公約数は $23$。
検算：$667=23\times 29$、$437=23\times 19$ で、$29$ と $19$ は互いに素なので、最大公約数は $23$ で正しい。