整数の性質の問題

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

「正の整数 $a,b$ について、$a$ を $b$ で割った商を $q$、余りを $r$ とすると、$a=bq+r$ であり、$a$ と $b$ の最大公約数は $b$ と $r$ の最大公約数に等しい。」

1 回目　$437$ を $323$ で割ると
$$437=323\times 1+114$$
よって、$437$ と $323$ の最大公約数は、$323$ と $114$ の最大公約数に等しい。

2 回目　$323$ を $114$ で割ると
$$323=114\times 2+95$$
よって、$323$ と $114$ の最大公約数は、$114$ と $95$ の最大公約数に等しい。

3 回目　$114$ を $95$ で割ると
$$114=95\times 1+19$$
よって、$114$ と $95$ の最大公約数は、$95$ と $19$ の最大公約数に等しい。

4 回目　$95$ を $19$ で割ると
$$95=19\times 5$$
となり、余りは $0$ である。したがって、$95$ と $19$ の最大公約数は $19$ である。

以上より、$437$ と $323$ の最大公約数は $19$ である。

（確かめ）$437=19\times 23$, $323=19\times 17$ であり、$23$ と $17$ は互いに素であるから、最大公約数は $19$ で正しい。

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