2016年の京都大学理系の素数が絡んだ整数問題です。
一見複雑ですが、うまく絞り込めばあっという間に解くことも可能です。
どのような分類で絞り込みをするのか、工夫してみましょう。
問題
素数 $p,q$ を用いて, $p^q+q^p$ と表される素数をすべて求めよ。
2016年京都大学理系より
解答
$p,q$ がともに奇数であるとき、$p^q+q^p$ は偶数となる。
そのような素数は2のみであるが、$p,q\geq 3$ より、$p^q+q^p=2$ とはならない。
したがって、$p,q$ のいずれかは偶素数である。
ここで、$p=2$ とする。
このとき、$q=2$ は $p^q+q^p=8$ となり不適。
よって、$q$ は奇素数である。
(i) $q=3$ のとき
$$p^q+q^p=17$$
となり、これは素数である。
$q\neq 2,3$ のとき、このような素数は非負整数 $k$ を用いて、 $q=6k+1$ または $q=6k+5$ と表せる。
以下、$2^6k\equiv 64^k\equiv 1 \mod 3$ を利用する。
(ii) $q=6k+1$ のとき
$$2^q=2^{6k+1}\equiv 2\mod 3$$
より、
$$2^q+q^2\equiv 2+1^2\equiv 0 \mod 3$$
(iii) $q=6k+5$ のとき
$$2^q=2^{6k+5}\equiv 2^5\equiv 2\mod 3$$
より、
$$2^q+q^2\equiv 2+5^2\equiv 0 \mod 3$$
よって、$p=2$、$q\neq 2,3$ のとき $p^q+q^p$ は3の倍数である。
また、$p^q+q^p>3$ であるから、素数でもない。
したがって、対称性も考慮し、求められる素数は $17$ のみである。
ワンポイント
(ii)以降で、6で割ったあまりに注目するのがポイントです。
いきなりそこに着目することは難しいかもしれませんが、3で割ったあまりで場合分けすることがうまくいかないので工夫が必要でした。