ユークリッドの互除法とは
- 商と余りの最大公約数は被除数と除数の最大公約数になるということ
- 上の性質を利用して下のような問題を解くことができる
(問題) 1071 と 1029 の最大公約数
- 1071 を 1029 で割った余りは 42
- 1029 を 42 で割った余りは 21 （なぜ上の行からこうなるかがわからない）
- 42 を 21 で割った余りは 0
- よって、最大公約数は21である。
42 = 21 x 2
覚え方
- 長方形の中に敷き詰められることのできる正方形を探すというのが感覚的に覚えやすそう。
https://suuhaji.com/euclid/
証明
被除数 = 除数 x 商 + 余り
- 除数と余りの両方を割り切ることできる数があると左辺の被除数も同じ数で割り切ることができる。
例
24 = 5 x 4 + 4
24, 4, 4は全て2で割ることができる。
- なので商と余りの最大公約数は被除数と除数の最大公約数になる。