ユークリッドの互除法を使って最大公約数を求める問題です。
ユークリッドの互除法に関する知識はユークリッドの互除法と一次不定方程式をご参照ください。
基本問題
1428と7038の最大公約数を求めなさい。
解き方
最大公約数の問題は、大体以下の3つを使いますね。
- 素因数分解
- ユークリッドの互除法
- 最小公倍数
最小公倍数は2数
の最大公約数を、最小公倍数をとしたときという性質がありますが、これを使った問題を意図しています。
解説
1428と7038の最大公約数を求めなさい。
今回はユークリッドの互除法の解説になります。
7038を1428で割った商と余りを求めます。
1つスライドし、1428を1326で割った商と余りを求めます。
1つスライドし、1326を102で割った商と余りを求めます。
割り切れたので、最大公約数はです。
ちなみに、逆にたどっていってみましょう。
終わりに
これだけだと少し退屈かもしれません。
ユークリッドの互除法はユークリッドの互除法の問題の解法でまた必要になります。
あわせてご確認ください。
