インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

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

463:Sondow素数

463は知られている最大のSondow素数です。Sondow素数は2, 5, 13, 37, 463の5つが知られています。

\displaystyle e=\sum_{k=0}^{\infty}\frac{1}{k!}
を有限項でちょん切って出来る有理数の分子を考えます:

\displaystyle N_n := \sum_{k=0}^n\frac{1}{k!}\text{の分子}

そうして、Sondowは何故かN_nN_{n+2}の最大公約数を考察しました:

R_n:=\mathrm{gcd}(N_n, N_{n+2})

この数列をR_0, R_1, R_2, \dotsと小さい順に眺めてみると、次のようになります:

1, 2, 5, \underbrace{1, \dots, 1}_7, 13, \underbrace{1, \dots, 1}_{23}, 37, \underbrace{1, \dots, 1}_{425}, 463, 1, 1, \dots,

1が多く現れますが、時々1でない数が出現することがわかります。そして、驚くべきことに、それらの1でない数は全て素数なのです!実際、Sondowは次の定理を証明しました:

定理 (Sondow) R_n \neq 1ならばR_nは素数である。

Sondowの定理の証明

実際には次のより精密な定理を証明します:

定理 素数全体のなす集合を\mathbb{P}とし、
\displaystyle \mathcal{A}:=\left\{ p \in \mathbb{P} \ \left| \ \sum_{k=0}^{p-1}(-1)^kk! \equiv 0 \pmod{p} \right\} \right.
とする。このとき、
\displaystyle R_n = \begin{cases}2 & n=1 \\ p & n=p-3, \ p \in \mathcal{A} \\ 1 & \text{otherwise} \end{cases}
が成り立つ。

自然数列\{ A_n\}

\displaystyle \sum_{k=0}^n\frac{1}{k!} = \frac{A_n}{n!}

で定義する。このA_nは漸化式

A_0=1, \ A_n = nA_{n-1}+1 \ (n \geq 1) ―①

で定まることは容易にわかる。また、

\displaystyle N_n = \frac{A_n}{\mathrm{gcd}(A_n, n!)} ―②

なる関係がある。

補題1 \ p \in \mathcal{A} \Longleftrightarrow p \mid A_{p-1}.

証明. 自然数nに対して

\displaystyle \sum_{k=0}^{n-1}(-1)^kk! \equiv A_{n-1} \pmod{n}

を示せばよい。これは次のように簡単に示される;

\begin{equation}\begin{split} A_{n-1} &= \sum_{k=0}^{n-1}\frac{(n-1)!}{k!} = \sum_{k=0}^{n-1}\frac{(n-1)!}{(n-1-k)!} \\ &= \sum_{k=0}^{n-1}(n-1)(n-2)\cdots (n-k) \\ &\equiv \sum_{k=0}^{n-1}(-1)^kk! \pmod{n} \end{split}\end{equation}
Q.E.D.
補題2 \ n>1, \ n+3 \nmid n! \Longrightarrow n+3は素数。

証明. n+3=ab \ (2 \leq a \leq b)とする。n > 1なので2b \leq n+3 < 2n+2。つまり、a \leq b \leq nがわかる。a < bならばn+3=ab \mid n!である。また、a=bであっても、a^2=n+3 > 4なのでa \geq 3であり、

0 \leq (a+1)(a-3)=a^2-2a-3=n-2a

であるから、a^2=n+3 \mid n!となる。これで対偶が証明された。 Q.E.D.

定理の証明. N_0=1, N_1=2, N_2=5, N_3=8より、R_0=1, R_1=2は直接確認できる。n > 1としよう。漸化式①を二回用いることにより

A_{n+2} = (n+2)(n+1)A_n+(n+3) ―③

が得られる。R_n \neq 1と仮定する。R_nの定義からR_n \mid A_n, A_{n+2}がいえる。よって、③よりR_n \mid n+3を得る。一方、R_n \neq 1なのでR_nの素因数pを取ることができる。このpN_nの素因数でもあるが、②からp \nmid n!がわかる。つまり、R_n \nmid n!なのでn+3 \nmid n!もいえる。従って、補題2からn+3は素数である。p \mid R_n \mid n+3なのでp=n+3である。また、p \mid R_n \mid A_{n+2}および補題1からp \in \mathcal{A}が成り立つ。
R_n=1になるのが"otherwise"であるためには逆も示す必要がある。つまり、奇素数p \in \mathcal{A}に対してR_{p-3}=pを示す。n:=p-3としよう。補題1よりp \mid A_{n+2}なので、③よりp \mid A_nが従う。一方、p > nよりp \nmid n!。よって、②よりp \mid N_n、従ってp \mid R_nとなる。R_n \neq 1ならばR_nが素数であることは前半で既に証明できているので、R_n = pが従う。 Q.E.D.

Sondow素数の無限性

463 < n \leq 1.5\times 10^8に対してR_n=1であることが確認されていますが、Sondow素数は無数に存在すると期待されます:

予想 Sondow素数は無数に存在する。

Heuristicな議論.

\displaystyle \sum_{k=0}^{p-1}(-1)^kk! \pmod{p}

がランダムに分布すると仮定すると、この数がpで割り切れる確率は1/pである。また、各素数毎の事象が独立であることを仮定することによって、期待値は

\displaystyle \#\mathcal{A}_{\leq x} ≒ \sum_{p \leq x}\frac{1}{p}

と見積もることができ、これはMertensの第二定理
integers.hatenablog.com
によって\log \logオーダーで成長し、特にx \to \inftyで発散する。

さて、

\displaystyle \sum_{463 < p \leq 1.5\times 10^8}\frac{1}{p} ≒ 1.12 > 1

なので、そろそろ6つ目のSondow素数が発見されてもおかしくありません!

6つ目のSondow素数を発見するのはあなたかもしれません。