イバコの生存記録

いまは競プロ(AtCoder)記事がメインです。

30. q-p, r-p, r-q が全て素数となる素数組 (p, q, r) を全て求めよ

いい頭の体操になる問題です。

 

問題

p,q,r素数とする。q-p,r-p,r-q が全て素数となるような (p,q,r) を全て求めよ。

 

考え方

まず、差に関する条件から p \lt q \lt r となります。

この条件で少し考えてみると、(2,5,7) という組が思い付きます。素数の組で、差はそれぞれ 3, 5, 2 で全て素数です。これ以外に条件を満たす素数組が存在するのか、という所がこの問題の肝となってきます。

2以外の素数は奇数であり、奇数同士の差は偶数となります。素数に関して p \lt q \lt r なので、全て奇数なら r-p は4以上の偶数となり、素数になりません。よって、少なくとも1つが偶数なので、p=2 は確定です。また、残った q,r は奇数となりますが、こちらも r-q が偶数かつ素数、つまり2である必要があります。よって、r=q+2 であることが確定します。

ここまでの考察で、条件を満たす素数組は (2,q,q+2) であることが分かりました。

 

この条件で、具体例を少し考えてみましょう。

(p,q,r)(q-p,r-p,r-q) について、

  • (2,5,7) → (3,5,2)
  • (2,11,13) → (9,11,2)
  • (2,17,19) → (15,17,2)
  • (2,29,31) → (27,29,2)
  • (2,41,43) → (39,41,2)

…と、(2,5,7) 以外の組では q-p素数にならなさそうです。さらに言えば、3の倍数になりそうに見えます。

ここから、q を mod 3 で分類することを考えてみます。すると、q-p が必ず3の倍数になることを示せて、条件を満たす素数組はただ1つだけ存在することが分かります。

以上の考察を答案としてまとめてみましょう。

 

答案

差に関する条件から、p \lt q \lt r である。

p,q,r が全て奇数なら、p \lt p+2 \le q \lt q+2 \le r なので、r-p \ge 4 となる。また、r-p は奇数と奇数の差なので偶数となる。よって、r-p は4以上の偶数となり素数ではない。即ち、p=2 であることが必要。

また、q,r は奇数となるので、r-q は偶数となる。よって、r-q素数となるには r=q+2 であることが必要。

以下、(2,q,q+2)素数組で考える。ある自然数 n を用いて q=3n または 3n+1 または 3n+2 と表せる。

 

q=3n の場合

q素数であることから、n=1 であることが必要。すると (p,q,r)=(2,3,5) となるが、q-p=1素数では無いので不適。

 

q=3n+1 の場合

r = q+2 = 3(n+1) となり、これは素数では無いので不適。

 

q=3n+2 の場合

q-p = q-2 = 3n となり、これが素数となるには n=1 が必要。また、このとき (p,q,r)=(2,5,7) であり、この素数組は差の条件を全て満たすので適切。

 

以上より、求める素数組は (p,q,r)=(2,5,7) のみ。