ユークリッドの互除法
ゾウ先生大きい数の最大公約数は、素因数分解よりも互除法のほうが速いことが多いよ。
30秒でつかむ
- aをbで割った余りをrとすると、aとbの最大公約数（新しいタブで開きます）はbとrの最大公約数に等しい。
- この割り算を余りが0になるまでくり返すと、最後に割った数がaとbの最大公約数になる。
- 互除法は、長さの異なる2本の線分から、共通に測れる最大の長さ（端の量）を探す考え方と同じである。
詳しく
公式
2つの整数a、b（a＞b）について、aをbで割った商をq、余りをrとすると、と表せる。このときaとbの最大公約数は、bとrの最大公約数に等しい。これをユークリッドの互除法という。
この関係を使い、余りが0になるまで「大きいほうを小さいほうで割って、割る数と余りの組に置きかえる」操作をくり返す。最後に割り切ったときの割る数が、もとの2数の最大公約数になる。
素因数分解（新しいタブで開きます）をしなくても最大公約数が求められるので、桁数の大きい数や、素因数分解がすぐにはできない数にも使える。
例題
例題：609と253の最大公約数を、ユークリッドの互除法で求めよう。
、、。、、。余りが0になったときの割る数は1なので、609と253の最大公約数は（互いに素）。
素因数分解だと、となる。共通する素因数がないことを確かめるのに大きい数の素因数分解が要るが、互除法なら割り算をくり返すだけで同じ結論に達する。
なぜそうなるか
「端の量」の考え方で確かめよう。長さ13の線分と長さ5の線分があるとき、短い5を使って長い13を測ると、5が2つ分で10、残り3（端の量）が測りきれずに残る。
次は5を3で測ると、3が1つで残り2。3を2で測ると2が1つで残り1。2を1で測ると残り0になり、最後に測った長さ1が、13と5を共通に測れる最大の長さになる。
のとき、aを割り切る数の集まりは、bとrの両方を割り切る数の集まりと一致する。だからaとbの最大公約数は、bとrの最大公約数に置きかえても変わらない。これをくり返して数を小さくしていき、最後に残った数が最大公約数だとわかる。
確認問題
確認問題（解答用紙）
スマホやタブレットで読み取ると、この問題をその場で解けます。
https://manazoo.com/math/euclidean-algorithm/?from=print#quiz
ユークリッドの互除法を使って、98と56の最大公約数を求めよ。
答え：＿＿＿＿＿＿＿＿＿＿＿＿
正解：14
98＝56×1＋42、56＝42×1＋14、42＝14×3＋0。余りが0になったときの割る数は14で、これが最大公約数（新しいタブで開きます）になる。ユークリッドの互除法を使って、119と34の最大公約数を求めよ。
答え：＿＿＿＿＿＿＿＿＿＿＿＿
正解：17
119＝34×3＋17、34＝17×2＋0。余りが0になったときの割る数は17で、これが最大公約数になる。261と195にユークリッドの互除法を使うとき、最初の割り算の余りはいくつか。
- ◯ 0
- ◯ 66
- ◯ 129
- ◯ 195
正解：66
261を195で割ると商1・余り66になる（261＝195×1＋66）。a＝bq＋r（商q・余りr）のとき、aとbの最大公約数と等しいものはどれか。
- ◯ qとrの最大公約数
- ◯ aとbの和の最大公約数
- ◯ bとrの最大公約数
- ◯ aとqの最大公約数
正解：bとrの最大公約数
ユークリッドの互除法の根拠は、aとbの最大公約数がbとrの最大公約数に等しいという関係である。
単元のポイント
- 互除法 余りで次々に割る操作をくり返して最大公約数を求める方法
- 端の量 2つの長さを割り切れるまで測っていったときの、共通に測れる最大の長さ
- 商 割り算で割り切れる回数を表す数