面白そうだったのでついやってみました。
素数の問題(京都大学2016理系数学)
素数p,qを用いてp^q+q^pで表される素数を全てもとめよ。
コメント
問題の意味は簡単そうですね。しかし、式だけみても、どうしたらよいのかさっぱりわかりません。使えそうな公式も思いつきません。
こういう場合は、小さなp,qに対していくつか計算しある程度予測をたてて、予測を証明して攻めていくしかありません。ひらめき、予測力が必要です。
解法
p,qが奇数だった場合は、p^q+q^pは偶数である。これに気がついた瞬間、かなりの希望の光が見えます。なにせ、p,qの片方は2であると絞り込まれるからです。
p=q=2の場合もありえないわけですから、とりあえず、p=2として解を求めます(p,qの対称性からこの仮定はOK)。
問題は簡素化されました。2^q+q^2の形の素数を全て求めよ。
かなり絞り込まれたとはいえ、なかなか糸口が掴めないです。modでうまく絞り込めないかを考えますが、もし絞りきれなければ難問化してしまいます。
先に、偶数奇数(mod2)で考えたので、今度はmod3を試してみます。だめだとしたら、q^2についてはmod4の絞込がよさそうです。3でだめなら4も有効そうです。
まず、mod3で考えます。
1^2≡1 mod(3)
2^2≡1 mod(3)
3^2≡0 mod(3)
4^2≡1 mod(3)
お、平方数はmod3で考えると0か1しかないわけで、1,1,0,1,1,0,…の繰り返し
2のベキの方はというと、
2^1≡2 mod(3)
2^2≡1 mod(3)
2^3≡2 mod(3)
2^4≡1 mod(3)
・・・ 2,1,2,1と繰り返しています。
2^q+q^2をmod2と3で考えるために、qを6の周期で考えればよくて、それぞれの組み合わせに対してmodを計算すると、
2^1+1^2≡2+1≡3 mod(6) 3で割れる
2^2+2^2≡4+4≡2 mod(6) 2で割れる
2^3+3^2≡8+9≡5 mod(6) 素数かも
2^4+4^2≡16+16≡2 mod(6) 2で割れる
2^5+5^2≡32+25 ≡3 mod(6) 3で割れる
2^6+6^2≡64+36≡4 mod(6) 2で割れる
素数の可能性があるのは、
2^3+3^2≡8+9≡5 mod(6)から、q≡3(mod6)に絞り込まれました。
つまり、2^(6n+3)+(6n+3)^2のパターンに絞り込まれました。
q=6n+3、0\le nとおいて、
2^(6n+3)+(6n+3)^2≡8・64^n+36n^2+36n+9が素数になるためには、・・・こういうふうに考えるとドツボにはまります。なにせ、このようなqは無限に存在するので。
そこで、視点を変えて、qが素数であるための条件を考えます。
q≡3(mod6)なので、これがq=3を除くと、qは3で割り切れます。
したがって、q=3のみしかありえません。やったー!
2^3+3^2=17より、
答え17(ただ一つ)
※問題としては答えが2,3個あるかと思っていましたが、答えは1個でした。