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

問題編

【問題】
素数p,qを用いて\[p^q+q^p\]と表される素数をすべて求めよ。

【考え方】
一見、条件が少なすぎる気がしますが、よく見ると大幅に候補をしぼることができます。pとqが、両方奇数、または両方偶数の場合、$p^q+q^p$は偶数になります。これが素数になるには、2しかありませんがそんなことはありえません。このことから、片方が偶数、片方が奇数であることがわかります。つまり、「2と奇数」です。ここまではすぐにわかります。

つぎにさらに絞るためにいくつか計算してみます。$p=2$とすると、$2^3+3^2=17$、$2^5+5^2=57$、$2^7+7^2=177$、$2^{11}+11^2=2169$となります。一つ目は素数で、それよりあとは3の倍数。これらをもとに、qが3じゃないときは$2^q+q^2$が3で割れるんじゃないかと予想して式変形していくと、これが正しいことがわかります。

---

解答編

【問題】
素数p,qを用いて\[p^q+q^p\]と表される素数をすべて求めよ。

【解答】
$p=q=2$とすると、$p^q+q^p$は8なので、素数ではない。

$p$も$q$も奇数のとき、$p^q+q^p$は偶数なので、これが素数だとすると2しかない。しかし、$p^q$も$q^p$も2以上の整数なので、2となることはない。

以上のことから、pかqのどちらかは偶数、どちらかは奇数となる。なお、どちらも素数なので、偶数の方は2である。

以下では、pを2、qを奇数とする。対称性から、この場合だけ考えればよい。

$q=3$のとき、$p^q+q^p=2^3+3^2=17$なので素数となる。

$q$を5以上の素数とする。

$2^q = (3-1)^q \equiv (-1)^q \pmod3$であり、qは奇数だから、\[2^q \equiv -1 \pmod3\]となる。

また、qは5以上の素数だから3で割り切れないので、整数nを用いて、$q=3n\pm 1$とかける。このとき、\[(3n \pm 1)^2 \equiv 1 \pmod3\]となる。

よって、\[2^q + q^2 \equiv 0 \pmod3\]となる。これから、$2^q + q^2$は3より大きい3の倍数であることがわかるので、これが素数になることはない。

以上から、求める答えは、17のみ。

【解答終】

【解説】
「2と奇数」にしぼった後からが少し難しいですね。3の倍数になるというのは、少し書き出してみれば予想できるかもしれませんが、それに気づけないとなかなか先に進みづらいかと思います。