インテジャーズ

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

インテジャーズ

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

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

26

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

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

定理1 (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の論文を引用して証明を省略している部分があるので(命題1)、その点についてはこの記事をまとめた価値があると思います)。

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

補題1 a2以上の整数とする。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
の定理2)よりわかる。 Q.E.D.

補題2 非負整数m, nに対して
\begin{align}x_a(m\pm n) &= x_a(m)x_a(n)\pm \sqrt{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で上手くいくものと上手くいかないものがある)。

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

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

x_a(n+1)=ax_a(n)+\sqrt{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.

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

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

補題5 mnの倍数であればy_a(m)y_a(n)の倍数である。

証明. 補題2より

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

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

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

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

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

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

補題7 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.

補題8 y_a(n)^2y_a(m)を割り切ればy_a(n)mを割り切る。

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

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

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

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

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

補題10 a, b, k2以上の整数とする。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.

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

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

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

補題12 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.

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

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

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

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

\begin{align}x_a(2n\pm m) &= x_a(n)x_a(n\pm m) + \sqrt{a^2-1}y_a(n)y_a(n\pm m) \\ &\equiv \sqrt{a^2-1}y_a(n)(y_a(n)x_a(m)\pm x_a(n)y_a(m) ) \pmod{x_a(n)} \\ &\equiv \sqrt{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.

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

証明. 補題14より

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

Q.E.D.

補題16 n \geq 1とし、i, ji \leq j \leq 2nを満たすような非負整数とする。このとき、a=2, \ n=1, \ i=0, \ j=2なる例外ケースを除いて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)}の完全代表系をなす。補題3より

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

であり、補題2からx_a(n) = ax_a(n-1)+\sqrt{a^2-1}y_a(n)なので

\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

と合同である(補題14よりわかる)。以上より、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)が成り立ったと仮定しよう。補題2からわかる

x_a(n) = ax_a(n-1)+\sqrt{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.

補題17 非負整数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のとき
補題16より例外ケースでなければj=iが言える。しかし、今はi > 0なので、例外ケースとなるのはi=2, \ j=0, n=1のときのみ。これはi \leq nに反する。

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

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

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

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

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

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

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

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

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

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

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

証明. a=e+1とおくと、①は

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

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

(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.

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

命題1 非負整数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が示された。

(Ⅰ)、(Ⅱ)、(Ⅲ)、補題1、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なので、補題3よりi \leq k

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

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

補題10より

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)}

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

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

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

y_a(i) \mid k

が得られる。よって、

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

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

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)、補題3より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)とおく。すると、補題1より(Ⅱ)が満たされる。

補題7よりy_a(ny_a(n))y^2で割り切れる。また、補題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)とすれば補題1より(Ⅲ)が成立。

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

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

系1 非負整数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

が成り立つことである。

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

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

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

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

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

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

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

証明. 有名定理(当ブログでは
integers.hatenablog.com
\Longrightarrowを証明しています)。\Longleftarrowの証明は容易(対偶を取ればよい)。 Q.E.D.

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

補題22 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)abで割った余りを表す記号とする。

証明. 仮定より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} ー②.

ここで

(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} ー③

を得る。②、③は

\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{補題20より}) \\ &\leq k! \left( 1+\frac{2k^2}{n} \right)  \ \ \ \ \ \ \ \ \ \ (\text{補題21より}) \\ &\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.

命題2 任意の正の整数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ならば(Ⅰ)よりzqを割り切るので、それは(Ⅴ)、(Ⅵ)よりp^{k+1}(p+1)^nを割り切ることを意味する。しかし、pp+1は互いに素なのであるから、それはありえない。よって、0 < h+j < zとなって、(Ⅰ)よりr(q, z)=h+jが確定する。

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

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

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

\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が得られる。fk!も整数なのだから、f=k!

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

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


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

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

\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.

定理2 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が存在して

  1. q=wz+h+j
  2. z=(gk+g+k)(h+j)+h
  3. (2k)^3(2k+2)(n+1)^2+1=f^2
  4. e=p+q+z+2n
  5. e^3(e+2)(a+1)^2+1=o^2
  6. x^2=(a^2-1)y^2+1
  7. u^2=16(a^2-1)r^2y^4+1
  8. (x+cu)^2=( (a+u^2(u^2-a) )^2-1)(n+4dy)^2+1
  9. m^2=(a^2-1)l^2+1
  10. l=k+i(a-1)
  11. n+l+v=y
  12. m=p+l(a-n-1)+b(2a(n+1)-(n+1)^2-1)
  13. x=q+y(a-p-1)+s(2a(p+1)-(p+1)^2-1)
  14. pm=z+pl(a-p)+t(2ap-p^2-1)

が成り立つことである。

証明. \Longleftarrowの証明.

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

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

p+q+z+2n-1+(p+q+z+2n)^{p+q+z+2n-2} \leq a ー④

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

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

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

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

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

k < a-1, \ \ \ k' < a-1 ー⑤

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

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

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

Step2 ④より、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 ー⑥.

12. より

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

であるが、補題12によれば

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}

ということになる。故に、⑥と合わせれば

p = (n+1)^k ー⑦

が示された。

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

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

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

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

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

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

補題12より

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}

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

q=(p+1)^n ー⑧

が示された。

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

a < 2ap-p^2-1

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

z=p^{k+1} ー⑨

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

Step5 1.-2.-3.-⑦-⑧-⑨より、命題2が発動して

gk+g+k = k!

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

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

k! = gk+g+k

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

p=(n+1)^k, \ \ q=(p+1)^n, \ \ z=p^{k+1} ー⑩

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

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

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

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

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)および⑩に注意して、補題12(特に後半の主張)より12.-13.-14.を満たすような非負整数b, s, tが存在することが分かる。 Q.E.D.

定理1の証明. 定理2の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である)。 すると、定理2より非負整数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.

証明を読んだ感想

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

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

素数2を作ろう!

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

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



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



\begin{align}&34986266962613973875045847782321687520204000098395473325553275663904\\ &92348482457052071656347281387416116470549596324250084380107561114769\\
&7500105207794622283860020078721024001^2 –\\ &\color{red}{1146880}×32669208755880421997798944233693767258585163765155067084038\\
&96290350588804872270444101770081405216230336525761784568731096269246\\
&6603506027264054755507300783502717246993765^2 = 1\end{align}



  • \begin{align}a=&326692087558804219977989442336937672585851637651550670840389\\ &629035058880487227044410177008140521623033652576178456873109\\ &62692466603506027264054755507300783502717246993764\end{align}

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

  • \begin{align}o=&349862669626139738750458477823216875202040000983954733255532\\ &756639049234848245705207165634728138741611647054959632425008\\ &43801075611147697500105207794622283860020078721024001\end{align}
  • 次はy=y_a(n)=y_a(2)=2aとおく。すなわち、\begin{align}y=&653384175117608439955978884673875345171703275303101341680779\\ &258070117760974454088820354016281043246067305152356913746219\\ &25384933207012054528109511014601567005434493987528\end{align}
  • 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

  • \begin{align} 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)\end{align}
  • \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変数用意できました。

f:id:integers:20160908002433p:plain



定理3 定理1の多項式を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, 349862669626139738750458477823216875\\ 
&\ \ \ \ 202040000983954733255532756639049234848245705207165634728\\ 
&\ \ \ \ 138741611647054959632425008438010756111476975001052077946\\
&\ \ \ \ 22283860020078721024001, 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}

が成り立つ。ここで、

\begin{align} a=\ &326692087558804219977989442336937672585851637651550670840389\\ &629035058880487227044410177008140521623033652576178456873109\\ &62692466603506027264054755507300783502717246993764\end{align}

である。




素数を作るのって大変〜

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

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

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

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

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

*6:アルファベットが足りない!!

*7:次のWeb上の計算機を利用しました: www.jakebakermaths.org.uk これ、単なるネタではなくて、中々計算が終わらなくて「見つけられるわけあるか!」って書いた後に再度webを確認したら丁度計算が終わっていたのです。私が検索して使ったこのサイトでは時間がかかりましたが、コメント欄で指摘されているように、このぐらいの解なら一瞬でプログラムで求められるようです。

*8:参考にa=10^{170}と簡略化したときのa^aの桁数を述べますと、1.7\times 10^{172}です。172桁の数ではないですよ。こんな表現ないかもしれないですが、(172桁)桁の数です。