ユークリッドの互除法は、2つの整数の最大公約数（GCD）を求めるためのアルゴリズムです。今回は、(1001, 286, 182, 154) と (30768, 10278, 4566, 2148, 588) の最大公約数を求める問題について詳しく解説します。計算過程を確認していきましょう。
ユークリッドの互除法とは？
ユークリッドの互除法は、2つの整数の最大公約数（GCD）を求める方法で、次の手順で進めます。
- 2つの整数を入れた後、余りが0になるまで割り算を繰り返します。
- 最後に余りが0になるとき、その時の商が最大公約数となります。
この方法を用いると、大きな数同士の最大公約数を効率的に求めることができます。
問題1：(1001, 286, 182, 154) の最大公約数
まず、(1001, 286, 182, 154) の最大公約数を求めるために、2つずつ順にユークリッドの互除法を適用します。
1001と286の最大公約数を求めます。
- 1001 ÷ 286 = 3 余り 143
- 286 ÷ 143 = 2 余り 0
よって、1001と286の最大公約数は143です。
次に143と182の最大公約数を求めます。
- 182 ÷ 143 = 1 余り 39
- 143 ÷ 39 = 3 余り 26
- 39 ÷ 26 = 1 余り 13
- 26 ÷ 13 = 2 余り 0
よって、143と182の最大公約数は13です。
次に13と154の最大公約数を求めます。
- 154 ÷ 13 = 11 余り 11
- 13 ÷ 11 = 1 余り 2
- 11 ÷ 2 = 5 余り 1
- 2 ÷ 1 = 2 余り 0
よって、13と154の最大公約数は1です。
したがって、(1001, 286, 182, 154) の最大公約数は1です。
問題2：(30768, 10278, 4566, 2148, 588) の最大公約数
次に、(30768, 10278, 4566, 2148, 588) の最大公約数を求めます。こちらも順に2つずつユークリッドの互除法を適用します。
30768と10278の最大公約数を求めます。
- 30768 ÷ 10278 = 2 余り 10212
- 10278 ÷ 10212 = 1 余り 66
- 10212 ÷ 66 = 154 余り 0
よって、30768と10278の最大公約数は66です。
次に66と4566の最大公約数を求めます。
- 4566 ÷ 66 = 69 余り 12
- 66 ÷ 12 = 5 余り 6
- 12 ÷ 6 = 2 余り 0
よって、66と4566の最大公約数は6です。
次に6と2148の最大公約数を求めます。
- 2148 ÷ 6 = 358 余り 0
よって、6と2148の最大公約数は6です。
次に6と588の最大公約数を求めます。
- 588 ÷ 6 = 98 余り 0
よって、6と588の最大公約数は6です。
したがって、(30768, 10278, 4566, 2148, 588) の最大公約数は6です。
まとめ
ユークリッドの互除法を使って、(1001, 286, 182, 154) の最大公約数は1、(30768, 10278, 4566, 2148, 588) の最大公約数は6と求まりました。計算過程を順を追って進めることで、どちらも正しい答えにたどり着きました。ユークリッドの互除法を用いると、大きな数でも効率よく最大公約数を求めることができるので、ぜひこの方法をマスターしましょう。
コメント