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

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

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

引用します。

素数 $p, q$ を用いて

　 $p^q+q^p$

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

なるほど

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

解説してみた

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

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

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

偶奇で分けて考える

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

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

$p,q$ の偶奇が一致しているとします。すると、 $p^q$ と $q^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$ になります。元の問題は $p$ と $q$ を入れ替えても成立するような問題であり、つまりどっちでもいいってことなので $q$ を $2$ ってことにします。するともう片方の $p$ は $3$ 以上の素数ということになります。

$p$ を $3$ で割った余りで分けて考える

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

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

「 $-1$ 余る」というのは「 $2$ 余る」ということと同じ（合同）です。 $3$ で割った数の世界において、 $-1$ と $2$ は同じなんです。「 $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^p$ は $3$ の倍数」という結果が出てきたことになります。

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

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

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

証明のおおまかなまとめ

$p,q$ の偶奇が一致するとすると全体が偶数になっちゃってヤバい
$p,q$ の偶奇は一致しない
よって $q$ は $2$
$p$ は $3$ の倍数じゃないとすると全体が $3$ の倍数になっちゃってヤバい
$p$ は $3$ の倍数
よって $p$ は $3$
よって $p^q+q^p$ は $3^2+2^3$ の $17$ のみ

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

はい

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

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

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

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