【入試過去問】p^q+q^p=素数となる素数p,qの組を全て求めよ【整数問題】

数学

整数問題でよく取り上げられる問題です。
私も解いてみました。
どの問題も場合分けは重要ですが、
ちゃんと説明しようとすると、
文章が冗長で複雑になってくるので
気楽にやっていきましょう。

問題
$$p^q+q^pが素数となる素数p,qを全て求めよ$$
スポンサーリンク

とりあえずいろいろやってみる

題意より

$$p^q+q^p=r(r\in 素数)(①)$$

とする

まず、素数の大事な特徴として

  • 偶数の素数は2だけ!
  • それ以外は奇数!

という事実があります。

右辺のrが素数となるのは2または奇数
となるときしか成立しないということが分かります。

まずp=q=2を代入するとどうなるかな

$$2^2+2^2=8$$
となって素数ではないので不成立

右辺が8になっていることからもrは奇数になるパターンしかない
ということが分かります。

そうすると何となく、

pまたはqのどっちかが2になりそうな…

そんな予感を持ちつつ、
ではp,qが両方とも奇数の場合を考えています。

$$p=2m+1,q=2n+1(m,nは0以上の整数)とおける$$

$$(①の左辺)=(2m+1)^{2n+1}+(2n+1)^{2m+1} \\
\equiv 1^{2n+1}+1^{2m+1}(mod 2) \\
\equiv 1 + 1(mod 2) \\
\equiv 0 (mod 2)$$

となりrが偶数であることがわかります。
つまりp,qが両方奇数の時、素数となるrは存在しない。
ということから、p,qはどちらかが、偶数となります。
偶数の素数は2しかありません。
ということは、
pまたはqのどちらかが2とわかります。

式①は対称性を持っていますので、
とりあえずp=2として議論をすすめます。

式①はつぎのようになります。

$$2^q+q^2=r(②)$$

さて、ここからどうしようか…

とりあえず、今度は3の倍数で考えてみるか…

ということで、

$$q=3m+1$$
として考えてみた

②式は

$$(②の左辺)\equiv (-1)^{3m+1}+(3m+1)^2(mod 3)\\

\equiv -(-1)^m+1(mod 3)$$

mが偶数の時は余りが0になるので、rが3の倍数になる。
ということはr=3となるとき以外は不成立。
mが奇数の時は、余りが2となるが、
これが素数になるかどうかの判断には使えない。

ちなみに$$q=3m-1$$のときもやってみたが、
結果は同じだった。

道に迷った…

そもそも、全て求めよ、という問題からしても
p,qの組は有限、というか数えられるぐらいの組数しか
なさそうな気がする。

こういう、整数や素数に限られた問題は
順番に代入をして、ヒントを見つけようとすることがある。

順番に代入しよう

$$q=3の時、2^3+3^2=8+9=17 →素数なので成立!\\
q=5の時、2^5+5^2=32+25=57=3\times 19 →不成立\\
q=7の時、2^7+7^2=128+49=177=3\times 59 →不成立\\
q=11の時、2^{11}+11^2=2048+121=2169=3\times 723 →不成立\\$$

次の2つのことに気づきました。

q=3以外の時は、

3の倍数になっている

$$mod 3のときに2^qの余りが-1,q^2の余りが1$$

後から見ると当たり前といえば当たり前なのですが、
問題を解いていると、見逃してしまうことがります。

p,qは素数なので、

  • 2以外の2の倍数(偶数)
  • 3以外の3の倍数

は除外できます。

qが3の時は代入したので、
それ以外の数、つまり
qは2の倍数でもなく、3の倍数でもない数を
検証していけばいいことになります。

その場合、qは

$$q=6l+1,6l-1(lは整数)とおくことができます$$

なぜなら下記の通りだからです。
q=6l-2 ←2の倍数
q=6l-1
q=6l ←2かつ3の倍数
q=6l+1
q=6l+2 ←2の倍数
q=6l+3 ←3の倍数

ということで

$$q=6l+1のとき\\
(②の左辺)=2^{6l+1}+(6l+1)^2\\
\equiv (-1)^{6l+1}+1^2(mod 3) \\
\equiv -1+1 \equiv 0(mod 3)$$

$$q=6l-1のとき\\
(②の左辺)=2^{6l-1}+(6l-1)^2\\
\equiv (-1)^{6l-1}+1^2(mod 3) \\
\equiv -1+1 \equiv 0(mod 3)$$

つまり3より大きい素数の場合、
からなず3の倍数になることから不成立となる

これで材料がそろった!

では回答に入ります。

私の回答

題意より

$$p^q+q^p=r(r\in 素数)(①)$$

とする

(i)

まず、p=q=2の場合を考える。

最小の素数であるp=q=2を代入すると

r=8となり不成立。

(ii)

(仮定)p,qがともに奇数の時、①が成立と仮定する

$$p=2m+1,q=2n+1(m,nは0以上の整数)とおける$$

$$(①の左辺)=(2m+1)^{2n+1}+(2n+1)^{2m+1} \\
\equiv 1^{2n+1}+1^{2m+1}(mod 2) \\
\equiv 1 + 1(mod 2) \\
\equiv 0 (mod 2)$$

となりrは偶数となる

また、rは最小の素数であるp=q=2を代入したときr=8であったことから
rは8より大きい素数しかとりえない

よって、p,qが両方が奇数の時、
素数となるrは存在しないことになり(仮定)に矛盾が生じる。

よって、p,qはどちらかが、偶数となる。

また、偶数の素数は2しかないため、
pまたはqのどちらかが2となる。

(iii)

①式の対称性より、p=2として、qの値を求める。

q=3を代入する。

$$q=3の時、2^3+3^2=8+9=17$$
rが17で素数となり①が成立!

よってp=2,q=3が成立。
対称性よりp=3,q=2も成立。

(iv)

qが3以上の場合を考える。

qは素数なので2,3以上の素数は
2の倍数でもなく、かつ3の倍数でもない
という数について考えていく。

この場合、qは

$$q=6l+1,6l-1(lは整数)とおくことができる$$

ということで

$$q=6l+1のとき\\
(②の左辺)=2^{6l+1}+(6l+1)^2\\
\equiv (-1)^{6l+1}+1^2(mod 3) \\
\equiv -1+1 \equiv 0(mod 3)$$

$$q=6l-1のとき\\
(②の左辺)=2^{6l-1}+(6l-1)^2\\
\equiv (-1)^{6l-1}+1^2(mod 3) \\
\equiv -1+1 \equiv 0(mod 3)$$

つまり3より大きい素数の場合、
からなず3の倍数になる。

最小の素数であるp=q=2を代入したときr=8であったことから
rは8より大きい素数しかとりえない。

よって3の倍数で、唯一の素数である3をとることはない。

よって2、3以外の素数の場合はrは(8より大きい)3の倍数にしかならないため、
①を満たす素数p,qは存在しない。

よって(i)(ii)(iii)(iv)より、p,qの組み合わせは
$$(p,q)=(2,3),(3,2)$$
である。

(終)

回答の穴はないはず

色々大変だったけど
これでOKなはず。

解法はこうだった

整数、素数、京都大学入試問題 数学 Japanese university entrance exam questions Kyoto University

解き方はほぼ一緒でした。
動画の中で麻雀トリビアも出てきましたが解答には
関係ありません。

パターンを押さえて「素数の神」になれ!【整数問題で勝つ】

動画の中で、整数問題の解き方のポイントも解説していただいています。

  1. 因数分解して積の形に
  2. 倍数、余りを利用する
  3. 不等式評価による絞り込み

厳密な回答の説明というよりは
倍数や余り、素数の性質から
こうやって答えが見つけられるよ、
ということを提示しております。

まとめ

無限に存在されても困るので、
どうやって結論を付ければいいのか
という点で困ってしまいました。

ただ、2の倍数でも3の倍数でもない
という形を検証することに
気が付いたのがよかった。
おかげで自力で答えにたどり着くことができました。

  • 小さい数でアタリを付ける
  • 素数の性質を理解する
  • こうなりそうだ、という仮説を見つける

ということが大事だと確認できました。

ほかの整数問題も見たい方はこちらです。

タイトルとURLをコピーしました