素数でアハ体験 – 2016年京大 数学 第2問

2021年7月2日2023年3月5日

　2016年京大 数学 第2問 は、指定された条件の整数が素数であることの証明です。問題文は以下の通りです。

素数 p,q を用いて

p^q+q^p

と表される素数をすべて求めよ.

　素数のべき乗の和が素数になるとか、なんかゴールドバッハ予想みたいな主張です。そんなの簡単に解けるのかよ、とか、すべて求めよと言っているが素数なのだから無限にあるんじゃないか、とか、捨て問フラグ立ちまくりの予感ですが、実はちょっとした手掛かりから一気に解くことが出来て、強烈なアハ体験を味わえます。解法を見る前に、軽く挑戦してみてください。

　では、解法の説明に入ります。

p,q の一方は２である

　　いきなり強烈ですが、素数と言うのは大抵奇数なので、何も考えずに p,q をチョイスすると、 p^q+q^p は偶数になってしまいます。和が奇数になるためには、 p,q のいずれか一方だけが偶数、すなわち2である必要があります。

　以下、 q=2 であるとして、論考を進めます。

実際に計算して傾向を見る

　どんな時に素数になるのか傾向をつかむために、 p にいろいろな値を代入してみて、実際に計算してみます。

　以下の通りです。

　 p=3 のとき以外は、素数ではなく、しかも3で割れそうな気配です。以下、 p \geqq 5 のときに、これの証明を試みます。

p^2+2^p が3で割れる証明

　まず 2^p を評価します。 p は奇数なので、ある自然数 m が存在して、 p = 2m+1 と表記できます。

　このとき

2^p = 2^{2m+1} =  2 \cdot 4^m

ですが、 4 \equiv 1 \mod 3 なので、 4^m \equiv 1 \mod 3 です。したがって、

2^p \equiv 2 \mod 3

が成り立ちます。

　次に p^2 です。 p は5以上の素数なので、当然3では割り切れません。3で割った余りは1か2のどちらかですが、どちらの場合も

p^2 \equiv 1 \mod 3

が成り立ちます。ゆえに

p^2 + 2^p\equiv 0 \mod 3

となり、 p^2 + 2^p は3で割り切れることが示せました。

　以上の考察により、 p^q+q^p が素数となる ( p,q) の組み合わせは (2,3) しかなく、その時の p^q+q^p の値は17です。

解法のポイントと今後の学習方針

　まず、　 p, q の一方が2であることに気が付くことがポイントです。本稿でのロジックはポピュラーなものなので、是非マスターしましょう。

　次に重要なのは、実際に値を計算して傾向をつかむことです。試験問題ではべらぼうな計算を求められることは考えにくいので、数パターンの計算で傾向がつかめるはずです。

　3で割り切れることが予想できてしまえば、その証明は容易なので、一気に解答にたどり着くことが出来ると思います。

　以上、実際に解いてみてそう快感を味わえたでしょうか。素数が絡んだ問題は本問同様、ちょっとしたヒントから一気に解けることが多いと思います。整数が何かで割れる／割り切れない的な問題をたくさん解いて、感覚をつかむようにしてください。