INTEGERS

数、特に整数に関する記事。

６より大きい任意の整数は相異なる素数の和として表すことができる

整数整数-6

$6$ は相異なる素数の和としては表すことができません。一方、次の定理が成り立ちます：

定理 (Richert, 1949) $6$ より大きい任意の整数は相異なる素数の有限個の和として表すことができる。

証明. 素数は無数に存在するので、次の主張を示せば十分。 $p_k$ で小さい方から数えて $k$ 番目の素数を表す：

主張任意の $5$ 以上の整数 $k$ に対して在る自然数 $s_k$ が存在し、区間 $[7, s_k+6]$ にある連続する $s_k$ 個の整数は全て $p_1, p_2, \dots, p_k$ を用いた相異なる素数の和として表され、 $s_k \geq p_{k+1}$ を満たす。

この主張を $k$ に関する数学的帰納法で証明する。

$k=5$ のとき
$s_5=13$ とできる。実際、 $p_1=2, p_2=3, p_3=5, p_4=7, p_5=11, p_6=13$ であり、

$\begin{align}7&=7 \\ 8&=3+5 \\ 9&= 2+7 \\ 10&= 3+7 \\ 11 &=11 \\ 12 &= 5+7 \\ 13&=2+11 \\ 14 &= 3+11 \\ 15 &= 3+5+7 \\ 16 &= 5+11 \\ 17 &= 2+3+5+7 \\ 18&=7+11 \\ 19 &=3+5+11\end{align}$

$s_5 = 13 \geq 13=p_6$

であることから確認できる。

$k \geq 6$ として、 $k-1$ のときに成立すると仮定する。

このとき、題意を満たすような $s_{k-1}$ が存在する。そうして、

$s_k := s_{k-1} + p_k$

によって、 $s_k$ を定める。 $[7, s_k+6]$ の元 $x$ を任意にとる。

$x \in [7, s_{k-1}+6]$ ならば帰納法の仮定によって、 $x$ は $p_1, \dots, p_{k-1}$ を用いた相異なる有限個の素数の和として表される。

$x\in [s_{k-1}+7, s_k+6]$ ならば $y \in [7, s_{k-1}+6]$ が存在して、 $x=y+p_k$ と書けるので、再び $y$ に対する帰納法の仮定から $x$ は $p_1, \dots, p_k$ を用いた相異なる有限個の素数の和として表されることがわかる。

最後に、帰納法の仮定より、

$s_k = s_{k-1}+p_k \geq 2p_k$

であるが、Bertrandの仮説より $2p_k \geq p_{k+1}$ が成り立つので、

$s_k\geq p_{k+1}$

を得る。すなわち、 $k$ のときも成立することが示された。

こうして、数学的帰納法によって主張が証明されたので、Richertの定理も示された。
Q.E.D.

Grahamの定理の証明において「数列の半完全性」が重要になりますが、Richertの定理は「素数のなす数列は半完全である」と表現することができます。