何十年ぶりに数学の整数問題を解いてみました。
数式の入力方法が分からず、すべて画像のため読みづらいと思いますが、ご容赦ください。
問題
（京都大学）
素数 p, q を用いて
pq + qp
と表される素数を求めよ。
解答例
最も小さい素数は2のため、 pq + qp ≧ 22 + 22 = 8 ---- (1)
pとqがともに奇数またはともに偶数だと仮定すると、「pq + qp」は偶数となる。
偶数の素数は2しかないが、(1)よりこのとき与式は2になることはないため、素数となることはない。
そのため、pとqのどちらかは偶数でどちらかが奇数である。
偶数の素数は2しかないため、どちらかは奇数でどちらかは2であると確定できる。
pとqは対称性があるため、pが奇数、q=2 とし、与式に代入すると
p2 + 2p
与式を3で割ったときを検討する。
pが奇数なので、 2p ≡ (-1)p ≡ -1 (mod 3) ---- (2)
- A) p≡0 (mod 3) のとき
- pは3の倍数であると同時に素数のため、p = 3 と確定できpが奇数であることと矛盾しない。
- これを与式に代入すると pq + qp = 32 + 23 = 17 となり、素数となる。
- B) p≡1 (mod 3) のとき
- p2 ≡ 12 ≡ 1 (mod 3) なので、(2)から与式は p2 + 2p ≡ 1 - 1 ≡ 0 (mod 3)
- となり3の倍数となる。
- そのなかで素数は3のみだが、(1)から与式は3になることはないので、与式が素数となるpは存在しない。
- C) p≡2 (mod 3) のとき
- p2 ≡ 22 ≡ (-1)2 ≡ 1 (mod 3) なので、同様に与式は3の倍数となり、同じく与式が素数となるpは存在しない。
従って pq + qp = 17 ( p=2, q=3 または p=3, q=2 )
説明
素数というシンプルでやっかいな条件しかないので、どこから手を付けていいか迷うところですが、整数問題の典型的な解法を検討してみます。
王道の積の形にする解法は、素数という条件しかないので無理です。
範囲をしぼる解法も、対称式なので自分で大小関係を決めることができるものの、素数という条件だけでは不可能です。
そこで、倍数（約数）と余りに注目する方針とします。
まず、偶数か奇数かに注目すると、pとqは奇数と偶数の組み合わせしかありえないことが分かり、偶数の素数は2しかないので片方の値が確定します。素数となる偶数が2だけであることに注意しましょう。
次に3で割ったときの余りに注目すると、もう一方が3で割り切れない数になる場合は与式が3の倍数になってしまうため、もう一方は3の倍数で素数の3に確定できます。
解答例では合同式を使っていますが、合同式でなくても同じことをいえると思います。
合同式を使う場合は、同じ余りとなる数字で置き換えができる性質を利用して導きましょう。
「3で割ったとき2余る」は「3で割ったとき-1余る」と言い換えることができます。
22 ≡ (-1)2 ≡ 1 (mod 3) としましたが、 22 ≡ 4 ≡ 1 (mod 3) でも構いません。
なぜ2で割ったときと3で割ったときに注目したのか疑問に思う人もいると思いますが、2や3、4などで割ったとき（合同式では法といいますが）を使うことが多いので順番に検討しただけです。素数という条件しかないので、どの値を候補にするかのヒントはありません。場合によっては7などで割ったときも必要かもと思いながら解き進めています。
ただ平方数がでてきた時点で、平方数を3で割ったときまたは4で割ったときの性質を利用できるので、おそらく3で割ったときか4で割ったときで行けるだろうとも思いながら進めました。
ご質問は下の コメントを書く からお願いします。
