読者です 読者をやめる 読者になる 読者になる

アジマティクス

ここをこうするとおもしろい

京大理系数学の入試問題(2016)が面白いらしい

受験生のみなさん、お疲れ様です。どうでしたか?

2016年度京都大学理系数学の入試問題の大問②が、界隈でちょっとした話題になっているようです。

引用します。

素数 p, q を用いて

 p^q+q^p

と表される素数をすべて求めよ.

なるほど

なるほど。わたくし受験数学は詳しくないので、そっち畑の人からはこの問題がどう見えるのかはわかりませんが、確かにもし自分でこの問題を思いついたとしたら、しばらくはハマって考えてしまいそうな感じの興味深さがあります。たくさんあるのかな? 一つしかなかったりして? そんなの証明できるの? 気になります。

解説してみた

これ、私一人では手も足も出ませんでしたが、ネット上で解いてみてる人がたくさんいたのでカンニングしました。

したんですが、ちょっと前提として必要な知識が多すぎて、受験生向けにはいいかもしれないけど数学初心者にはちょっと辛いかなみたいな感じでしたので、僭越ながらわたくし必死こいて理解させていただいて、さらに初心者でも楽しめるように解説なんてさせていただこうかななんて思います。

自分で解きたい人にはネタバレですので注意です。読むのダルい人は下の方に大まかなまとめがあります。

偶奇で分けて考える

大まかな作戦としては「分けて考える」を何回か繰り返します。

まずp,qの偶奇を見てみます。整数や自然数の問題ではとりあえず偶奇を調べてみることは常套手段なのです。これは、問題を偶数の場合と奇数の場合とに「分けて考える」ということにほかなりません。

p,qの偶奇が一致しているとします。すると、p^qq^pは「偶数の偶数乗」か「奇数の奇数乗」ということになります。偶数の偶数乗は偶数、奇数の奇数乗は奇数です。加えて、偶数+偶数は偶数、奇数+奇数も偶数になります。必ず。どっちにしろ偶奇が同じものを足すと偶数になるよということです。

ということで、p,qの偶奇が一致しているとするとp^q+q^pが偶数になってしまいました。p^q+q^p素数になる場合を探してくれ、っていう問題だったので、これが偶数ではマズい(どんな素数p,qを選んでもp^q+q^p\gt2なので2の可能性はありません)。これはつまり「p,qの偶奇が一致している」という前提が間違っていたということであり、「p,qの偶奇は一致しない」ということがここからいえるのです。どちらかが偶数、どちらかが奇数。

偶数であるような素数2しかないので、どちらか片方は必ず2になります。元の問題はpqを入れ替えても成立するような問題であり、つまりどっちでもいいってことなのでq2ってことにします。するともう片方のp3以上の素数ということになります。

p3で割った余りで分けて考える

偶奇を調べる、というのは「2で割った余りで分けて考える(偶数は2で割った余りが0、奇数は1)」ということでしたが、今度は3で割った余りで分けて考えてみます。q2で確定しているので問題はpの方ですが、ひとまずpを「3の倍数でない数」だとしてみます。

3の倍数でない数」というのは式でいうと「3n\pm1(nは整数)」と表されます。3の倍数である「3n」は3で割ると整数になって割り切れますが、「3n\pm1」を3で割ると+1-1余ってしまうということです。

-1余る」というのは「2余る」ということと同じ(合同)です。3で割った数の世界において、-12は同じなんです。「3時間しかない時計において、2時間進むことと1時間戻ることは同じ」というとわかりやすいでしょうか。

f:id:motcho:20160229014953p:plain

3の倍数でない数「p」は、「3n\pm1」と表されるよ、という話でした。ここまでを元の式p^q+q^pに代入してみるとこうなります。

\left(3n\pm 1\right)^2+2^{3n\pm 1}

 全体を3で割った余りで分けて考える

こんどは、この式全体を3で割った余りを考えてみます(さっきのはpについて、3で割った余りを考えていたのでした。こんどは全体です)。

まず、前半部分\left(3n\pm 1\right)^2を普通に展開すると9n^2\pm 6n+1となります。これを3で割った余りを考えると、9n^2\pm 6nの部分は「3\left(3n^2\pm 2n\right)」とも書くことができ、カッコの中身は整数なので3の倍数になっていることがわかります。ということはつまり9n^2\pm 6n+1全体としては「3で割って1余る数」ということになります。

後半部分の2^{3n\pm 1}は、3で割った余りにおいては2-1は合同ということで、\left(-1\right)^{3n\pm 1}と書き換えることができます。指数である「3n\pm 1」はつまりpのことなので奇数でもあります。-1の奇数乗は-1です。よって\left(-1\right)^{3n\pm 1}すなわち2^{3n\pm 1}-1です。2^{3n\pm 1}3で割ると-1余るということです。

前半部分が1、後半部分が-1ということで、式の通りにこの二つを足すと0になります。「\left(3n\pm 1\right)^2+2^{3n\pm 1}3で割ると0余る」ということです。これはつまり「\left(3n\pm 1\right)^2+2^{3n\pm 1}3の倍数」ということを意味します。「\left(3n\pm 1\right)^2+2^{3n\pm 1}」とはすなわちp^q+q^pのことでした。代入したわけですから。「p^q+q^p3の倍数」という結果が出てきたことになります。

3の倍数であるような素数3しかない。しかし、p^q+q^p3になるような素数 p, qは存在しない(q2なんだからどうあがいても3を超えてしまう)。よって、前提が間違っていたということになる。前提とはなんだったかといえば、「p3の倍数でない」でした。ということで、「p3の倍数」がいえました。

 3の倍数であるような素数3以外にないので、pにあてはまる数は3しかない、ということが確定しました。

以上から、p^q+q^p素数になるのは、p=3,q=2のときの17だけであることがわかりました。証明終わり。

証明のおおまかなまとめ

  1. p,qの偶奇が一致するとすると全体が偶数になっちゃってヤバい
  2. p,qの偶奇は一致しない
  3. よってq2
  4. p3の倍数じゃないとすると全体が3の倍数になっちゃってヤバい
  5. p3の倍数
  6. よってp3
  7. よってp^q+q^p3^2+2^317のみ

もちろん、これが唯一の答えではなくほかにもいろいろやり方はあるでしょうが、他の解答もおおまかには2で割って3で割って...という道筋をたどっていることは共通しているだろうと思います。

はい

どうでしたか? そうですね。どっか間違ってたらご指摘ください。

問題の簡潔さ自体が美しいって人もいるだろうし、 解き方が楽しいって人もいるでしょう。人それぞれです。個人的には、まず17しか存在しないってところがなんか意外だし、その17しか存在しないって事実がここまでのことをやってバッチリ証明できちゃうっていうところに気持ちよさも感じます。解き方にしても、余り1と余り-1が足されて0になって3の倍数になるところなんかよくできてんなー!って感じです。

こんな問題を時間内に自分の頭だけ使って解けってんですから京大生はすごいですね。ぼくにはとてもできない

他にも、最後の式を\left(p-1\right)\left(p+1\right)まで持っていってp3の倍数ではないのでp-1p+1の少なくともどちらかは3の倍数になる。よって\left(p-1\right)\left(p+1\right)3の倍数になる。みたいなやり方をしているものも見つけて、なかなかスマートで感激しました。いろんな解き方があるところも数学の魅力の一つですね。