ハク
問題わからなくて解説見たんだけど、ユークリッドの互除法ってなんで余りで割るの？
レイ
そこ疑問に思いますよね。じゃあ、今回はそこを解説していきましょう。
- 最大公約数って？
- なぜ余りを使うの？
- ユークリッドの互除法の流れ
を、できるだけイメージで解説していきます！
最大公約数って？
例えば、
24 と 18の最大公約数を考えます。
「両方を割れる数字」の中で、一番大きいものですね！
実際に探すと…
1、2、3、6があります。
この中で一番大きいのは
6なので、
24 と 18 の最大公約数は 6です！
でも毎回探すのは大変…
数字が大きいと、
「全部試す」のはかなり大変です💦
そこで使うのが、
ユークリッドの互除法です！
なぜ「余り」を使うの？
ここが一番重要です✨
まず、
24 ÷ 18 = 余り6になります。
つまり、
24 = 18 + 6ということ。
ブロックで考えてみる
24の中に18を入れると…
■■■■■■■■■■■■■■■■■■ 18
■■■■■■ 6余るこんな感じになります。
ここがポイント！
もし、
24 と 18 を同じ数で割れるなら、
余った6も同じ数で割れるはずなんです！
例えば「6」で割る
24 → 6 6 6 6
18 → 6 6 6
余り → 6全部きれいに割れます！
つまり…
24 と 18 の最大公約数
↓
18 と 6 の最大公約数に変えてOKなんです✨
数字が小さくなって楽ですよね！
さらに続ける
次は、
18 ÷ 6 = 余り0になります。
つまり、
6でぴったり割れた！ということ。
なので、
最大公約数は 6と分かります！
ユークリッドの互除法の流れ
実際の流れはこんな感じです。
24 と 18
↓
24 ÷ 18 = 余り6
↓
18 と 6 を調べる
↓
18 ÷ 6 = 余り0
↓
終了！最後に残った
6が最大公約数です✨
なぜ便利なの？
ユークリッドの互除法は、
数字をどんどん小さくできるので、
とても高速に最大公約数を求められます！
そのため、
- 基本情報技術者試験
- 応用情報
- プログラミング
- アルゴリズム問題
などで超頻出です✨
レイ
共通で割れる数は、余りも必ず割れるんです。
ハク
なるほど！だから数字を小さくしていけるんだ！
まとめ
✅ 最大公約数は「両方を割れる一番大きい数」
✅ 共通で割れる数は「余り」も割れる
✅ だから「余り」に変えても最大公約数は変わらない
✅ 数字を小さくして効率よく計算できる！
コメント