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

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

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

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

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

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

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

え？　そんなのわかるの？

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

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

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

なら、\(b\)は消去しないで残しておくってことね。あと、3つ文字があるけど。もしかして、\(a, d\)って、どっちを代入しても同じことかな。だって、\(a, 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\)ってことまでわかっちゃう。

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

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

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

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

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

よし、じゃあ、次いこ！

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

？　よくわからないなぁ。

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

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

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

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

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

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

何で？

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

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

実験かぁ。あんまり考えたことなかったよ。やってみよ。
\(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になって、素数だ！

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

でもさ、素数がらみで”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整数の積は6の倍数なんだから、絶対3の倍数になるじゃん！

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

そうだね。じゃあ、これを因数分解して
$$(n-1)(n+3)(n-2) = 0$$
になるから、答えは、\(n=1, 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\)でも素数にならない。

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

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

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

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

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

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

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

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

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

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

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

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

これは、素数ー因数分解の繋がりで良さそう。
$$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\)みたいにするってことかな？　代入すると
$$(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=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\)は絶対奇数の素数だよ。

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

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

まず\(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}$$
って感じかな。

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

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

やっぱり、一番見やすい\(_{pq}C_{1}\)かな。これって要は\(pq\)だもんね。この形を見ると、最大公約数の候補は\(1, p, q, pq\)のいずれかってわかるけど、問題文から、\(p\)でも\(q\)でも、\(pq\)でもないってことがわかる。だから、どっかに、\(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\)についても同じ？

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

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

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

そうだねぇ。とりあえず、因数分解してみたくなるかな。
$$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番目のパターンだけを考えればいいね。

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\)でこれが最小値。

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

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

そうだねぇ。とりあえず、やってみたくなるのは代入かな。
$$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}\)の倍数だってことがわかるし、問題はここからだね。

え〜と、\(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\)について、題意が証明された。

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

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

よし、じゃあ、行こ！