京都大学 2016年 理系 第2問 解説

方針・初手

• $p,\ q$ の偶奇に着目します。両方が奇数の場合、和が偶数になり素数になり得ないことから、$p,\ q$ のいずれかが 2 であることを導きます。
• $p = 2$ と固定した上で、$q$ に具体的な素数を代入して規則性を探ります。$q = 3$ のときは素数になりますが、$q > 3$ のときは 3 の倍数になると予想し、合同式を用いてそれを証明します。

解法1

$p,\ q$ を素数とし、$N = p^q + q^p$ とおく。$N$ が素数となる条件を考える。

式は $p$ と $q$ について対称であるから、$p \leq q$ としても一般性を失わない。

$p,\ q$ がともに奇素数であると仮定する。

このとき $p^q$ も $q^p$ も奇数の奇数乗であるから奇数となる。奇数同士の和である $N = p^q + q^p$ は偶数となる。

さらに $p \geq 3,\ q \geq 3$ であるから、$N \geq 3^3 + 3^3 = 54 > 2$ であり、$N$ は 2 より大きい偶数となるため、素数ではない。

したがって、$N$ が素数となるためには、$p,\ q$ の少なくとも一方は偶数の素数、すなわち 2 でなければならない。

$p \leq q$ と仮定したため、$p = 2$ である。

このとき $N = 2^q + q^2$ となる。$q$ は素数であるから、$q = 2,\ 3$ および $q > 3$ の場合に分けて調べる。

(i) $q = 2$ のとき

$$ N = 2^2 + 2^2 = 8 $$

$8$ は素数ではない。

(ii) $q = 3$ のとき

$$ N = 2^3 + 3^2 = 8 + 9 = 17 $$

$17$ は素数である。

(iii) $q$ が 3 より大きい素数のとき

$q$ は奇数であり、また 3 の倍数ではない。以下、法を 3 とする合同式を用いて考える。

$q \not\equiv 0 \pmod{3}$ より、$q \equiv 1 \pmod{3}$ または $q \equiv 2 \pmod{3}$ のいずれかである。

$$ q \equiv 1 \pmod{3} \implies q^2 \equiv 1 \pmod{3} $$

$$ q \equiv 2 \pmod{3} \implies q^2 \equiv 4 \equiv 1 \pmod{3} $$

いずれの場合も $q^2 \equiv 1 \pmod{3}$ が成り立つ。

一方、$2 \equiv -1 \pmod{3}$ であり、$q$ は素数かつ $q > 3$ より奇数であるから、

$$ 2^q \equiv (-1)^q \equiv -1 \pmod{3} $$

ゆえに、

$$ N = 2^q + q^2 \equiv -1 + 1 = 0 \pmod{3} $$

$N$ は 3 の倍数である。$q > 3$ のとき $N = 2^q + q^2 > 2^3 + 3^2 = 17 > 3$ であるから、$N$ は 3 より大きい 3 の倍数となり、素数ではない。

(i)〜(iii) より、$p \leq q$ のもとで $N$ が素数となるのは $(p,\ q) = (2,\ 3)$ のときのみであり、そのときの値は 17 である。

対称性から $(p,\ q) = (3,\ 2)$ のときも同様に $N = 17$ となる。

したがって、条件を満たす素数は $\mathbf{17}$ のみである。

解説

素数に関する問題で条件を絞るための強力な武器である「偶奇の確認（2 の倍数かどうか）」と「3 の剰余（3 の倍数かどうか）」を順番に用いる典型的な整数問題です。

まず、偶数と偶数の和は偶数、奇数と奇数の和は偶数であることから、「素数が奇数ばかりであると和が偶数になり素数にならない（2 を除く）」という性質を使って、素数の中の例外的な存在「2」を特定します。

その後、$q$ が 5 以上の素数のときに 3 の倍数になることを証明する際、合同式を使うと記述が非常に簡潔になります。$2 \equiv -1 \pmod{3}$ とみなし、奇数乗すれば $-1$ になるという処理はよく使うテクニックです。

答え

条件を満たす素数は $\mathbf{17}$ のみである（$(p,\ q) = (2,\ 3)$ または $(3,\ 2)$ のとき）。