$p^q+q^p$と表される素数
入試標準レベル
素数$p$,$q$を用いて$p^q+q^p$と表される素数を全て求めよ。
（京都大学）
数値代入による実験
…
…5分後
整数問題の必須手法「剰余で分類する」
整数問題を考えるとき、「余りによって分類する」ことが多くあります。そのうち最も簡単なものが、2で割った余りで分類する、つまり「偶奇で分類する」ものです。
$q$について実験
$q=5$のとき
$2^5+5^2=32+25=57$
57=3×19より素数ではない。
$q=7$のとき
$2^7+7^2=128+49=177$
177=3×59より素数ではない。
$q=11$のとき
$2^{11}+11^2=2048+121=2169$
2169=9×241より素数ではない。
3の剰余で分類
合同式をつかって、3の剰余に注目してみましょう。
$q^2$に注目
3より大きい素数は3の倍数ではないから、$q\equiv1$または$q\equiv2$(mod 3)のいずれかとなる。
$q\equiv1$のとき$q^{2}\equiv1$(mod 3)
$q\equiv2$のとき$q^{2}\equiv2^{2}\equiv4\equiv1$(mod 3)
より、いずれにしても$q^{2}\equiv1$(mod 3)
$2^q$に注目
合同式を使って余りを求めると、
$2^{2n+1}\equiv4^{n}\times2\equiv1^{n}\times2\equiv2$(mod 3)
解答
$p$,$q$がともに偶数のとき、$p^{q}$,$q^{p}$はともに偶数であるから、$p^{q}+q^{p}$は偶数となり、
$p$,$q$がともに奇数のとき、$p^{q}$,$q^{p}$はともに奇数であるから、$p^{q}+q^{p}$は偶数となる。
2より大きい偶数は素数でないことから考えて、$p^{q}+q^{p}$が素数になるのは$p$,$q$のいずれかが2であるときに限られる。
ここで$p=2$としても一般性を失わない。
このとき$q$は3以上の奇数になる。
ここで、$q$が3より大きな奇数であるとすると、
$q\equiv1$,$q\equiv2$(mod 3)のいずれかとなる。
$q\equiv1$のとき$q^{2}\equiv1$(mod 3)
$q\equiv2$のとき$q^{2}\equiv2^{2}\equiv4\equiv$1(mod 3)
であるから、いずれにしても
$q^{2}\equiv1$(mod 3)である。
また、$q$が3より大きな奇数のとき、$q=2n+1$($n$:自然数)と表すことができる。
このとき
$2^{q}\equiv2^{2n+1}\equiv4^{n}\times2\equiv1^{n}\times2\equiv2$(mod 3)となる。
よって$q$が3より大きな奇数であるとき、$2^{q}+q^{2}$は3の倍数になる。
$2^{q}+q^{2}$は3より大きいから、素数ではない。
以上より、$p^{q}+q^{p}$と表される素数は、$2^{3}+3^{2}$、つまり17だけである。
（解答終わり）
