京大2016年理系第2問 - 数式で独楽する

素数 $p,q$ を用いて $p^q + q^p$ と表される素数をすべて求めよ。

解答例
解説

解答例

$p,q$ が共に奇数である場合、

$p^q + q^p$ は偶数、つまり2の倍数
になります。
したがって、少なくとも一方は偶数の素数、すなわち2となります。

$p=q=2$ の場合、
\begin{equation}
p^q + q^p = 2^2 + 2^2 = 8
\end{equation}は素数ではありません。

以下、 $p=2,\ q \ne 2$ とします。 $p^q + q^p$ は $p,q$ について対称であり、このように限定しても一般性を失いません。

$q>3$ の場合、 $q \equiv \pm 1 \mod 3$ なので、
\begin{equation}
2^q + q^2 \equiv -1 + (\pm 1)^2 = 0 \mod 3
\end{equation}となります。
つまり、 $2^q + q^2$ は3の倍数となります。

$q=3$ の場合、
\begin{equation}
2^3 + 3^2 = 17
\end{equation}は素数です。

以上より、求める素数は17のみとなります。

解説

問題文が簡潔に書かれています。
しかも「素数」と「すべて」が、取り付きにくさを増幅させています。

ところが、無限にある素数のうち偶数は2のみというのが、候補の絞り込みを容易にしてくれています。
そこかしこに背理法を散りばめて、あり得ない条件を排除しています。

もう片方が3かどうかで場合分けした根拠は次の通りです。
片方が2であるということが分かれば、幾つか数字を入れてみて、
\begin{eqnarray}
2^3 + 3^2 &=& 17 \\
2^5 + 5^2 &=& 57 &=& 3 \times 19 \\
2^7 + 7^2 &=& 177 &=& 3 \times 59 \\
& \vdots &
\end{eqnarray}求める素数は17のみであろうという目星をつけることができます。

あとは3ではない素数を持って来ると $2^q + q^2$ が3の倍数になることを確認します。
3の倍数ではないので、3で割れば1余るか1足りない(2余る)かのいずれかです。
ということで、本文のような展開になります。
なお、 $q$ は奇数なので、
\begin{equation}
2^q \equiv -1 \mod 3
\end{equation}です。