整数にまつわる問題を京大数学の入試問題を使って慣れる 〜京大数学良問から整数を学ぶ〜

スポンサーリンク
理系数学の世界
スポンサーリンク

整数問題に関する考察

まみ、整数の問題教えてよ。

いいけど、どんな問題?

問題っていうかさぁ、入試問題の整数関係の問題って、とらえどころがないっていうか、つかみどころがないじゃん。整数に関する公式を使えばいいってわけじゃないし、典型的な解き方ってないよね。物理とは違うよ。

ようこちゃん。整数問題の面白さを知らないんだねぇ。もったいない! それに、整数問題には立派な、典型的な枠組みがあるんだよ。だって、所詮入試に出てくるような問題なんだから。確かに、入試問題を超えたら、いまだに解かれていないような問題がたくさんあるけどさ。

え〜、じゃあ、それ教えてよ。そんな難しい整数問題なんて、興味ないし。

整数の問題にはさぁ、独特の「数学的キーワード」があるんだよ。そのキーワードと解法をうまく結びつけてやれば、少なくともつかみどころは、見つかると思うよ。それがわからないと、掴みのようのない、雲みたいな問題だけどね。ちょっと図で書いてみよっか。

黄色が整数問題のキーワード。青色がいろんな問題に対応できる解法、紫色が決まった問題に対して強力な解法だよ。

紫の位置関係は何か意味があるの?

あたしの経験からすると、キーワードに近い紫色の解法ほど役に立つかな。この関係から、キーワードをみて、ある程度どんな解法を選ぶかをイメージできるかも。あとは、問題を解きながら、整数問題の解き方を調べていこうよ。

 

京大数学に現れる整数問題

スポンサーリンク

2007年甲 第3問 ”4人”の共犯者を捕まえよ!

問題
\(p\)を3以上の素数とする。4個の整数\(a, b, c, d\)が次の3条件
\(a+b+c+d=0,\ ad-bc+p = 0,\ a\geq b\geq c\geq d\)
を満たすとき、\(a, b, c, d\)を\(p\)を用いて表せ。

キーワードは何でしょう?

素数、だね。あとは、整数の組み合わせ、というところかな。

うん。素数の問題は整数の組み合わせを決める時に、よく出てくるよ。何でかっていうと、素数って条件をつけるだけで、整数の組み合わせを劇的に絞り込むことができるからね。問題を作りやすいんだ。

じゃあ、目指すのは因数分解?

そうだね。因数分解したいけど、どれもできそうじゃないね。できそうなものがなかったら、作ればいいんじゃない?

最初の二つの方程式を使えばできそうだけど、、、でも、どの文字を消すのがいいの?

それがポイントだよ! まずさ、この問題を見て、どの文字が最初に決定できると思う?

え? そんなのわかるの?

だってさ、一度に全ての文字が決まるような方程式なんて、滅多にないんだから、一つずつ求めていくはずでしょ。だったら、最初に決定できる文字があるはずだよね。でも、\(a, b, c, d\)って、平等じゃないよね。

う〜ん。平等じゃないっていうのは、対称じゃないってこと?

そうそう。どんな問題でもさ、情報量が一番多いものから決定されていくよね。例えば、殺人事件で、複数の犯人がいたとしても、最初に捕まるのはもっとも情報を残してしまった人でしょ。そこから芋づる式に犯人が見つかっていくことがあるよね。数学も同じでさ、情報をたくさん残している文字からせめていきたいんだよ。じゃあ、情報量がもっとも多いのはどの文字?

え〜と、\(b\)と\(c\)かな。\(b, c\)はどっちも同じくらいの情報があると思うな。

あたしもそう思うよ。だって、すべての文字は方程式で1つずつ情報を残しているけど、最後の不等式では、\(b, c\)は2つの情報を残してるもんね。だからさ、\(b, c\)のどっちかを先に攻めるのがいいんだ。

でも、\(b, c\)のどっち?

それはどっちでもいいんだよ。だって、\(b ,c\)は同じ情報量を持っているんだから、どっちから攻めたって同じこと。じゃあ、\(b\)に狙いを定めるよ。

なら、\(b\)は消去しないで残しておくってことね。あと、3つ文字があるけど。もしかして、\(a, d\)って、どっちを代入しても同じことかな。だって、\(a, d\)って対称な形してるし。

ようこちゃん、鋭い。そうだよ。\(a, d\)のどっちを代入しても、形は違うけど、同じ情報しかくれないね。だから、どっちかでいいんだ。二番目の方程式を見てさ、\(ad-bc\)という形があるから、\(a, d\)のどちらか、それと、\(b, c\)のどちらかを代入したら、違う情報が手に入りそうな気がするよね。だから今回は、\(a, c\)を代入してみることにしよう。

代入した式
1. \((b+d)(c+d) = p\) (\(a = -b-c-d\)を代入した式)
2. \((a+b)(b+d) = -p\) (\(c = -a-b-d\)を代入した式)

これで、目的の式ができたね。右辺が素数というのが超強力な条件だよ。これが素数じゃなかったら、この問題、解けないからね。

なるほど、1の式と大小関係から\(b+d = p, c+d=1\)か、\(b+d = -1, c+d=-p\)になり、2の式から、\(a+b = 1, b+d=-p\)か、\(a+b = p, b+d=-1\)がわかるんだね。それで、1の式から出たものと2の式から出たものが矛盾しないようにするためには、\(b+d = -1\)しかないってことだね! これがわかると、
\(c+d = -p, a+b = p\)ってことまでわかっちゃう。

ね、面白いでしょ。今出てきた式をまとめよう。

新たにわかったこと
1. \(b+d = -1\)
2. \(c+d = -p\)
3. \(a+b = p\)

ようこちゃん、どの文字から攻めるか覚えてる?

忘れてないよ。\(b\)でしょ。じゃあ、3の式を使って\(b\)に関する不等式を作ってみる? そうすると、
$$b\leq\frac{p}{2}$$

そうだよね。じゃあ、次は1, 2を使ってみると
$$b-c = -1+p$$
になるけど、ここからどうしようか?

\(b\)を残したいんだから、\(c\)を消したいよね。方程式はめいっぱい使ってきたから、あとは不等式をつかうのかな。例えば、
$$c = b+1-p$$
として、\(c\leq d\)に代入してみよっかな。

いいね、いいね、そうすると?

$$b-p+1\leq d$$
が出てくるよ。で、今度は\(d\)が邪魔だから、\(b+d = -1\)を使って、、、
$$b\geq \frac{p}{2}-1$$
が出てくる。あれ、これって。

うんうん。\(b\)に関する不等式をまとめると、こうだよね。

bに関する不等式
$$\frac{p}{2}-1 \leq b \leq \frac{p}{2}$$

これを満たす整数\(b\)の値なんて、一つしかないでしょ?

え? あ、そうか。pは3以上の素数で、奇数なんだから
$$b = \frac{p-1}{2}$$
しかないんだ。ああ、そうすると、
$$b+d = -1$$
$$c+d = -p$$
$$a+b = p$$
なんだから、次々にわかっちゃうね!

ね? 芋づる式に全部わかっちゃうでしょ。

解答
$$a = \frac{p+1}{2}, b = \frac{p-1}{2}, c = \frac{-p+1}{2}, d = \frac{-p-1}{2}, $$

おお、結構面白いね。でも、解ければ、ね。

でも、閃きなんていらなかったでしょ。情報量が多いものから順にせめていっただけだもん。入試問題なんだから、誰でも解けるように作られているんだよ。整数の問題は、頭を鍛えるのに、とってもいいよ!

よし、じゃあ、次いこ!

2016年 第2問 素数から作られる素数”たち”

問題
素数\(p, q\)を用いて
$$p^{q}+q^{p}$$
と表される素数をすべて求めよ。

はい、来たよ、キーワード、素数!

今度は、何だろう? 因数分解じゃないよね。

因数分解じゃないときには、素数キーワードは、「整数の組」「存在証明」「あまり」なんかと繋がりが強いんだよ。特に、「素数」と「「整数の組」と「あまり」の結びつきは重要だよ。

? よくわからないなぁ。

すべての整数の組を探す時には、整数を「あまり」で分類することが多いんだ。例えば、すべての整数を\(n\)を整数として\(3n, 3n+1, 3n+2\)と置く、とかね。そうやっておいたあと、最終的に「素数」になるってことを使って絞り込んでいくんだよ。これはもう鉄板だね。

う〜ん、そうなんだね。でも因数分解できないと、ちょっと手がつけられないなぁ。何から始めればいいんだろう。

ようこちゃん! 整数の問題は、微分・積分の問題と違って「論理的な計算」よりも「論理的な言葉」で攻めたほうがいいんだよ。

論理的な言葉? どうやって?

誰でもすぐに考えついて、しかも確実な事実から明らかにするんだよ。数式をいじらないで、その数式からわかることを言葉にするんだ。

まず、pとqは両方とも偶数じゃないってこととか?

そうだよ! そういうことから始めるんだ。他には?

そうだねぇ、両方とも奇数じゃないな。

そうだよ。それ、すごい気づきだよ。

な〜んか、バカにしてない?

そ、そんなことないよ! だって、素数は……。

あ、ごめん、ちょっと待った。そっか、わかった。素数で偶数なものは2しかなくて、両方とも奇数でも偶数でもないってことは、どっちか一方が絶対2じゃなきゃいけないんだ。

そうなんだよ。だから、\(p=2\)と書くよ。
$$2^{q}+q^{2}$$
そうなると、あとは\(q\)が何かを考えればいいんだよね。素数がらみで肝になるのは、”3″だよ。

何で?

ほどほどにパターンが作れるからかな。2だと簡単すぎるし、5だとパターンが多すぎる。これが「入試問題」だってことを思い出すんだ。すべての素数を求めるような問題や、素数にならないことを証明する問題では、「3の倍数を作ってしまう」というのが鍵なんだ。

う〜んと、つまり、すべての整数を
$$3n, 3n+1, 3n+2$$
みたいに分けて、\(2^{q}+q^{2}\)が3の倍数になることを言えばいいわけ?

そっ! やってみよっか。

ん〜でも\(2^{q}\)を3で割った時のあまりはいくつだろう?

ようこちゃんに、もう一つのテクニックを教えちゃおう!
それは、「実験」。物理だけじゃなくって、数学でも実験すると有効なんだよ。\(q\)にいろんな値を入れて、試してみなよ。

実験かぁ。あんまり考えたことなかったよ。やってみよ。
\(2^{1}\)は3で割ると、2余る。
\(2^{2}\)は3で割ると、1余る。
\(2^{3}\)は3で割ると、2余る。
\(2^{4}\)は3で割ると、1余る。
\(2^{5}\)は3で割ると、2余る。
\(2^{6}\)は3で割ると、1余る。
へ〜、なんか繰り返しになってるんだ。

証明できる? ようこちゃん。

ちょっと待ってね。あ、簡単だよ。だって3で割って2余るものは\(3n+2\)ってかけて、これを2倍すると\(6n+4 = 3(2b+1)+1\)で1余る。3で割って1余るものは、\(3n+1\)って書けて、これを2倍すると\(3(2n)+2\)で2余る。だから繰り返しになるんだ。それで、\(q=1\)の時に2余るんだから、\(q\)が奇数だったら、絶対あまりは2だね。

その通り! じゃあ、最後までいくかな?

いつも通り、図にまとめてみよっかな。

うん。\(2^{q}+q^{2}\)は3より大きいから、素数になりうるのは、\(q\)が3の倍数になるときだけだね。\(q\)は素数なんだから、それって、\(q=3\)しかありえないね。その時は、確かに17になって、素数だ!

うん、完璧! だから、答えは17だね。どう? 面白くない? 整数。

確かに、推理みたいで、ちょっと面白いね。数学的な証拠を突きつけて、犯人を追い込んでいく、みないな感じ。

うん。なんか、そういう感じがするよね。

でもさ、素数がらみで”3″がポイントってホント? この問題だけじゃないの?

あ〜、疑ってるな。じゃあ、これ見てよ!

2018年 第2問 ”3″が重要なんだってば!

問題
\(n^{3}-7n+9\)が素数になるような整数nをすべて求めよ。

この数式、因数分解できそうだけど、できないんだよね〜。だから、素数、整数の組、存在証明、あまりっていうつながりで、やっぱり整数をあまりで分類して、素数性から、候補を限定していくって方針だね。

で、3が鍵なのよね?

そうだよ。京大の整数問題に限らないけど、特に、京大は3が鍵。

でも今回は\(3n, 3n+1, 3n+2\)を代入して計算って面倒だな。ちょっと工夫して\(3n, 3n+1, 3n-1\)としても面倒だなぁ。まぁでもやるか。

合同法っていう武器もあるけど、これくらいだったら計算してもいいじゃん。

は〜い。じゃあ、\(n=3n\)の時は、
$$27n^{3}-21n+9$$
で、3の倍数だね。\(n=3n+1\)の時は
$$27n^{3}+27n^{2}-12n+3$$
で、3の倍数だね。\(n=3n-1\)の時は
$$27n^{3}-27n^{2}-12n+15$$
で、3の倍数だね、、、って、すご!

ほらね、また”3″が当たりだったでしょ。ちなみに、こんな変形
$$n^{3}-n-6n+9 = (n-1)n(n+1)-6n+9$$
思いついたら、ようこちゃん、褒めてくれる?

あ、ずる〜い。計算する前にそれ見せてよ。連続する3整数の積は6の倍数なんだから、絶対3の倍数になるじゃん!

へへっ。とっておきの変形。まぁ、それはそうと、解答を続けようよ。

え? まだやるの? 3の倍数で素数なのは3しかないんだから
$$n^{3}-7n+9 = 3$$
を解けばいいだけよね?

一応さ、最後までやろうよ!

そうだね。じゃあ、これを因数分解して
$$(n-1)(n+3)(n-2) = 0$$
になるから、答えは、\(n=1, 2, -3\)だね。

せいか〜い。どう? 信じてくれた?

う〜ん。でもこれって両方とも最近の問題でしょ。昔は違うんじゃない?

むむ。今日は、疑り深いね、ようこちゃん。じゃあ、もう一つやる?

2006年前期 第4問 ”3″が大事。大事なことなので3問目。

問題
2以上の自然数\(n\)に対し、\(n\)と\(n^{2}+2\)がともに素数になるのは、\(n=3\)の場合に限ることを示せ。
*問題文を間違えていました。
\(n, n+2\)ではなく、正しくは\(n , n^{2}+2\)です。twitterで「双子素数が解決した」と書かれていて気づきました。

まず、”2″から攻めるけど、両方奇数だったら2の倍数にならないから絞り込めないね。

あ、じゃあ、やっぱり”3″なのか!

そうなんだよ! やっぱり”3″なんだよ! ミスタースリー!

……ようこです。ミスターじゃないし。

ようこちゃん、漫画のキャラクターだよ。

あ、そうなんだ。え〜と、問題としては、自然数\(n\)を\(3k, 3k-1, 3k-2\)に分けて考えればいいね。\(k\)は自然数ね。\(n=3k\)のとき、
$$n=3k, n^{2}+2 = 9k^{2}+2$$
だから、\(k=1\)の時だけOKだね。それ以外は\(n\)が素数じゃなくなっちゃう。
\(n=3k-1\)のとき
$$n=3k-1, n^{2}+2 = 9k^{2}+3 = 3(3k^{2}+1) > 3$$
だから、どんな自然数\(k\)でも素数にならない。
\(n=3k-2\)のとき
$$n=3k-2, n^{2}+2 = 9k^{2}+6k+6 = 3(3k^{2}+2k+2) > 3$$
だから、どんな自然数\(k\)でも素数にならない。

うん。こんな感じで、素数というキーワードで因数分解ができない時は、素数、整数の組、存在証明、あまりと連想して、あとは、”3″を鍵にして宝箱を開ければ、中には完答というお宝が入っているんだよ!

確かに! まみの言う通りかも。これが難関大学の整数問題のパターンなのかもね。しかも、数式をいじるだけじゃなくて、推理と実験で犯人を追い込むようなスリルも味わえる!

ね? ね? 整数問題って、面白いよね。

ちょっと、その気持ちもわかったような気がする。他にはどんな問題があるの?

いいね! ようこちゃん、やる気出てきた! 整数特化の問題じゃないけど、ちょっと小休止。こんな問題はどう? 論理的に攻めるという点では良い問題かも。

1986年前期 第1問 百聞は一見に如かず!

問題
すべては0ではない\(n\)個の実数\(a_{1}, a_{2}, \cdots\cdots, a_{n}\)があり、
$$a_{1}\leq a_{2}\leq \cdots\cdots \leq a_{n}$$
かつ
$$a_{1}+a_{2}+\cdots\cdots+a_{n} = 0$$
を満たすとき、
$$a_{1}+2a_{2}+\cdots\cdots+na_{n} \geq 0$$
が成り立つことを証明せよ。

これは、ちょっと数式を弄くり回したいような気持ちになるなぁ。

その気持ちをグッとこらえて、言葉で考えてみようよ。

言葉って言ってもなぁ。まず、\(a_{1}\)はマイナスで、\(a_{n}\)がプラスでしょ。それで、\(a_{1}\)から\(a_{n}\)のどっかで、符号がマイナスからプラスになるってことくらいかな。

良いねぇ、ようこちゃん。それが良い気づきだよ。気づいたことを形にするのも大事。\(a_{1}\)から\(a_{n}\)までで初めてプラスになるものを\(a_{k}\)とおいてみよっか。そうすると、\(a_{k-1}\)まではマイナスで、\(a_{k}\)からはプラスだってわかるよね。

うん。そこまではわかる。でも、どうやって証明しようかな。

ようこちゃん。ここで図だよ。証明したい数式をバラバラにして書いてみるんだ。バラバラっていうのは
\(a_{1}+\)
\(a_{2}+a_{2}+\)
\(a_{3}+a_{3}+a_{3}+\)
みたいにすることね。書いてみてよ!

え、う〜ん。まぁ、まみがいうなら、書いてみるけどね。

何か気づかないかな?

え、う〜ん。なんだろう。

よっと!

ちょっと、まみ、机の上に乗ってどうしたの?

Why do I stand up here? (どうして登ったと思う?)

(あ〜あれか。)To feel taller. (背を高くしたいから。)

No. I stand upon my desk to remind myself that we must constantly look at things in a different way. You see, the world looks very different form up here.(違う。あたしが机の上に乗ったのはね、あたしたちはいつも、違う見方で物事をみなきゃいけないんだってことを、思い出すためなんだ。ほら、ここから見ると、世界はまるで変わって見えるよ。)

はいはい。もうわかったから、降りて良いよ。”Dead Poets Society”だね。違った見方で見れば良いってことでしょ。……ああ! こういうこと?

うん、バッチリ! 横じゃなくて、縦に見るんだよ。そうすると、それぞれの列の和は絶対0以上だよね。だって
$$a_{1}+a_{2}+\cdots\cdots+a_{n} = 0$$
だし、それに、ようこちゃんが指摘したように、\(a_{k}\)までは全部負で、その負の数がなくなるんだから。

すごい。この図だけでこの問題解けてるじゃない。

うん。数式をいじるだけが数学じゃないってことだよ。言葉を使って論理的にせめていけば、必ず糸口は見つかるんだ。

良い例だね。次は、あたしが積極的に解いてみたいな。なんか、整数の問題出してよ。

おっけい。じゃあ、これはどう?

1995年前期 第2問 ”d”って逆立ちすると”p”だよね。

問題
\(a, b\)は\(a>b\)を満たす自然数とし、\(p, d\)を素数で\(p>2\)とする。このとき、\(a^{p}-b^{p}=d\)であるならば、\(d\)を\(2p\)で割った余りは1であることを示せ。

ごめん! また、素数だった。ようこちゃん、頑張って。

これは、素数ー因数分解の繋がりで良さそう。
$$a^{p}-b^{p} = (a-b)(a^{p-1}+a^{p-2}b+\cdots\cdots+b^{p-1})=d$$
で\(d\)が素数だよね。\(a-b\)の方が値が小さいから、\(a-b=1\)ということがわかるね。

ウンウン。慣れてきたね。

でもそこからがちょっと。\((a^{p-1}+a^{p-2}b+\cdots\cdots+b^{p-1})\)という式がとっても扱いづらいから、なかなか先に進まないなぁ。

そういう時はさぁ、最初の式に戻ってみれば良いんだよ。今一応\(a-b=1\)ってことがわかったよね。

え〜と、例えば\(a=b+1\)みたいにするってことかな? 代入すると
$$(b+1)^{p}-b^{p}$$
だけど。もしかして、展開しちゃう?

しちゃう。

$$1+_{p}C_{1}b+_{p}C_{2}b^{2}+\cdots\cdots_{p}C_{p-1}b^{p-1} = d$$
かな。それで、これを\(2p\)で割った時のあまりが1に慣れば良いんだから、あ、\(_{p}C_{1}b+_{p}C_{2}b^{2}+\cdots\cdots_{p}C_{p-1}b^{p-1} \)が\(2p\)の倍数になってくれれば嬉しいな。

そうそう! 証明の時には、こうなってくれると嬉しいなぁ、ということを見つければ良いんだよ。そうすれば、次の行動のとっかかりになるからね。あとはそれを証明するだけじゃん。

\(p\)の倍数なのは良いんじゃない? だって、\(p\)は素数なんだから、\(p-1\)以下のもので割り切れることはないよね。\(_{p}C_{r}\)の形をしている式って、ちゃんと書けば
$$_{p}C_{r} = \frac{p!}{(p-r)!r!}$$
だから、r=pじゃない限りは、分子に\(p\)が残るはず。だから、\(p\)の倍数なのはクリア。あとは、偶数だってことだけど。

うん。良い調子だね。

あれ? ていうか\(d\)は素数なんだから、
$$1+_{p}C_{1}b+_{p}C_{2}b^{2}+\cdots\cdots_{p}C_{p-1}b^{p-1} = d$$
$$_{p}C_{1}b+_{p}C_{2}b^{2}+\cdots\cdots_{p}C_{p-1}b^{p-1} = d-1$$
となって、\(d-1\)は偶数じゃない?

ほんとうに? \(d\)は素数だけど、”奇数”じゃないよ!

あ、そうか。\(d=2\)ってこともあるのか、、、って、それはないでしょ。だって\(_{p}C_{1}b+_{p}C_{2}b^{2}+\cdots\cdots_{p}C_{p-1}b^{p-1}\)の最小値って、\(p=3, b=1\)の時で、7だもん。\(d\)は絶対奇数の素数だよ。

うん。それをちゃんと言っておけば、良いんだよ。そうすると、ようこちゃんのいう通り、\(_{p}C_{1}b+_{p}C_{2}b^{2}+\cdots\cdots_{p}C_{p-1}b^{p-1}\)は偶数だね。

ということは、この問題解けたんじゃない? 確かに
$$1+_{p}C_{1}b+_{p}C_{2}b^{2}+\cdots\cdots_{p}C_{p-1}b^{p-1} = d$$
は\(2p\)で割ると1余るよね。ん〜、意外と整数の問題は簡単なんだね。公式をたくさん覚える必要もないし、キーワードを追いながら、「これを示せたら嬉しい」→「証明」っていう流れで進めていけば、自然と解けてしまうって感じ。

素数がらみでいうと、例えばこんなのもあるよ。

2009年甲 第5問 ”p”を探せ。

問題
\(p\)を素数、\(n\)を整数とするとき、\((p^{n})!\)は\(p\)で何回割り切れるか?

この問題、とても有名な問題だよ。

え〜と、\(N!\)について、素因数\(n\)の個数は\(N\)を\(n\)で割った商、\(N\)を\(n^{2}\)で割った商、(N\)を\(n^{3}\)で割った商と続けていって、それらを足し合わせたものだったよね。この問題、これだけ知ってたら、できるんじゃ、、、。

 う〜ん、実はそうだよ。今の場合\(N=p^{n}\)だからね。

まず\(p\)で割ると、\(p^{n-1}\)
\(p^{2}\)で割ると、\(p^{n-2}\)
\(p^{3}\)で割ると、\(p^{n-3}\)
で、最終的に\(p^{n}\)で割ると、1って感じになるから、\((p^{n})!\)に含まれる\(p\)の個数は、等比数列の和の公式で
$$1+p+p^{2}+p^{3}+\cdots\cdots+p^{n-1} = \frac{p^{n}-1}{p-1}$$
って感じかな。

うん。正解。ちなみに、この問題で、なんで素数が重要だったかわかる?

う〜ん。素数じゃなかったら、めんどくさいよね。”素因数”じゃないとそもそも個数を求めるのが大変だよ。

うん。そういうことだね。素因数の問題だと、こんなのも面白いかも。

1997年前期 第2問 共通点なんてなかった……

問題
\(n\)が相異なる素数\(p, q\)の積、\(n=pq\)であるとき、\((n-1)\)個の積の数\(_{n}C_{k}\ (1\leq k \leq n-1)\)の最大公約数は1であることを示せ。

キーワードは”素数”と”最大公約数”だから、まみのいう通り、素因数が重要なのか。

そうだね。どこから手をつければいいと思う?

やっぱり、一番見やすい\(_{pq}C_{1}\)かな。これって要は\(pq\)だもんね。この形を見ると、最大公約数の候補は\(1, p, q, pq\)のいずれかってわかるけど、問題文から、\(p\)でも\(q\)でも、\(pq\)でもないってことがわかる。だから、どっかに、\(p\)の倍数ではない数、\(q\)の倍数ではない数があれば嬉しいな。

出たね! こうだったらいいな〜から始まる「”希望”発”証明”着」メソッド。ようこちゃんのいう通り、\(_{pq}C_{k}\ (1\leq k \leq pq-1)\)の中から、\(p\)の倍数ではない数と\(q\)の倍数ではない数を見つけちゃえばいいんだよ。見つけられるかな?

まぁ、まず考えたいのは、分母に\(p\)が現れるような式だから、\(_{pq}C_{p}\)かな。これって、全部書いてみると、
$$_{pq}C_{p} = \frac{pq\dot(pq-1)\dot(pq-2)\cdots\cdots(pq-(p-1))}{p!}$$
だよね。分子は\(pq\)から始めて項数が\(p\)個になるように1ずつ引いたものを掛け合わせればいいんだから。ああ! この分子って、素因数\(p\)が1個しかないじゃん。分母も!

ほんと? じゃあ、証明できる?

だってさ、
$$pq-1, pq-2, \cdots\cdots, pq-(p-1)$$
のどれも\(p\)の倍数じゃないもん。\(p\)の倍数-(\(p\)の倍数じゃないもの)は絶対、\(p\)の倍数にならないよ。あれ? ってことは\(q\)についても同じ?

うん。\(q\)も同じような形しているよね。
$$_{pq}C_{q} = \frac{pq\dot(pq-1)\dot(pq-2)\cdots\cdots(pq-(q-1))}{q!}$$
\(p\)を\(q\)に変えただけ。だから、やっぱり、分母・分子ともに素因数\(q\)は1個しかないよね。

ということは、こういうこと?
1. \(_{pq}C_{p}\)は\(p\)の倍数じゃない。
2. \(_{pq}C_{q}\)は\(q\)の倍数じゃない。
3. \(_{pq}C_{1} = pq\)はpとqだけの倍数。
だから、最大公約数は1。

そういうこと! 素数キーワードは素因数とも繋がりがあるんだよ。素数キーワードの問題をちょっとまとめてみよっか。

素数の問題
1. 素数ー因数分解の系統
与えられた式をみて、因数分解できれば、素数の性質から因数に整数を割り当てる。
2. 素数ー整数の組ー存在証明ーあまりの系統
因数分解できそうになく、整数の組や存在証明を要する問題は、整数をある数(D)の商とあまりで分類(特に”3″)。与えられた式がDの倍数になることを示して、整数の組を限定する。
3. その他
(例)素数ー素因数の個数
   

素数関連以外の問題も興味ある?

そうだねぇ、少しやってみたいかな。

じゃあ、これはどう? 

2014年 第5問 京大のお家芸、”3″の倍数での整数表現

問題
自然数\(a, b\)はどちらも3で割り切れないが、\(a^{3}+b^{3}\)は81で割り切れる。このような\(a, b\)の組(\(a, b\))のうち、\(a^{2}+b^{2}\)の値を最小にするものと、そのときの\(a^{2}+b^{2}\)の値を求めよ。

さて、出たよ、出たよ! ミスタースリー。

そんなテンション上がんないよ。

でも、この式を見たら、まずやりたくなることない?

そうだねぇ。とりあえず、因数分解してみたくなるかな。
$$a^{3}+b^{3} = (a+b)(a^{2}-ab+b^{2})$$
的な。これが81で割り切れるってことは、素因数3を4つも持っていないとダメなんだね。しかも、\(a, b\)ともに3の倍数ではないのかぁ。

ようこちゃん。次のシナリオは浮かんでいるけど、頭の中でちょっと嫌がってない? ま〜た、その計算するの? みたいな。

う〜ん。\(a=3n\pm1\)と\(b=3m\pm1\)を試すのかなぁとか思ってる。確かに、これ、さっきやったよね。今回は\(a, b\)が対称だから、
$$(a, b) = (3n-1, 3m-1), (3n-1, 3m+1), (3n+1, 3m+1)$$
の3パターン試せばいいんだけど。いやだなぁ。

ようこちゃん、ファイト! 合同法はまた今度やるからさ!

しょうがないなぁ。
1) \((a, b) = (3n-1, 3m-1)\)のときは
$$a^{3}+b^{3} = (3n+3m-2)(9m^{2}-9mn-3m-3n+2)$$
だから、3の倍数にならないから、ダメ。
2) \((a, b) = (3n-1, 3m+1)\)のときは
$$a^{3}+b^{3} = 9(n+m)(3m^{2}-3mn-3m-3n+1)$$
だから、とりあえず9の倍数だね。2番目のカッコは3の倍数にはならないから、\(n+m\)が9の倍数になる必要がある。
3) \((a, b) = (3n+1, 3m+1)\)のときは
$$a^{3}+b^{3} = (3n+3m+2)(9m^{2}-9mn+3m+3n+2)$$
だから、3の倍数にならない。

そうすると2番目のパターンだけを考えればいいね。

ようこちゃんのいう通り、\(n+m\)が9の倍数になれば、条件を満たせるね。

9の倍数だけど、\(a^{2}+b^{2}\)を最小にしたいんだから、\(n+m=9\)にすればいいのよね。そうすると\(a, b\)はそれぞれ、
$$a = 3n-1, b=-3n+28$$
にすればいいから、あとは\(a^{2}+b^{2}\)を計算すればいいね。

ようこちゃん、がんば!

計算は私の役割なのね。物理のときは、まみに計算してもらうからね!
$$f(n) = a^{2}+b^{2} = 18n^{2}-174n+785$$
で、重要なのは頂点だね。頂点は
$$n = \frac{174}{36} \simeq 4.83$$
だから、一番近い整数は5だね。\(n=5\)で最小になる。
つまり、\(a=14, b=13\)。\(a, b\)は対称だから、\(a=13, b=14\)のときもOK。このとき\(a^{2}+b^{2} = 275\)でこれが最小値。

大正解!

うん。整数の問題、なんかできるようになったかも。

じゃ、ようこちゃん、最後の問題!

え? まだやるの? 今日のまみ、気合い入りすぎじゃない?

いいから、いいから。それ!

1998年前期 第2問 \(2^{n}\)倍数のレシピ

問題
\(f(x) = x^{2}+7\)とおく。
(1) \(n\)は3以上の自然数で、ある自然数\(a\)に対して\(f(a)\)は\(2^{n}\)の倍数になっているとする。このとき\(f(a)\)と\(f(a+2^{n-1})\)のうち、少なくとも一方は\(2^{n+1}\)の倍数になっていることを示せ。
(2)任意の自然数\(n\)に対して\(f(a_{n})\)が\(2^{n}\)の倍数となるような自然数\(a_{n}\)が存在することを示せ。

今までと毛色が違うように見えるけど、内容は、易しめだよ。

そうだねぇ。とりあえず、やってみたくなるのは代入かな。
$$f(a) = a^{2}+7$$
$$f(a+2^{n-1}) = 2^{2n-2}+2^{n}\cdot a+7+a^{2} = 2^{n}(a+2^{n-2})+a^{2}+7$$
\(f(a)\)が\(2^{n}\)の倍数ということはわかっているから、これが\(2^{n+1}\)の倍数になっているかもしれないね。その場合はよくて、もしそうじゃない場合は\(f(a+2^{n-1})\)が\(2^{n+1}\)の倍数になっていればいいんだね。\(n\)が3以上だから、\(2^{n}(a+2^{n-2})\)は\(2^{n}\)の倍数だってことがわかるし、問題はここからだね。

ようこちゃん、\(f(a)\)の式を書き直すとどうなる?

え〜と、\(2^{n}\)の倍数で、\(2^{n+1}\)の倍数じゃないから、
$$a^{2}+7 = p\times2^{n}$$
ただし、\(p\)は奇数。かな。あ、そうか、まだ因数分解できるってこと?
$$f(a+2^{n-1}) = 2^{n}(a+2^{n-2})+a^{2}+7 = 2^{n}(a+p+2^{n-2})$$
だけど、括弧が偶数になっていればいいなぁ。\(p\)は奇数だから、\(a\)が奇数になっていればいいんだけど、、、って、\(f(a) = a^{2}+7\)が偶数なんだから、\(a\)は奇数に決まってるか。あ、じゃあ、\(f(a+2^{n-1})\)は\(2^{n+1}\)の倍数じゃん。証明終わり!

うん。頭に思い浮かんだことをやりながら、「”希望”発”証明”着」メソッドを使っていれば、自然と証明できちゃうね。

(2)は(1)を使えばできそう。\(f(a)=2^{n}\)の倍数になるような\(a, n\)を一つ見つけれくればいいんだよね。それ以降は、\(f(a)\)か\(f(a+2^{n-1})\)が\(2^{n+1}\)の倍数になってくれるからね。これを繰り返せば、どこまでも作れる。

うんうん、それで、見つかった?

そりゃ、\(a=1\)でしょ。8は\(2^{3}\)なんだから。これで、\(n=1, 2, 3\)はクリア。\(n\geq4\)からは、帰納法でできそう。

よし! じゃあ、最後の仕上げ、頼んだ、ようこちゃん。

おっけい。
\(n=4\)のとき、\(a = 1+2^{2} = 5\)とすれば、\(f(a) = 32\)となって成立。
\(n=k(k\geq4)\)のとき、\(f(a_{k}) = 2^{k}\)となる\(a_{k}\)が存在するとする。このとき(1)から、\(a_{k+1} = f(a_{k})\)または、\(a_{k+1} = f(a_{k}+2^{k-1})\)とすれば、\(f(a_{k+1})\)は\(2^{k+1}\)の倍数になる。よって、\(n=k+1\)のときも成立する。

数学的帰納法により\(n\geq 4\)以上の全ての自然数\(n\)についても成立する。
以上より、全ての自然数\(n\)について、題意が証明された。

うん! バッチリだね。

あ〜、疲れた! でも、整数の問題を練習できてよかった。

ちょっと休憩しよっか。あたしも疲れたぁ。

お疲れ様。今日はなんか奢っちゃおう!

え? ほんと? いつもはそんなこと言わないのに。じゃあ、いつもの喫茶店に行こ! ”よしこ”さんにも会いたいし。

よし、じゃあ、行こ!

コメント

タイトルとURLをコピーしました