京大の問題解いた

2016-02-25

p^q + q^p と表される素数をすべて求めよ

答えは17だけ。

1.両方とも奇数の場合

となる。

奇数＋奇数 = 偶数のため、これは2で割りきれてしまう。

よって片方は偶数でなくてはならない。

偶数の素数は2しかないため、片方は2と決まる。

p = 2とする。

2.qについて考える。

q = 3のとき

2^3+3^2 = 17であり、素数である。

残りの数については、すべて3で割りきれてしまう。以下それを証明する。(適当だけど。)

2^(奇数) は 3で割ると余りが2となる。

この辺証明曖昧だけれど、

2 => 4 => 8 => 16 => 32 ... を3で割ると

1 => 2 => 1 => 2 => 1 .... と循環している。

modでやるんだ。書き方は忘れた。

素数^2 は 3で割ると余りが1となる。

素数は、3で割ると1か2が余る。

もし1の場合、mod3の世界だと

1×1 = 1となるので、素数を2乗したものも1で割れる。

もし2の場合、mod3の世界だと

2×2 = 1となるので、素数を2乗したものも1で割れる。

よって、その2つを足すと3で割れてしまう。

従って、p=2, q=3のみが正解となる。そのため正解は17のみ。

間違ってたら泣いて謝ります。