入試標準レベル
入試演習 整数
素数$p$,$q$を用いて$p^q+q^p$と表される素数を全て求めよ。
（京都大学）
数値代入による実験
まずは色々な素数$p$,$q$を選んで実験してみてください。
先生、一つ見つけましたよ！$p=2$,$q=3$として、17が作れます！
そうですね。17は作れますね。他には見つかりますか？
…
…5分後
カリカリ…カリカリ……うーん、見つからないですね。どれも素数にはならないです…もうこの1つしかないんじゃないですか？
結果を先に言うと、この一つしか存在しないんです。しかし、問題文の「すべて求めよ」の言葉の中には、「他には存在しない」ことが分かるように解答せよという意味も含まれています。
例えば、「$x^3-8=0$をみたす実数をすべて求めよ。」という問題に、「2を代入すると成立するから、$x＝2$」と解答してよいと思いますか？
結論としては$x＝2$が唯一の実数解ですが、他の二つが虚数解であることが重要なんですよね。
この問題は「条件をみたす$p$,$q$の組は2と3に限る」ことを示すのが最も重要なポイントです。
「すべて求めよ」とか言っておきながら1つしかないなんて、意地悪な問題ですね！
整数問題の必須手法「剰余で分類する」
整数問題を考えるとき、「余りによって分類する」ことが多くあります。そのうち最も簡単なものが、2で割った余りで分類する、つまり「偶奇で分類する」ものです。
$p$と$q$の偶奇の組み合わせのうち、あり得ないものはなんですか？
えっと、偶数と偶数はおかしいですね。偶数＋偶数で、出来上がるのは偶数になってしまうので、素数になりません。
そう、素数のなかで偶数であるものは2しかないですからね。他にもありえない組み合わせはありますか？
奇数と奇数もおかしいです。奇数の奇数乗は奇数なので、奇数＋奇数で、出来上がるのは偶数になって素数になりません。
そうなると偶数と奇数の組み合わせしかありえないとなりますが…
あ！偶数である素数は2だけなので、片方は2で決定ですね！
そのとおり。$p$と$q$どちらが2でも問題に影響はありませんから、ここでは$p=2$として、$q$をそれ以外の素数としましょう。
$q$について実験
$q$にいろいろな素数を入れてみましょう。 $q=3$のときには$2^3+3^2=17$となって素数になりますが…
$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で割り切れるというのを使って。
うん、まずは3の
倍数判定法を使うよね。そうするとどれも3で割り切れてしまうことがわかるんです。
倍数判定法何か大きな整数があって、何で割り切れるかを調べないといけないことはしばしばあります。倍数の判定をする方法をまとめておきます。
倍数判定...
もっと大きい$q$を入れたときも必ず3の倍数になりますかね！？
だから今からの目標は、「$q$が3より大きいときには$2^q+q^2$が3の倍数になる」ことを示すことです。
3の剰余で分類
合同式をつかって、3の剰余に注目してみましょう。
合同式 速習講座合同式の定義から使い方、例題まで解説しています。...
$q^2$に注目
「$q$が3より大きいときには$2^q+q^2$が３の倍数になる」ことを示すのが目標ですから、$q$は3より大きい素数として考えましょう。
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^q$もどうなるか考えてみましょう。「$q$が3より大きいときには$2^q+q^2$が３の倍数になる」という結論から逆算して考えると、$2^q$を3で割った余りはどうなったらいいですか？
えっと、$q^2$が余り1だから、足して3の倍数にするには…$2^q$は余り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だけである。
（解答終わり）
