Thu Feb 25 22:49:59 JST 2016

京都大学 2016 文系 数学問題[2]

https://twitter.com/yuya_lz/status/702767994053615616/photo/1

素数 \(p,q\) によって表される数 \(p^q+q^p\) が素数であるような \((p,q)\) の組み合わせを求めよ.

解

実際に実験をすると予想が立ってしまう:

require 'prime'

N=1000
Prime.each(N) {|q1|
  Prime.each(N) {|q2|
    r = q1**q2 + q2**q1
    if r.prime?
      p [q1,q2]
    end
  }
}

\(p,q\) が共に奇数、即ち3以上の素数である場合、 \(p^q+q^p\) が偶数だし、2よりは大きそうだからダメだとすぐに分かる. 従ってどちらか一方は2で、\(p=2\) とする. \(p^q+q^p = 2^q + q^2\).

でまあ、これも、実験して分かったことなんだけど、 \(q\) が3の倍数ではない素数のとき、 \(2^q+q^2\) は3の倍数である.

\(2^q\) の3の剰余というのは、 \(q=1,2,3,4,5,...\) について、 \(2^q \bmod 3=2,1,2,1,...\) であること、 \(q\) を奇数に限ると \(2^q \bmod 3=2,2,2...\) であることはすぐ分かる.

q=3n+1

\(q\) が \(3n+1\) で表せる素数のとき、 \((2^q) \bmod 3=2\) である.

\((2^q+q^2) \bmod 3 = (2 + (3n+1)^2) \bmod 3=0\)

であるので、\(q\) がそういう素数ならば、それは3の倍数であるので、素数ではない (もちろん3自体ではないことは言わないといけないが).

q=3n+2

全く同様に、\(q\) がこういう形の素数ならば、 \((2^q) \bmod 3=2\) であって \((2^q+q^2) \bmod 3 = (2 + (3n+2)^2) \bmod 3=0\) で、やっぱり3の倍数である. 3ではないので合成数である.

q=3n

\(q\) が \(3n\) で表される素数であるならば、\(q=3\) である. 実際に計算することで、\(2^q+q^2\) が素数であることが言える.