整数の性質の問題

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

「$a$ を $b$ で割った商を $q$、余りを $r$ とすると、$\gcd (a,b)=\gcd (b,r)$ である。」（$r=a-qb$ です。）

大きい方を小さい方で割り、「割る数」と「余り」の組に置き換えていきます。

$(1)$ $437$ を $323$ で割ると
$$437=323\times 1+114$$
よって $\gcd (437,323)=\gcd (323,114)$

$(2)$ $323$ を $114$ で割ると
$$323=114\times 2+95$$
よって $\gcd (323,114)=\gcd (114,95)$

$(3)$ $114$ を $95$ で割ると
$$114=95\times 1+19$$
よって $\gcd (114,95)=\gcd (95,19)$

$(4)$ $95$ を $19$ で割ると
$$95=19\times 5$$
余りが $0$ になったので、$95$ は $19$ で割り切れ、$\gcd (95,19)=19$ です。

以上より
$$\gcd (437,323)=\gcd (323,114)=\gcd (114,95)=\gcd (95,19)=19$$

（確認: $437=19\times 23$, $323=19\times 17$ で、$23$ と $17$ は互いに素なので、最大公約数は確かに $19$ です。）

答え: $19$

ユークリッドの互除法を用いる。
$437=323\times 1+114$
$323=114\times 2+95$
$114=95\times 1+19$
$95=19\times 5+0$
余りが $0$ になったときの割る数が最大公約数なので、最大公約数は $19$。
検算：$437=19\times 23$、$323=19\times 17$ であり、$23$ と $17$ は互いに素なので、最大公約数は $19$ で正しい。