京大2016年度理系第2問(整数問題)

問題.

素数 $p, q$ を用いて

$p^q+q^p$

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

素数に関する整数問題です. 答えだけなら簡単に(当てはめて)求まりますが, それ以外に答えがないことを示す必要があります. $p, q$ に小さい素数を当てはめてみることで解答の糸口を探します.

解答.

与えられた式の対称性から, $p\leqq q$ としてよい.

[1] $p=2$ , $q=2$ のとき

$p^q+q^p=2^2+2^2=8$ より素数でない.

[2] $p=2$ , $q=3$ のとき

$p^q+q^p=2^3+3^2=17$ より素数である.

[3] $p=2$ , $q\geqq 5$ のとき

5 以上の素数は, 自然数 $n$ を用いて $6n\pm 1$ と書くことができる

( $\because$ 6 で割った余りが 0, 2, 3, 4 である自然数はそれぞれ 6, 2, 3, 2 の倍数となり素数でない).

このとき,

\begin{align*}
p^q+q^p &= 2^{6n\pm 1}+(6n\pm 1)^2\\
&\equiv (-1)^{6n\pm 1}+(\pm 1)^2\\
&\equiv -1+1\\
&\equiv 0
\end{align*}

ただし, $A\equiv B$ は $A-B$ が 3 で割り切れる (つまり, $A$ と $B$ を 3 で割った余りが等しい)ことを表し, $2\equiv -1$ , $6n\pm 1\equiv \pm 1$ を途中で用いています.

(これを合同式といいます. 合同式についてはこちら. )

よって, $p^q+q^p$ は 3 の倍数であって, $p^q+q^p>p+q>3$ より, これは素数でない.

[4] $p\geqq 3$ , $q\geqq 3$ のとき

$p, q$ はともに奇数なので, $p^q+q^p$ は偶数となり, $p^q+q^p>p+q>2$ なので, $p^q+q^p$ は素数でない.

[1]～[4]より, 素数 $p, q$ を用いて $p^q+q^p$ と表される素数は17のみ.

追記.

上にも書きましたが, 今回のような問題では, まず $p, q$ としていくつか素数を当てはめて $p^q+q^p$ が素数になるかを調べてから解答の糸口を探します. まず, 場合分けの[1], [2], [4]の場合はすぐに気が付きますが, [3]の証明が問題です. 実際に小さい素数を当てはめると,

$2^5+5^2=57=3\cdot 19$ , $2^7+7^2=177=3\cdot 59$ などから, $p^q+q^p$ が3の場合になると言えそうです. そこで, 5 以上の素数が $6n\pm 1$ と書けることを利用して証明ができました.