素数とはA～Zで見つけられる数である(証明編)

整数整数-26

$26$ はアルファベットの文字数である。

相互リンクサイト『素数に恋する女』の最新記事
p.1yen.jp
に登場する有名な素数公式

定理１ (Jones-Sato-Wada-Wiens, 1976) ( $26$ 変数 $25$ 次)多項式

$\begin{align}&(k+2)(1 - (wz+h+j-q)^2 - ( (gk+2g+k+1)(h+j)+h-z)^2\\ &- (2n+p+q+z-e)^2 - (16(k+1)^3(k+2)(n+1)^2+1-f^2)^2\\ &- (e^3(e+2)(a+1)^2+1-o^2)^2- ( (a^2-1)y^2+1-x^2)^2\\ &- (16r^2y^4(a^2-1)+1-u^2)^2 - ( ( (a+u^2(u^2-a) )^2 -1)(n+4dy)^2 + 1 \\ &- (x+cu)^2)^2 - (n+l+v-y)^2 - ( (a^2-1)l^2+1-m^2)^2 - (ai+k+1-l-i)^2 \\ &- (p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m)^2 - (q+y(a-p-1)\\ &+s(2ap+2a-p^2-2p-2)-x)^2 - (z+pl(a-p)+t(2ap-p^2-1)-pm)^2 )\end{align}$

の変数に非負整数を代入して得られる値全体のなす集合と正の整数全体のなす集合の共通部分は素数全体集合に一致する。

の証明を紹介します(上記サイトでは値を実際に計算できるExcelファイルをダウンロードできます。そして、負の数ばっかりに出会うことができるでしょう(笑))。

任意の非負整数点で素数を返すような定数でない複素係数多項式が存在しないことが証明されていますが、上記定理のように「正の値のときのみを考える」という制限をつけることによって素数を表現するような多項式が存在することを証明できます(これはHilbertの第10問題を解決したMatijasevicが本質的に示しています*1 )。

そのような具体的な素数表現多項式としてどのようなものがあるか？、変数および次数はどのようなものが取れるか？ということが気になりますが、

J. P. Jones, D. Sato, H. Wada, D. Wiens, Diophantine representation of the set of prime numbers, Amer. Math. Monthly, 83 (1976) 449-464.

で発表された多項式(上述の定理のもの)が最も有名なものだと思われます*2。

$26$ 変数なので、多項式がアルファベット全てを用いて表されていることについては「そすこい」を見て始めて気づきました。

この論文で証明しているのはこの定理だけではないですが、とりあえずこの定理の証明を紹介しましょう(原論文ではDavisの論文を引用して証明を省略している部分があるので(命題１)、その点についてはこの記事をまとめた価値があると思います)。

Pell方程式に関する補題群から始めます。Pell方程式の一般論(補題１)だけこの記事では証明をつけていません。例えば高木貞治『初等整数論講義』で勉強できる気がします(難しくないですが二次体論や連分数論が関係します)。

補題１ $a$ を $2$ 以上の整数とする。Pell方程式

$x^2-(a^2-1)y^2=1$

の一般解 $(x_a(n), y_a(n))$ は漸化式

$\begin{align}&x_a(0)=1, \ x_a(1)=a, \ x_a(n+2)=2ax_a(n+1)-x_a(n),\\ &y_a(0)=0, \ y_a(1)=1,\ y_a(n+2)=2ay_a(n+1)-y_a(n)\end{align}$

で与えられる。一般項は

$\begin{align}x_a(n) &= \frac{(a+\sqrt{a^2-1})^n+(a-\sqrt{a^2-1})^n}{2}, \\ y_a(n) &= \frac{(a+\sqrt{a^2-1})^n-(a-\sqrt{a^2-1})^n}{2\sqrt{a^2-1}}.\end{align}$

ただし、(この記事では)解は非負整数解のみを考える。

証明. $(a, 1)$ が最小非自明解であることは容易に確認できるので、Pell方程式の一般論
mathtrain.jp
の定理２よりわかる。 Q.E.D.

補題２ 非負整数 $m, n$ に対して

$\begin{align}x_a(m\pm n) &= x_a(m)x_a(n)\pm (a^2-1)y_a(m)y_a(n), \\ y_a(m \pm n)&=x_a(n)y_a(m)\pm x_a(m)y_a(n)\end{align}$

が成り立つ*3(複合同順)。

証明. 一般項より容易に確認出来る。 Q.E.D.

以下幾つかの補題において $n=0$ を含めても「自明」とか「便宜的」に扱えば良いですが、気持ち悪い場合は $n \geq 1$ として読んでください( $n$ は勿論整数。 $a$ についても $a=1$ で上手くいくものと上手くいかないものがある)。

補題３ $x_a(n)$ および $y_a(n)$ は $n$ に関して狭義単調増加である。また、 $n+y_a(n-1) \leq y_a(n)$ が成り立つ。

証明. 単調増加であることは、補題２より

$x_a(n+1)=ax_a(n)+(a^2-1)y_a(n), \ \ y_a(n+1) = ay_a(n)+x_a(n)$

が成り立つことよりわかる。後半は $y_a(n)$ の漸化式を

$y_a(n+1)-y_a(n) = y_a(n)-y_a(n-1)+(2a-2)y_a(n)$

と変形してやることにより、帰納法で示せる。 Q.E.D.

補題４ $x_a(n)$ と $y_a(n)$ は互いに素である。

証明. Pell方程式の形からすぐわかる。 Q.E.D.

補題５ $m$ が $n$ の倍数であれば $y_a(m)$ は $y_a(n)$ の倍数である。

証明. 補題２より

$y_a(n(k+1)) = x_a(n)y_a(nk)+x_a(nk)y_a(n)$

なので、 $k$ に関する帰納法で証明できる。 Q.E.D.

補題６ $y_a(m)$ が $y_a(n)$ の倍数となるための必要十分条件は $m$ が $n$ の倍数となることである。

証明. 補題５より $\Longleftarrow$ はOK。 $\Longrightarrow$ を示すために、 $y_a(m)$ は $y_a(n)$ の倍数であるが、 $m$ は $n$ で割り切れないと仮定する。このとき、 $m=nq+r, \ (0 < r < n)$ を満たすような非負整数 $r, q$ が存在する。すると、補題２より

$y_a(m) = x_a(r)y_a(nq)+x_a(nq)y_a(r)$

が成り立つ。補題５より $y_a(n)$ は $y_a(nq)$ を割り切るので、 $y_a(n) \mid x_a(nq)y_a(r)$ 。補題４、５より $y_a(n)$ と $x_a(nq)$ は互いに素なので、 $y_a(n) \mid y_a(r)$ を得る。これは $y_a(n)$ が $n$ について狭義単調増加であることに反する。Q.E.D.

補題７ $k$ を正整数とする。このとき、

$y_a(nk) \equiv kx_a(n)^{k-1}y_a(n) \pmod{y_a(n)^3}$

が成り立つ。

証明. 一般項の公式を用いることにより

$\begin{align}x_a(nk)+y_a(nk)\sqrt{a^2-1} &= (a+\sqrt{a^2-1})^{nk} = (x_a(n)+y_a(n)\sqrt{a^2-1})^k \\ &= \sum_{j=0}^k \binom{k}{j}x_a(n)^{k-j}y_a(n)^j(a^2-1)^{\frac{j}{2}}\end{align}$

と計算できる。よって、 $\sqrt{a^2-1}$ の係数を比較することにより

$\displaystyle y_a(nk) = \sum_{j=1, \ j:\text{奇数}}^k\binom{k}{j}x_a(n)^{k-j}y_a(n)^j(a^2-1)^{\frac{j-1}{2}}$

を得る(この式には整数しか現れない)。 $j > 1$ の項は全て $y_a(n)^3$ の倍数なので所望の結果が得られる。 Q.E.D.

補題８ $y_a(n)^2$ が $y_a(m)$ を割り切れば $y_a(n)$ は $m$ を割り切る。

証明. まず補題６より $m$ は $n$ の倍数であることが従う。そこで、 $m=nk$ とおこう( $k$ は正の整数)。すると、補題７より

$y_a(n)^2 \mid kx_a(n)^{k-1}y_a(n)$

が言える。すなわち、 $y_a(n) \mid kx_a(n)^{k-1}$ 。よって、補題４より $y_a(n) \mid k$ 。 $k$ は $m$ を割り切るので主張が言えた。 Q.E.D.

補題９ $\ \ \ y_a(n) \equiv n \pmod{a-1}$ が成り立つ。

証明. 数学的帰納法。 Q.E.D.

補題１０ $a, b, k$ を $2$ 以上の整数とする。 $a \equiv b \pmod{k}$ ならば、任意の $n$ に対して

$x_a(n) \equiv x_b(n) \pmod{k}, \ \ y_a(n) \equiv y_b(n) \pmod{k}$

が成り立つ。

証明. 数学的帰納法。 Q.E.D.

補題１１*4 $n$ のパリティと $y_a(n)$ のパリティは一致する。

証明. 漸化式より $y_a(n+2) \equiv y_a(n) \pmod{2}$ なので数学的帰納法で示せる。 Q.E.D.

誠に遺憾ではありますが、この記事では原論文に従って $p$ は素数を表す記号としては用いません(怒)。

補題１２ $p, n$ を正の整数とする。このとき、合同式

$x_a(n) \equiv p^n + y_a(n)(a-p) \pmod{2ap-p^2-1}$

が成り立つ。また、 $0 < p^n < a$ なる状況下では、合同式の左辺 ≥ 右辺である。

証明. 合同式は数学的帰納法で示せる。 $0 < p^n < a$ のときを考える。 $n=1$ のときは左辺と右辺は一致するので、 $n \geq 2$ とする。一般項の公式から、 $\sqrt{a^2-1}y_a(n) < x_a(n)$ が成り立つので、

$p^n+y_a(n)(a-p) \leq a-1+y_a(n)(a-1) < \sqrt{a^2-1}y_a(n) < x_a(n)$

と評価できる。ここで、二番目の不等号は

$\displaystyle (a-1)\left( 1+\frac{1}{y} \right) \leq (a-1)\left( 1+\frac{1}{2a} \right) < a-\frac{1}{2} < \sqrt{a^2-1}$

からわかる。 Q.E.D.

補題１３ $\ \ \ (2a-1)^n \leq y_a(n+1) \leq (2a)^{n}$ が成り立つ。

証明. 数学的帰納法。実際、 $y_a(n+1)=2ay_a(n)-y_a(n-1) < 2a\cdot (2a)^{n-1}=(2a)^n$ および $y_a(n+1)=2ay_a(n)-y_a(n-1) > (2a-1)y_a(n) \geq (2a-1)^n$ を得る。Q.E.D.

補題１４ 合同式 $x_a(2n\pm m) \equiv -x_a(m) \pmod{x_a(n)}$ が成り立つ。

証明. 補題２を用いて次のように計算できる：

$\begin{align}x_a(2n\pm m) &= x_a(n)x_a(n\pm m) + (a^2-1)y_a(n)y_a(n\pm m) \\ &\equiv (a^2-1)y_a(n)(y_a(n)x_a(m)\pm x_a(n)y_a(m) ) \pmod{x_a(n)} \\ &\equiv (a^2-1)y_a(n)^2x_a(m) \\ &= (x_a(n)^2-1)x_a(m) \\ &\equiv -x_a(m) \pmod{x_a(n)}.\end{align}$

Q.E.D.

補題１５ 合同式 $x_a(4n\pm m) \equiv x_a(m) \pmod{x_a(n)}$ が成り立つ。

証明. 補題１４より

$x_a(4n\pm m) \equiv -x_a(2n \pm m) \equiv x_a(m) \pmod{x_a(n)}$ .

Q.E.D.

補題１６ $n \geq 1$ とし、 $i, j$ を $i \leq j \leq 2n$ を満たすような非負整数とする。このとき、 $a=2, \ n=1, \ i=0, \ j=2$ なる例外ケースを除いて $x_a(i)\equiv x_a(j) \pmod{x_a(n)}$ が成り立つならば $i=j$ が成立する。

証明. $x_a(n)$ が奇数のとき:

$q=(x_a(n)-1)/2$ とおく。すると、

$\{-q, -q+1, \dots, -1, 0, 1, \dots, q-1, q\}$

は $\bmod{x_a(n)}$ の完全代表系をなす。補題３より

$1=x_a(0) < x_a(1) < \cdots < x_a(n-1)$

であり、補題２から $x_a(n) = ax_a(n-1)+(a^2-1)y_a(n-1)$ なので

$\displaystyle x_a(n-1) \leq \frac{x_a(n)}{a} \leq \frac{1}{2}x_a(n),$

すなわち、 $x_a(n-1) \leq q$ が成り立つ。また、 $x_a(n+1), x_a(n+2), \dots, x_a(2n)$ はそれぞれ

$\color{red}{(}-q \leq \color{red}{)} -x_a(n-1) < -x_a(n-2) < \cdots < -x_a(1) < -x_a(0)=-1$

と合同である(補題１４よりわかる)。以上より、 $x_a(0), \dots, x_a(2n)$ は $\bmod{x_a(n)}$ で全て互いに合同ではない。

$x_a(n)$ が偶数のとき:

今度は $q=x_a(n)/2$ とおく。このときは

$\{-q+1, -q+2, \dots, -1, 0, 1, \dots, q-1, q\}$

が $\bmod{x_a(n)}$ の完全代表系をなす。奇数のときと同じく $x_a(n-1) \leq q$ は成立( $q$ の定義が変わっていることに注意)。従って、 $x_a(n-1)=x_a(n)/2=q$ でない限り奇数のケースと同様に $x_a(0), \dots, x_a(2n)$ は全て $\bmod{x_a(n)}$ で互いに非合同となる。

さて、 $x_a(n) = 2x_a(n-1)$ が成り立ったと仮定しよう。補題２からわかる

$x_a(n) = ax_a(n-1)+(a^2-1)y_a(n-1)$

と比較すれば、この状況になるのは $a=2, y_a(n-1)=0$ のときで、 $n=1$ に限る。 $x_2(0)=1, x_2(1)=2, x_2(2)=7$ なので、 $i=0, \ j=2$ のときに

$x_a(i) \equiv x_a(j) \pmod{x_a(n)}$

となることがわかる。 Q.E.D.

補題１７ 非負整数 $i, j, n$ であって $0 < i \leq n, \ 0 \leq j < 4n$ なるものを考える。このとき、 $x_a(j) \equiv x_a(i) \pmod{x_a(n)}$ が成り立つならば $j=i$ または $j=4n-i$ が成り立つ。

証明. $j \leq 2n$ のとき:
補題１６より例外ケースでなければ $j=i$ が言える。しかし、今は $i > 0$ なので、例外ケースとなるのは $i=2, \ j=0, n=1$ のときのみ。これは $i \leq n$ に反する。

$j > 2n$ のとき:
$j':=4n-j$ とする。すると、 $0 < j' < 2n$ が成り立つ。補題１５より

$x_a(j') \equiv x_a(j) \pmod{x_a(n)}$

が成り立つ。よって、補題１６より例外ケースでなければ $j'=i$ が従う。 $i, \ j' > 0$ なので例外ケースは起こりえない。 Q.E.D.

補題１８ $0 < i \leq n$ 、 $x_a(j) \equiv x_a(i) \pmod{x_a(n)}$ ならば $j \equiv \pm i \pmod{4n}$ が成り立つ。

証明. $j$ を $4n$ で割って、 $j=4nq+j', \ (0 \leq j' < 4n)$ と表す。このとき、補題１５より

$x_a(i) \equiv x_a(j) \equiv x_a(j') \pmod{x_a(n)}$

が成り立つ。よって、補題１７より $i=j'$ または $i=4n-j'$ が成り立つ。こうして、

$j \equiv j' \equiv \pm i \pmod{4n}$

が得られる。 Q.E.D.

よくやるように、 $\Box$ は完全平方数を表す記号として用います。

補題１９ $2$ 以上の整数 $e$ と非負整数 $n$ が

$e^3(e+2)(n+1)^2+1=\Box \tag{1}$

を満たすならば、 $e-1+e^{e-2} \leq n$ が成り立つ。また、任意の正の整数 $e, t$ が与えられたとき、(1)が成り立つような非負整数 $n$ であって、 $t \mid n+1$ なるものが存在する。

証明. $a=e+1$ とおくと、(1)は

$(a^2-1)(a-1)^2(n+1)^2+1 = \Box$

となるので、補題１のPell方程式が $y=(a-1)(n+1)$ なる解を持つことがわかる。すなわち、ある非負整数 $j$ が存在して $(a-1)(n+1)=y_a(j)$ が成り立つ。このとき、補題９より $a-1 \mid j$ 。明らかに $j \neq 0$ なので $j \geq a-1$ である。従って、補題１３より

$(a-2)(a-1)+(a-1)^{a-2} < (2a-1)^{a-2} \leq y_a(a-1) \leq y_a(j) =(a-1)(n+1)$

を得る(最初の不等式は例えば $(a-2)(a-1) < a^{a-2}$ から分かる)。両辺を $a-1$ で割ることにより、

$(a-2)+(a-1)^{a-3} < n+1,$

すなわち、 $e-1+e^{e-2} \leq n$ を得る。

後半を示す。任意の正の整数 $e, t$ が与えられたとき、 $a=e+1$ と置いてPell方程式 $x^2-Ay^2=1$ を考える。ここで、 $A=(a^2-1)(a-1)^2t^2 \neq \Box$ 。Pell方程式は常に非自明解を持つので(一般論)、所望の $n$ の存在がわかる。 Q.E.D.

この不等式は後で大活躍します。

命題１ 非負整数 $a, n, y$ (ただし、 $a \geq 2, \ n \geq 1$ )に対して、 $y=y_a(n)$ が成り立つための必要十分条件は非負整数 $b, c, d, r, s, t, u, v, x$ が存在して

(Ⅰ) $x^2=(a^2-1)y^2+1,\ \$ (Ⅱ) $u^2=(a^2-1)v^2+1$ ,
(Ⅲ) $s^2=(b^2-1)t^2+1,\$ (Ⅳ) $v=4ry^2$ ,
(Ⅴ) $b=a+u^2(u^2-a),\ \$ (Ⅵ) $s=x+cu$ ,
(Ⅶ) $t=n+4dy,\ \ \ \ \ \ \ \ \ \ \ \$ (Ⅷ) $n \leq y$

が成り立つことである。

証明. $\Longleftarrow$ の証明:
(Ⅰ)〜(Ⅷ)を満たすような非負整数 $b, c, d, r, s, t, u, v, x$ が存在したと仮定する。最初に $v > 0$ を確認する。 $v=0$ だと仮定しよう。すると、(Ⅱ)より $u=1$ 。(Ⅴ)より $b=1$ 。(Ⅲ)より $s=1$ 。(Ⅵ)より $x \leq 1$ となるが、(Ⅰ)より $x \geq 1$ なので $x=1$ 。よって、(Ⅰ)より $y=0$ となって、(Ⅷ)と $n \geq 1$ の仮定に矛盾する。よって、 $v > 0$ が示された。

(Ⅰ)、(Ⅱ)、(Ⅲ)、補題１、 $y, \ v, \ t \geq 1$ から、 $i, \ j, \ k \geq 1$ が存在して

$\begin{align} &x=x_a(i), \ \ y=y_a(i) \\ &u=x_a(k), \ \ v=y_a(k) \\ &s=x_b(j), \ \ t=y_b(j)\end{align}$

が成り立つ。示すべきことは $i=n$ 。

(Ⅳ)より $y \leq v$ なので、補題３より $i \leq k$ 。

(Ⅴ)より $b \equiv a \pmod{u}$ 、すなわち

$b \equiv a \pmod{x_a(k)}$ .

補題１０より

$x_b(j) \equiv x_a(j) \pmod{x_a(k)}$ .

(Ⅵ)より $s \equiv x \pmod{u}$ 、すなわち

$x_b(j) \equiv x_a(i) \pmod{x_a(k)}$ .

合わせると

$x_a(i) \equiv x_a(j) \pmod{x_a(k)}$

が成立する。よって、補題１８より

$j \equiv \pm i \pmod{4k}$ .

(IⅤ)より $y^2 \mid v$ 。すなわち、 $y_a(i)^2 \mid y_a(k)$ 。すると、補題８より

$y_a(i) \mid k$

が得られる。よって、

$j \equiv \pm i \pmod{4y_a(i)}$ .

(Ⅱ)、(Ⅳ)、(Ⅴ)より $b \equiv 1 \pmod{4y}$ が言えるので、補題９と合わせると

$y_b(j) \equiv j \pmod{4y_a(i)}$ .

また、(Ⅶ)より $t \equiv n \pmod{4y}$ 、すなわち

$y_b(j) \equiv n \pmod{4y_a(i)}$

なので、結局

$n \equiv \pm i \pmod{4y_a(i)}$

が示されたことになる。

(Ⅷ)より $0 < n \leq y_a(i)$ 、補題３より $0 < i \leq y_a(i)$ であることに注意すれば、 $i = n$ でなければならないことがわかる。

以上で、 $y=y_a(i) = y_a(n)$ の証明が完了する。

$\Longrightarrow$ の証明:
$y=y_a(n)$ と仮定する。 $x=x_a(n)$ とすれば(Ⅰ)が成立。

$m=4ny_a(n), \ u=x_a(m), \ v=y_a(m)$ とおく。すると、補題１より(Ⅱ)が満たされる。

補題７より $y_a(ny_a(n))$ は $y^2$ で割り切れる。また、補題２より正整数 $N$ に対して $y_a(2N)=2x_a(N)y_a(N)$ が成り立つので、 $y_a(4N)=4x_a(2N)x_a(N)y_a(N)$ . $N=ny_a(n)$ として適用することによって $v=y_a(m)$ は $4y^2$ で割り切れることがわかる。すなわち、(Ⅳ)を満たす正整数 $r$ が存在することがわかった。

$b:=a+u^2(u^2-a)$ とすれば当然(Ⅴ)が成立する。 $s:=x_b(n), \ t:=y_b(n)$ とすれば補題１より(Ⅲ)が成立。

$b \geq a$ より $s=x_b(n) \geq x_a(n)=x$ が成り立つ(添字部分に関する単調性は一般項の公式からわかる*5 )。また、(Ⅴ)より $b \equiv a \pmod{u}$ なので、補題１０より $s \equiv x \pmod{u}$ である。以上により(Ⅵ)を満たす非負整数 $c$ の存在がわかる。

補題３より $t=y_b(n) \geq n$ 。補題９より $t \equiv n \pmod{b-1}$ 。(Ⅱ)、(Ⅳ)、(Ⅴ)より $b\equiv 1 \pmod{4y}$ なのだから $t \equiv n \pmod{4y}$ 。すなわち、(Ⅶ)を満たす非負整数 $d$ が存在する。(Ⅷ)は補題３からわかる。 Q.E.D.

系１非負整数 $a, n, y$ (ただし、 $a \geq 2, \ n \geq 1$ )に対して、 $y=y_a(n)$ が成り立つための必要十分条件は非負整数 $c, d, r, u, x$ が存在して

(Ⅰ) $x^2=(a^2-1)y^2+1,\ \$ (Ⅱ) $u^2=16(a^2-1)r^2y^4+1$
(Ⅲ) $(x+cu)^2=( (a+u^2(u^2-a) )^2-1)(n+4dy)^2+1,\$ (Ⅳ) $n\leq y$

が成り立つことである。

証明. 命題１の条件式において、 $v, b, s, t$ を消去すればよい。 Q.E.D.

補題２０ 正の整数 $q$ および $0 \leq \alpha < 1/q$ を満たす実数 $\alpha$ に対して、不等式 $0 < 1-q\alpha \leq (1-\alpha)^q$ が成り立つ。

証明. これは、Bernoulliの不等式よりわかる：
mathtrain.jp
Q.E.D.

補題２１ $0 \leq \alpha \leq 1/2$ なる実数 $\alpha$ に対して、不等式 $(1-\alpha)^{-1} \leq 1+2\alpha$ が成り立つ。

証明. 自明。 Q.E.D.

素数である事の必要十分条件の出発点はWilsonの定理に頼ります：

Wilsonの定理 $k$ を正の整数とする。このとき、 $k+1$ が素数であるための必要十分条件は $k+1$ が $k!+1$ を割り切ることである。

証明. 有名定理(当ブログでは2015の階乗を10の502乗で割った数の一の位は？ - INTEGERSで $\Longrightarrow$ を証明しています)。 $\Longleftarrow$ の証明は容易(対偶を取ればよい)。 Q.E.D.

最終的に多項式に向かうにあたって、階乗を消すのに次の補題が決定的に重要な役割を果たします：

補題２２ $k, n, p$ を正の整数とする。 $(2k)^k \leq n$ および $n^k < p$ が成り立つならば、

$\displaystyle k! < \frac{(n+1)^kp^k}{r( (p+1)^n, p^{k+1})} < k!+1$

が成り立つ。ただし、 $r(a, b)$ は $a$ を $b$ で割った余りを表す記号とする。

証明. 仮定より $k < n$ であることに注意して、二項定理より

$\displaystyle (p+1)^n = \sum_{i=0}^k\binom{n}{i}p^i + p^{k+1}\sum_{i=k+1}^n\binom{n}{i}p^{i-k-1} \tag{2}$

ここで

$(np)^{k+1}-1 = n^k(p^{k+1}n)-1 \leq (p-1)p^{k+1}n-1 < p^{k+2}n-p^{k+1} = (np-1)p^{k+1}$

なので、

$\displaystyle \sum_{i=0}^k\binom{n}{i}p^i \leq \sum_{l=0}^kn^ip^i = \frac{(np)^{k+1}-1}{np-1} < p^{k+1} \tag{3}$

を得る。(2)、(3)は

$\displaystyle r( (p+1)^n, p^{k+1}) = \sum_{i=0}^k \binom{n}{i}p^i \neq 0$

であることを意味している。

$\begin{align}k!\sum_{i=0}^k\binom{n}{i}p^i &\leq k!\left( k\binom{n}{k-1}p^{k-1}+\binom{n}{k}p^k \right) \leq k!\left( \frac{kn^{k-1}}{(k-1)!}p^{k-1}+\frac{n^k}{k!}p^k \right)\\&= k^2n^{k-1}p^{k-1}+n^kp^k < (k+n^k)p^k \ \ \ \ \ \ \ \ \ \ \ (kn^{k-1} < n^k < p \ \text{を用いた})\\ &\leq (1+n)^kp^k\end{align}$

より、後は

$\displaystyle (k!+1)\sum_{i=0}^k\binom{n}{i}p^i > (n+1)^kp^k$

を示せばよい。

$\displaystyle \sum_{i=0}^k\binom{n}{i}p^i > \binom{n}{k}p^k$

なので、

$\displaystyle (k!+1)\binom{n}{k} > (n+1)^k$

に帰着される。これは次のようにして示される：

$\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots (n-k+1)}{k!} > \frac{(n-k+1)^k}{k!}$

より、

$\begin{align} \frac{(n+1)^k}{\binom{n}{k}}&< \frac{k!}{\frac{(n-k+1)^k}{(n+1)^k}} = \frac{k!}{\left( 1-\frac{k}{n+1}\right)^k} < \frac{k!}{\left( 1-\frac{k}{n}\right)^k} \\ &\leq k!\left( 1-\frac{k^2}{n}\right)^{-1} \ \ \ \ \ \ \ \ \ \ (\text{補題２０より}) \\ &\leq k! \left( 1+\frac{2k^2}{n} \right) \ \ \ \ \ \ \ \ \ \ (\text{補題２１より}) \\ &\leq k!\left( 1+\frac{2k^2}{(2k)^k}\right) \ \ \ \ \ \ \ \ \ \ (\text{仮定より}) \\ &\leq k!\left( 1+\frac{1}{k!} \right) = k!+1. \end{align}$

Q.E.D.

命題２ 任意の正の整数 $k, f$ に対して、 $f=k!$ となるための必要十分条件は非負整数 $j, h, n, p, q, w, z$ が存在して

(Ⅰ) $q=wz+h+j,\ \$ (Ⅱ) $z=f(h+j)+h,\ \$ (Ⅲ) $(2k)^3(2k+2)(n+1)^2+1=\Box,$
(Ⅳ) $p=(n+1)^k,\ \$ (Ⅴ) $q=(p+1)^n,\ \$ (Ⅵ) $z=p^{k+1}$

が成り立つことである。

証明. $\Longleftarrow$ の証明: $k, f, j, h, n, p, q, w, z$ が(Ⅰ)〜(Ⅵ)を満たすと仮定する。(Ⅳ)より $p \geq 1$ 、(Ⅵ)より $z > 0$ である。 $h+j=0$ ならば(Ⅱ)より $z=h=0$ となって、矛盾。仮定より $f \geq 1$ 。よって、 $0 < h+j \leq z$ が分かる。 $h+j=z$ ならば(Ⅰ)より $z$ は $q$ を割り切るので、それは(Ⅴ)、(Ⅵ)より $p^{k+1}$ が $(p+1)^n$ を割り切ることを意味する。しかし、 $p$ と $p+1$ は互いに素なのであるから、それはありえない。よって、 $0 < h+j < z$ となって、(Ⅰ)より $r(q, z)=h+j$ が確定する。

(Ⅳ)より $p > n^k$ が成り立つ。また、(Ⅲ)に補題１９を適用すると

$(2k)^k \leq 2k-1+(2k)^{2k-2} \leq n$

を得る。よって、補題２２より

$\displaystyle k! < \frac{z}{h+j} < k!+1$ .

が成り立つ( (Ⅳ)、(Ⅵ)より $z=(n+1)^kp^k$ である)。

一方、(Ⅱ)より

$\displaystyle f \leq \frac{z}{h+j} \leq f+1$

なので、 $X=z/(h+j)$ とおけば

$f \leq X < k!+1 < X+1 \leq f+2$

すなわち、 $f < k!+1 < f+2$ が得られる。 $f$ も $k!$ も整数なのだから、 $f=k!$ 。

$\Longrightarrow$ の証明: $f=k!$ とする。補題１９より、(Ⅲ)および $(2k)^k \leq n$ を満たすような $n$ が存在する。 $p:=(n+1)^k$ 、 $q:=(p+1)^n$ 、 $z:=p^{k+1}$ としよう。この時点で(Ⅳ)、(Ⅴ)、(Ⅵ)も成立。そうして、

$\begin{align}w &:= \frac{q-r(q, z)}{z}\\ h&:=z-fr(q, z) \\ j&:=r(q, z)-h\end{align}$

と定める。これは(Ⅰ)、(Ⅱ)が成り立つように定義されている。 $w$ は $q$ を $z$ で割った商なので、非負整数。あとは $h, j\geq 0$ のみが示すべきものとして残っている。

現時点で補題２２が使える状況になっており、

$\displaystyle k! < \frac{z}{r(q, z)} < k!+1$

が成り立つが、 $f=k!$ の仮定より(ここで初めて使う！)、

$\displaystyle f < \frac{z}{r(q, z)} < f+1$

が得られる。この二つの不等号がすなわち $h, j > 0$ を言っている。 Q.E.D.

定理２ $k$ を正の整数とする。このとき、 $k+1$ が素数となるための必要十分条件は、非負整数 $a, b, c, d, e, f, g, h, i, j, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z$ が存在して

$q=wz+h+j$
$z=(gk+g+k)(h+j)+h$
$(2k)^3(2k+2)(n+1)^2+1=f^2$
$e=p+q+z+2n$
$e^3(e+2)(a+1)^2+1=o^2$
$x^2=(a^2-1)y^2+1$
$u^2=16(a^2-1)r^2y^4+1$
$(x+cu)^2=( (a+u^2(u^2-a) )^2-1)(n+4dy)^2+1$
$m^2=(a^2-1)l^2+1$
$l=k+i(a-1)$
$n+l+v=y$
$m=p+l(a-n-1)+b(2a(n+1)-(n+1)^2-1)$
$x=q+y(a-p-1)+s(2a(p+1)-(p+1)^2-1)$
$pm=z+pl(a-p)+t(2ap-p^2-1)$

が成り立つことである。

証明. $\Longleftarrow$ の証明:

Step１ 1. 〜 14. が成り立つような $a, b, \dots, z$ が存在したと仮定する。3.に補題１９の前半の主張を適用することにより、 $2k \leq n$ が成り立つ(特に $2 \leq n$ および $k < n$ を念頭におく)。

次に、4.と5.に補題１９の前半の主張を適用することにより、

$p+q+z+2n-1+(p+q+z+2n)^{p+q+z+2n-2} \leq a \tag{4}$

が成り立つ(特に $n < e \leq a$ 、すなわち $n < a$ も覚えておく)。

6.-7.-8.-11.より系１が発動して( $n \geq 1$ 、 $a \geq 2$ は既に確認済み)、 $y=y_a(n)$ が成り立ち、従って、6.より $x=x_a(n)$ となる。

9.は考察しているPell方程式なので、或る非負整数 $k'$ が存在して*6、 $m=x_a(k')$ 、 $l=y_a(k')$ となる。

$n \geq 1$ なので、11. より $l < y$ が分かる。すると、補題３より $y_a(\ )$ が狭義単調増加であることから $k' < n$ でなければならない。

これまでに分かったことから、 $k < n, \ n < a$ および $k' < n, \ n < a$ であり、これらは全て整数なので

$k < a-1, \ \ \ k' < a-1 \tag{5}$

が得られる。10. より $l \equiv k \pmod{a-1}$ であり、 $l=y_a(k')$ および補題９より

$k' \equiv k \pmod{a-1}$ .

(5)と合わせることにより $k=k'$ が分かった。これより、特に $m=x_a(k), \ l=y_a(k)$ となる。

Step２ (4)より、 $p < p+2n-1 \leq a$ 。また、

$(n+1)^k < (p+q+z+2n)^{p+q+z+2n-2} \leq a$ .

$a\geq n+2$ ならば $a+1 \leq 2a-n-1$ であるし、 $a=n+1$ ならば $a+1 < a^2$ なので、どちらにせよ $a+1 < (2a-n-1)(n+1)$ が成り立って、

$a < 2a(n+1)-(n+1)^2-1$ .

まとめると、

$p, \ \ (n+1)^k < 2a(n+1)-(n+1)^2-1 \tag{6}$

12. より

$m \equiv p+l(a-n-1) \pmod{2a(n+1)-(n+1)^2-1}$

であるが、補題１２によれば

$x_a(k) \equiv (n+1)^k+y_a(k)(a-n-1) \pmod{2a(n+1)-(n+1)^2-1}$ ,

すなわち

$m \equiv (n+1)^k+l(a-n-1) \pmod{2a(n+1)-(n+1)^2-1}$

が成り立ち、

$p \equiv (n+1)^k \pmod{2a(n+1)-(n+1)^2-1}$

ということになる。故に、(6)と合わせれば

$p = (n+1)^k \tag{7}$

が示された。

Step３再び、(4)を用いれば(さっきとはピックアップする場所を変える！)、 $q < a$ 、 $(p+1)^n < a$ が分かる。Step２では $a > n$ なる条件から

$a < 2a(n+1)-(n+1)^2-1$

を導出したのであるから、 $a > p$ であったことから

$a < 2a(p+1)-(p+1)^2-1$

を得る。しからば、Step２と同様にして、13. から

$x \equiv q+y(a-p-1) \pmod{2a(p+1)-(p+1)^2-1}$ .

補題１２より

$x_a(n) \equiv (p+1)^n + y_a(n)(a-p-1) \pmod{2a(p+1)-(p+1)^2-1}$ ,

すなわち、

$x \equiv (p+1)^n+y(a-p-1) \pmod{2a(p+1)-(p+1)^2-1}$

が成り立ち、

$q \equiv (p+1)^n \pmod{2a(p+1)-(p+1)^2-1}$

が得られる。Step３の初めに並べた不等式から

$q=(p+1)^n \tag{8}$

が示された。

Step４ (4)を用いれば、 $z < a$ 、 $p^{k+1} < a$ が得られる( $k+1 \leq 2n-2$ に注意)。また、(7)より $p \geq 1$ であることに注意すれば、 $a > p-1$ であることから

$a < 2ap-p^2-1$

が示される。三度目なので詳述する必要なく、14. および補題１２から

$z=p^{k+1} \tag{9}$

が結論付けられる(ただし、 $p$ 倍することに注意)。

Step５ 1.-2.-3.-(7)-(7)-(9)より、命題２が発動して

$gk+g+k = k!$

が従う。すなわち、 $k!+1 = (g+1)(k+1)$ が成り立つので、Wilsonの定理によって $k+1$ は素数でなければならない。

$\Longrightarrow$ の証明: $k+1$ が素数であると仮定する。すると、Wilsonの定理によって非負整数 $g$ が存在して

$k! = gk+g+k$

が成り立つ。このとき、命題２によって1.-2.-3. および

$p=(n+1)^k, \ \ q=(p+1)^n, \ \ z=p^{k+1} \tag{10}$

が成り立つような非負整数 $f, h, j, n, p, q, z, w$ が存在することが分かる。

$e:=p+q+z+2n$ として4. が成立する。補題１９より5. が成立するような非負整数 $a, o$ であって $a \geq 2$ を満たすものが存在する。 $y:=y_a(n)$ としよう。すると、系１により6.-7.-8. が成立するような非負整数 $c, d, r, u, x$ が存在する。 $m:=x_a(k)$ 、 $l:=y_a(k)$ とする。Pell方程式の解なので9. が成立。

補題９より、 $l = y_a(k) \equiv k \pmod{a-1}$ であって、補題３より $l \geq k$ なのだから、10. を満たす非負整数 $i$ の存在が分かる。

3.より補題１９から余裕で $k < n$ が成り立つので、補題３より

$n+l = n+y_a(k) \leq n+y_a(n-1) \leq y_a(n) = y$

となって、11. を満たすような非負整数 $v$ の存在が分かる。

さて、現時点で3.〜5.が成立しているのだから、証明の前半の議論がそのまま適用できて

$(n+1)^k < a, \ \ (p+1)^n < a,\ \ p^k < a$

が成立する。従って、 $x=x_a(n), y=y_a(n), m=x_a(k), l=y_a(k)$ および(10)に注意して、補題１２(特に後半の主張)より12.-13.-14.を満たすような非負整数 $b, s, t$ が存在することが分かる。 Q.E.D.

定理１の証明

定理２の1. 〜 14. の(右辺)-(左辺)をそれぞれ $P_1, \dots, P_{14}$ とおく(全て多項式)。ただし、 $k$ のみ $k+1$ に置き換える(好みの問題であるが、こうすると $k$ も非負整数として扱える)。このとき、 $26$ 変数 $25$ 次の多項式 $M(a, b, \dots, z)$ を

$M(a, b, \dots, z) := (k+2)(1-P_1^2-\cdots -P_{14}^2)$

と定義する( $\deg P_{8}=12$ である)。すると、定理２より非負整数 $a, \dots, z$ に対して $k+2$ が素数となるための必要十分条件は

$P_1=P_2=\cdots =P_{14}=0$

で、これは

$1-P_1^2-\cdots -P_{14}^2 =1$

と同値である。しかし、

$1-P_1^2-\cdots -P_{14}^2 \leq 1$

かつ $1-P_1^2-\cdots -P_{14}^2$ は整数値をとるので、結局

$k+2$ が素数である $\Longleftrightarrow\ M(a, \dots, z) > 0$

が成り立つ。更に、この条件が成り立つとき

$M(a, \dots, z) = k+2$

なので、 $M(a, \dots, z)$ が正であるような値の全体集合は素数全体集合に一致することが示された。 Q.E.D.

証明を読んだ感想

この証明法は芸術的である。

よく使っているテクニックとしては「合同式＋不等式で等号を示す」です。
個人的には(4)を着目する部分を変えて何度も利用するのが面白いと感じました。

素数 $2$ を作ろう！

具体的な多項式を作れるということが重要な点であって、素数生成機としての実用性がないことは構成からも明らかです(代入したら素数が次々と生み出されるタイプのものではなく、定理２に従って考えている数 $k+2$ が素数かどうかを判定するものです。しかし、その素数判定は実質的にWilsonの定理に頼っているのであって、それ自体が実用性のないものでした。そこから他のアルファベットの値も決定しようとするとPell方程式を解く必要があります)。 $a, \dots, z$ にテキトーに非負整数を代入して $M(a, \dots, z)$ を計算しても大抵は負の数になって素数になりません。しかしながら、せっかくなので定理２(および命題１、２)の後半の証明を参考にして $M(a, \dots, z)=2$ となるような $a, \dots, z$ を一組見つけてみましょう
( $k\mapsto k+1$ として読み替えることに注意)。

$k=0$ (証明中の記号で言えば $k=1$ 。紛らわしいので $k':=k+1=1$ を導入する).
$1!=g\cdot 1+g+1$ より $g=0$ .
$32(n+1)^2+1=f^2, \ (n \geq 2)$ なる $n$ と $f$ を見つける。Pell方程式の一般論で必ずアルゴリズミックに見つけられるものの、ここでは幸い $n=2, \ f=17$ が即座に見つかる。
$p=(n+1)^{k'}=3$ .
$q=(p+1)^n=4^2=16$ .
$z=p^{k'+1}=3^2=9$ .
$w=\frac{q-r(q, z)}{z} = \frac{16-7}{9} = 1$ .
$h=z-k'!r(q, z)=2$ .
$j=r(q, z)-h=5$ .
$e=p+q+z+2n=3+16+9+4=32$ .
Pell方程式 $1114112(a+1)^2+1=o^2$ を満たす $a, o$ であって $a \geq 2$ であるようなものを見つける。

見つけられるわけあるか！

あ、見つかりました(最小解です)*7。

$\begin{align}&8340353015645794683299462704812268882126086134656108363777^2 –\\ &\color{red}{1114112}\times 7901690358098896161685556879749949186326380713409290913^2 = 1\end{align}$

$a=7901690358098896161685556879749949186326380713409290912$

これは条件 $a \geq 2$ を満たしていますネ！

$o=8340353015645794683299462704812268882126086134656108363777$

次は $y=y_a(n)=y_a(2)=2a$ とおく。

すなわち、 $y=15803380716197792323371113759499898372652761426818581824$

$x=x_a(n)=x_a(2)=2a^2-1$ とおく。

そろそろ、アラビア数字だけで書き下す気力がなくなってきました。。。ここからは、 $a$ を使って書けるということを理解できたらOKということにして妥協しましょう。

$\displaystyle u=x_a(4ny) = x_a(16a) = \frac{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}}{2} \in \mathbb{Z}_{>0}$

ちょっと大きい数が出てきたよ⭐︎ *8

$\displaystyle c=\frac{x_{a+u^2(u^2-a)}(n)-x}{u} = \frac{2(a+u^2(u^2-a))^2-1-(2a^2-1)}{u} = 2u(u^2-a)(u^4-au^2+2a)$

$\displaystyle d=\frac{y_{a+u^2(u^2-a)}(n)-n}{4y} = \frac{(u^2-1)(u^2-a+1)}{4a} \in \mathbb{Z}_{>0}$

$\displaystyle r=\frac{y_a(4ny)}{4y^2}=\frac{(a+\sqrt{a^2-1})^{16a}-(a-\sqrt{a^2-1})^{16a}}{32a^2\sqrt{a^2-1}} \in \mathbb{Z}_{>0}$

$m=x_a(k')=x_a(1)=a$

$l=y_a(k')=y_a(1)=1$

$\displaystyle i=\frac{l-k'}{a-1} = 0$

$v=y-n-l = 2a-3$

$\displaystyle b=\frac{m-p-l(a-n-1)}{2a(n+1)-(n+1)^2-1} = \frac{a-3-(a-3)}{6a-10} = 0$

$\displaystyle s=\frac{x-q-y(a-p-1)}{2a(p+1)-(p+1)^2-1}=\frac{2a^2-1-16-2a(a-4)}{8a-17}=1$

$\displaystyle t = \frac{pm-z-pl(a-p)}{2ap-p^2-1} = \frac{3a-9-3(a-3)}{6a-10}=0$

これで $26$ 変数用意できました。

定理３ 定理１の多項式を $M(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z)$ とおく。このとき、

$\begin{align}&M(a, 0, \{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}\} \\ &\ \ \ \ \times \left\{ \left( \frac{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}}{2} \right)^2-a\right\} \\ &\ \ \ \ \times \left\{ \left( \frac{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}}{2}\right)^4 \right. \\ &\ \ \ \ \left. -a\left( \frac{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}}{2}\right)^2+2a \right\}, \\ &\ \ \ \ \ \ \ \frac{1}{4a}\left\{ \left( \frac{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}}{2} \right)^2 - 1 \right\} \\ &\ \ \ \ \times \left\{ \left( \frac{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}}{2}\right)^2-a+1 \right\}, \\ &\ \ \ \ 32, 17, 0, 2, 0, 5, 0, 1, a, 2, 8340353015645794683299462704812 \\ &\ \ \ \ 268882126086134656108363777, 3, 16, \\ &\ \ \ \ \frac{(a+\sqrt{a^2-1})^{16a}-(a-\sqrt{a^2-1})^{16a}}{32a^2\sqrt{a^2-1}}, 1, 0, \\ &\ \ \ \ \frac{(a+\sqrt{a^2-1})^{16a}+(a-\sqrt{a^2-1})^{16a}}{2}, 2a-3, 1, 2a^2-1, 2a, 9) \\ &=2 \end{align}$

が成り立つ。ここで、

$a=7901690358098896161685556879749949186326380713409290912$

である。

素数を作るのって大変〜

謝辞

最後の $2$ を作るところで、 $a, o$ の値を間違えていました。これは、 $e^3(e+2)$ を計算するところで $e^3(e+3)$ と間違えたことによって、 $1114112(a+1)^2+1=o^2$ というPell方程式ではなく $1146880(a+1)^2+1=o^2$ を解いてしまっていたためです。このことは藤本浩司氏にご指摘いただきました。藤本氏に感謝致します。また、実際は170桁ではなく55桁の数だったため、書籍『素数姫の素数入門』における該当部分も連動してミスということになります。以上について深くお詫び申し上げます。

*1:Davis, Putnam, Robinsonの仕事も使って素数を表現する多項式の存在が1970年に理論的に示され、Matijasevicが1971年に $24$ 変数 $37$ 次の多項式の存在を示しています。

*2:例えば、この４人は $42$ 変数 $5$ 次のものを見つけており、 Matijasevicは $10$ 変数かつ約 $1.6\cdot 10^{45}$ 次のものを見つけています。

*3:この記事における制限においては、 $m-n$ を考える場合は $m \geq n$ を仮定すると考えてよい。

*4:これはDavisの論文では証明に使われているのですが、命題１の証明では実は不要です。不要なのに書いてしまったので、せっかくなのでこのまま残しておきます(実際には補題が多すぎて番号を揃えるのが面倒だから消したくないのです笑)。命題１の証明以外を書き上げてから命題１を書こうと思ったら大量に補題が必要だということに気づき、その分の執筆が大変でした。

*5: $(a-\sqrt{a^2-1})^n$ の部分の寄与は $1$ 以下であることに注意