2つの素数のべきの和が素数になる組

方針

解答

⓪ 発想 — どう考え始めるか。 「素数になる組をすべて」型は、候補を消していく消去法で進める。

第一の刃は偶奇だ。$p,q$ がともに奇素数なら、$p^q+q^p$ は奇数+奇数=偶数で、2より大きいから合成数。よって一方は2。

$p=2$ として $2^q+q^2$ を調べると、$q=3$ で17(素数)が見つかる。問題は「$q>3$ では全部だめ」とどう言い切るかだ。ここで法を3に切り替える。$2\equiv -1(\mathrm{mod}3)$ だから $2^q$ の余りは $q$ の偶奇だけで決まり、$q^2$ の余りは「3で割れない数の平方は1」で決まる。2つを足すと3の倍数になってしまう、という仕掛けだ。

① 一方は2。 $p,q$ がともに奇素数なら $p^q+q^p$ は偶数で4以上だから素数でない。対称性から $p=2$ の場合を調べ、最後に $p,q$ の入れ替えを含めればよい。

② 小さい $q$ を試す。 $q=2$: $2^2+2^2=8$ で不適。$q=3$: $2^3+3^2=8+9=17$ は素数。候補になる。

③ $q>3$ の素数はすべて不適。 $q$ は奇数で、3の倍数でもない。$2\equiv -1(\mathrm{mod}3)$ より

$$2^q\equiv (-1{)}^q=-1\equiv 2(\mathrm{mod}3)$$

また $q$ は3で割れないから $q^2\equiv 1(\mathrm{mod}3)$。よって

$$2^q+q^2\equiv 2+1=3\equiv 0(\mathrm{mod}3)$$

つまり $2^q+q^2$ は3の倍数で、明らかに3より大きいから合成数。

④ 結論。 $(p,q)=(2,3)$ と、入れ替えた $(3,2)$ のみ。値は $17$。

まとめ: 偶奇 → 法3、と刃を持ち替える消去法。「$-1$ の奇数乗は $-1$」「3で割れない数の平方は1」という2つの小さな道具の連係で、無限個の候補が一撃で消える。

発展 — 一歩先へ。 実は $p^q+q^p$ が素数になる組は、$(2,3)$ 型のほかには1つも知られていない。たった2つの素数の組合せなのに、その先が誰にも分かっていない。整数の世界の「浅いところにある深い謎」の見本だ。

別解

なぜ「3」を試すのか — 法の選び方(得意な人向け)。 本解の法3は天下りに見える。候補の法を順に打診する思考をそのまま見せよう。

$2^q+q^2$ の余りを調べやすい法は、$2^q$ か $q^2$ の余りが単純になる法だ。

• 法4: $q\ge 3$ なら $2^q\equiv 0$、$q$ は奇数で $q^2\equiv 1$。和は $\equiv 1$。矛盾は出ない
• 法8: 同じく $2^q\equiv 0$、奇数の平方は $\equiv 1$。和は $\equiv 1$。やはり決まらない
• 法3: $2\equiv -1$ だから $2^q\equiv -1$($q$ 奇数)。$q$ が3の倍数でなければ $q^2\equiv 1$。和は $\equiv 0$ — 当たり

平方の余りが単純な法(3, 4, 8)を並べ、$2^q$ の余りの周期と噛み合うものを探す。この「打診」の目で見ると、法3は偶然ではなく、$2\equiv -1(\mathrm{mod}3)$ という好都合の帰結だと分かる。合同式の問題で法をどう選ぶか。その判断こそが、この種の問題の本当の技術だ。