大学受験エリートのSuuです。
この記事では、スタディサプリの映像授業について、
「オススメの視聴法」
「授業のポイント」
などを紹介していきます。
今回は、
トップレベル数学ⅠAⅡB 第４６講
整数問題の攻め方 その２
です。
一見、講座で扱っている問題に統一性がないように感じるかもしれません。
ですが、
Euclidの互除法
がテーマの１つです。
背景にある統一的なテーマ・理論が理解できると本当は素晴らしいのですが、
ちょっとハードルが高そうです。
問題自体も、経験がないと扱いにくいものです。
まずは、「問題への対処」をしっかり習得しましょう。
Chapter1
問題（１）を扱うチャプターです。
堺先生が冒頭で「エウクリッド」と言っているのは、
ユークリッドのスペルが「Euclid」だからです。
（野暮な解説で、すみません。）
問題（１）はEuclidの互除法の原理を証明する問題です。
初見ではかなりハードルが高いので、
何度か繰り返し勉強する必要があります。
証明の骨子を、まとめておきましょう。
使う関係式は１つだけです。
a=bq+r
この式１つから、次の２つの情報を抜き出します。
㋐「aとbの公約数は、bとrの公約数になっている」
㋑「bとrの公約数は、aとbの公約数になっている」
㋐を示すときは、r=a-bqの形で議論するのがコツです。
最大公約数の「最大性」に注目して、
㋐から、G1≦G2
㋑から、G1≧G2
の２つを示すことで、G1＝G2を導きます。
G1＝G2
を証明するのに、
G1≦G2、G1≧G2
から攻めるのは、高校生だとあまり見ない方針かもしれませんね。
背景を少し説明します。
㋐「aとbの公約数は、bとrの公約数になっている」
㋑「bとrの公約数は、aとbの公約数になっている」
の２つがキーです。
㋐、㋑から、次のことが従います。
｛aとbの公約数全体｝=｛bとrの公約数全体｝
つまり、「最大公約数が等しい」だけでなく、
そもそも「すべての公約数」自体が一致します。
そういう意味で、この問題の証明は
「２つの集合が等しいことを示す」
という側面があります。
問題（３）で扱う内容ですが、
２つの集合がA、Bが等しいことを示すには
A⊂B、A⊃B
の２つを示すのがセオリーです。
こう考えると、２つの不等式から等号を示すやり方が自然だと言えます。
繰り返しですが、最後に大切なことを改めて書いておきます。
Euclidの互除法の原理は、
a=bq+r という関係式があるとき、
㋐「aとbの公約数は、bとrの公約数になっている」
㋑「bとrの公約数は、aとbの公約数になっている」
ことがキーとなり成り立つ。
証明を習得する際は、ここを意識して練習しましょう。
さてさて。
ここで終わると、問題（２）や問題（３）とEuclidの互除法の関わりが分かりませんね。
問題の背景について、補足をします。
１５分３０秒ごろから、Euclidの互除法の具体例を紹介してくれています。
計算結果を書きましょう。
（授業動画の板書では、3718と書くところが１か所3716になっているので、注意しましょう。）
① 4914 = 3718×1 +1196
② 3718= 1196×3 +130
③ 1196= 130×9 +26
④ 130 = 26×5
さて、この計算から4914と3718の最大公約数が26と分かります。
……で、終わってはもったいないんです。
実は、もっと重要な情報が隠れています。
問題（２）と似たような問題を考えます。
【問題】
4914x+3718y=26
を満たす整数x,yを１つ求めよう
この【問題】が、互除法の計算①～④からすでに解けています。
ちょっとやってみます。
26
=1196-130×9 (③より)
=1196-(3718-1196×3)×9 （②より）
=1196×28-3718×9
=(4914-3718×1)×28-3718×9 （①より）
=4914×28-3718×37
よって、
4914×28-3718×37=26
結果だけ見ると、どうしてそんな計算が浮かんだのか不思議な数が出てきます。
このように、
整数方程式 ab+by=c の答えを具体的に見つける方法
というのが、Euclidの互除法がもつ側面です。
この辺りを知っていると、この講座に共通するテーマが見えてきます。
Chapter2
問題（２）の解説です。
12x+5y=2199
の整数解をすべて問題です。
これも定番で、堺先生の解説が基本です。
まとめておきましょう。
㋐整数解(x,y)を１つ見つける
㋑１つ見つけた解から、すべての解を見つける
㋐でみつける解を特殊解、㋑で見つける解を一般解と言ったりするので、
特殊解から一般解へ
などと言われることがあります。
㋐の解を１つ見つけるところですが、
授業動画の最初のように、具体的に探す方法と、
後半で解説されるように
12x+5y=1 となる解を見つけて、両辺を2199倍する
方法の２つがあります。
知識として、両方とも知っておきましょう。
前半の方が、計算が簡単です。
そのため、通常は具体的に１つ探す方法でいいでしょう。
ただし、「そもそも、解があるかすら分からない」ような抽象的な状況では、
後半の方法が有効になります。
また、「すべての解」の表示は、最初に見つける具体的な解によって変わります。
堺先生はそこまで丁寧に解説しているので、しっかり理解おきましょう。
Chapter3
問題(3)の解説です。
この記事の中では先に触れてしまいましたが、
２つの集合がA、Bが等しいことを示すには
A⊂B、A⊃B
の２つを示すのが定番です。
また、授業で出てきた式変形について補足をします。
「3m+5n」を2×（整数）+7×（整数）に変形するところですが、
3=2×(-2)+7
5=2×(-1)+7
を使って、
3m+5n
={2×(-2)+7}m+{2×(-1)+7}n
=2(-2m-n)+7(m+n)
とした方がスマートです。
（逆の変形は、堺先生もこの方法でやっていましたね。）
変形の仕方が統一されておらず、混乱するかもしれませんので、
補足しておきました。
慣れない議論が多く、難しいと感じる人が多いかもしれません。
最初は大変なので、この記事の要点をおさえながら復習しましょう。
また、このチャプターの問題や議論、この記事の補足をよくよく理解すると、
次のことが分かります。
aとbが互いに素な整数のとき、
{ax+by|x,yは整数}={整数全体}
互いに素な整数の重要な性質なので、
トップレベルを目指す人は知っておくのもいいでしょう。
すみません、最後に１つ書かせて下さい。
ちょっと我慢できないのです……
＜n1,n2,……nk＞=＜GCD(n1,n2,……nk)＞
整数環ZはPID
意味は、大学に入って勉強しよう！