おはようございます。
今日また諮問会議が開かれて残り5県の緊急事態宣言の解除をするかどうかが検討されます。報道を見る限りではすべて解除になる方向で話が進むようです。これで6月から学校が再開されます。
もう2020年も5か月、ほぼ半分過ぎようとしています。1、2月は受験であってないようなもので3月からは・・・なんて思っていたのに。
テレビを観ていたら紅白はリモート開催？なんてことが話題になっているし。もう半年したら2021年がやって来ちゃうんですね。
2021は受験を考えたらぜひ押さえておきたい数字です。（今年の2020と消費税は押さえていました。栄東で消費税の予想していた問題そのものが出た時はびっくりしました）
ということで2021と893の最大公約数を求める問題が出たらできますか？素因数分解ができるかどうかがポイントです。
2021と893のように公約数がすぐには見つからない場合の求め方を題材とした問題が過去に浅野中学で出題されています。
ユークリッドの互除法を題材とした問題です。
つまり4588と2109の最大公約数は37です。
塾では「割る数→割られる数」「あまり→割る数」へ入れ替えていって、最後に割り切れた時の「割る数」が最大公約数と習う？覚えさせられる？のかもしれませんね。
3と5のように互いに素な関係でも
5=3×1+2
3=2×1+1
2=1×2
と互いに素の場合は最大公約数は1と求められます。
そもそもなんでこれで求めることができるの？と思うかもしれませんが
上の入れ替えの式ではあまりがだんだん小さくなっていきます。
入れ替えの操作を繰り返していくといつかは割り切れるだろう、有限回で割り切れるだろうということを使っています。
この最後に割り切れた数が最大公約数ということです。
ではこの入れ替えでなんで求められるの？についてですが
a=bq+rという関係の式がある時に（aが割られる数、bが割る数、qが商、rがあまり）、gcdを最大公約数と表すとします。
m=gcd（a,b) n=gcd（b,r）とします。（
aとbはmの倍数 ⇒ a=bq+rからbとrはmの倍数となる ⇒ 逆にmはbとrの公約数
⇒ n=gcd（b,r）からbとr公約数mはbとrの最大公約数nの約数となる・・・①
⇒ mの倍数であるa,bはnの倍数とも言える ⇒ nはa,bの公約数
⇒ nはmの約数・・・② ⇒ ①②よりn=mが言える
⇒ gcd（a,b)＝gcd（b,r）が言えるので「割る数→割られる数」「あまり→割る数」への入れ替えが成立し（同値関係）、有限回繰り返すことで最大公約数を求めることができる
こんなアルゴリズムが行われているんです。
ちなみに2021と893の最大公約数は
2021=893×2+235
893=235×3+188
235=188×1+47
188=47×４
ということで最大公約数は47
2021は43×47と素因数分解できる数字でした。
これだけ押さえておいてもいいかもしれませんね。