UFD限定「オイラーの素数生成多項式」の証明

今日は「オイラーの素数生成多項式」についての話です。

f:id:tsujimotter:20210123230219p:plain:w400

この多項式に $X = 0, 1, \ldots, 39$ を代入した数はなんとすべて素数になることが知られています。

$f(0) = 0^2 + 0 + 41 = 41$ （素数）

$f(1) = 1^2 + 1 + 41 = 43$ （素数）

$f(2) = 2^2 + 2 + 41 = 47$ （素数）

$\vdots$

$f(39) = 39^2 + 39 + 41 = 1601$ （素数）

$X = 40$ を入れると $f(40) = 40^2 + 40 + 41 = 41^2$ となって合成数になってしまいます。しかしながら、それまでの実に $40$ 個もの間、素数が出続けるという驚異の多項式となっています。

この多項式の一般化として、 $q$ を $2$ 以上の自然数として

$f_q(X) = X^2 + X + q$

というものを考えます。

これが素数生成多項式であること、すなわち

整数 $0 \leq X < q-1$ に対して $f_q(X) = X^2 + X + q$ は素数

の必要十分条件は

$1-4q$ が平方因子を持たない
かつ
虚2次体 $\mathbb{Q}(\sqrt{1-4q})$ の類数が $1$ であること

であることが知られています。これは驚くべき事実ですね。

$1-4\cdot 41 = -163$ は平方因子を持たず、なおかつ、虚2次体 $\mathbb{Q}(\sqrt{-163})$ の類数が $1$ であることが知られているので、ここからただちにオイラーの多項式 $f_{41}(X) = X^2 + X + 41$ が素数を $40$ 連続で生成することがわかりますね。面白いです。

この一般的な事実の証明については、以前のブログ記事でもまとめたことがありました：
tsujimotter.hatenablog.com

しかしながら、証明はかなり難解であり、特にイデアルに慣れていない人にとってはアクセスしづらいものであったと思います。

一方で、主張の片側だけであれば、すなわち

$1-4q$ が平方因子を持たないかつ $\mathbb{Q}(\sqrt{1-4q})$ の類数が $1$
$\;\; \Longrightarrow \;\;$ 整数 $0 \leq X < q-1$ に対して $f(X) = X^2 + X + q$ は素数

に関して言えば、前提知識がかなり少なくても済みそうです。実際、イデアルをまったく使わなくても証明を行うことができます。

使うのは、2次体がUFD（一意分解整域）のときの「有理素数の素元分解法則」だけです。これだけ認めてしまえば、虚2次体についての少しの知識があれば、十分に証明を追うことができるようになります。

私は、オイラーの素数生成多項式は、もっと多くの人たちが興味を持ってもらえる対象だと思っていまして、ぜひ2次体の整数論への入り口として、この証明に興味を持っていただければと思います。

突然ですが、ここで宣伝です

今回の記事は、証明の厳密さに気をつけて書いているので、内容の正確性はある程度保証できますが、少し固いかもしれません。もう少しラフに、周辺の内容を紹介している動画がありますので、よろしければこちらも合わせてご覧いただけると嬉しいです。
www.youtube.com

UFDにおける有理素数の素元分解法則

$5$ という数は、通常の意味の整数おいては素数ですが、 $\mathbb{Z}[\sqrt{-1}]$ という環で考えると

$5 = (2+\sqrt{-1})(2-\sqrt{-1})$

というように、2つの $\mathbb{Z}[\sqrt{-1}]$ の整数の積に分解されます。

$2+\sqrt{-1}$ や $2-\sqrt{-1}$ は $\mathbb{Z}[\sqrt{-1}]$ における「素数」に相当する存在で、これを素元といいます。整数環 $\mathbb{Z}$ の素数を区別のために有理素数ということにします。

このように言葉を定義すると、 $5$ という有理素数が $\mathbb{Z}[\sqrt{-1}]$ における2つの素元の積に分解されたことになります。元々有理素数だったのに、環を広げると素数ではなくなってしまうというわけです。

一方で、 $3$ という数も同じく有理素数ですが、これは $\mathbb{Z}[\sqrt{-1}]$ においても素元のままです。有理素数によって分解されたりされなかったりするわけです。

こんな風に、虚2次体を $K$ として、 $K$ の整数環において、有理素数 $p$ がどのように分解されるのかを与える法則を紹介したいと思います。

ただし、次に紹介する法則が適用できるのは $\mathcal{O}_K$ が一意分解整域、すなわち任意の整数が素元の積に一意的に分解されるような $\mathcal{O}_K$ に限られます。一意分解整域の英語 "Unique Factorization Domain" の頭文字をそれぞれとって UFD と呼ぶことにします。

定理1（UFD限定・有理素数の素元分解法則）

$m$ を平方因子を持たない $0, 1$ ではない整数とする。 $K = \mathbb{Q}(\sqrt{m})$ を2次体とし、 $\mathcal{O}_K$ をUFDであるような $K$ の整数環とする。また、 $d$ を $K$ の判別式とする。すなわち

$d = \begin{cases} m & (m\equiv 1 \pmod{m}) \\ 4m & (m \equiv 2, 3 \pmod{4}) \end{cases}$

である。このとき、有理素数 $p$ に対して次が成り立つ：

(i) $p \not \mid d$ かつ $p \neq 2$ のとき：

$d$ が $p$ の平方剰余 $\;\;\Longrightarrow \;\;$ $p$ は $\mathcal{O}_K$ の素元 $\pi$ を用いて $p = \pm \pi \pi'$ と表される（ $\pi'$ は $\pi$ の共役で、 $\pi$ と $\pi'$ は同伴ではない）。
$d$ が $p$ の平方非剰余 $\;\;\Longrightarrow \;\;$ $p$ は $\mathcal{O}_K$ の素元である。

(ii) $p \not \mid d$ かつ $p = 2$ のとき：

$d \equiv 1, 7 \pmod{8}$ $\;\;\Longrightarrow \;\;$ $2$ は $\mathcal{O}_K$ の素元 $\pi$ を用いて $2 = \pm \pi \pi'$ と表される（ $\pi'$ は $\pi$ の共役で、 $\pi$ と $\pi'$ は同伴ではない）。
$d \equiv 3, 5 \pmod{8}$ $\;\;\Longrightarrow \;\;$ $2$ は $\mathcal{O}_K$ の素元である。

(iii) $p \mid d$ のとき：

$p$ は $\mathcal{O}_K$ の素元 $\pi$ を用いて $p = \pm \pi \pi'$ と表される（ $\pi'$ は $\pi$ の共役で、 $\pi$ と $\pi'$ は同伴である）

上に挙げた例について考えてみましょう。 $K = \mathbb{Q}(\sqrt{-1})$ で、整数環は $\mathbb{Z}[\sqrt{-1}]$ です。判別式は $d = -4$ です。 $\mathbb{Z}[\sqrt{-1}]$ はUFDなので、定理1が適用できます。

$p = 5$ のとき、定理1の(i)を適用できます。 $-4$ は $5$ の平方剰余なので、 $5 = (2+\sqrt{-1})(2-\sqrt{-1})$ という2つの相異なる素元の積に分解されます。

また、 $p = 3$ のときも同じく定理1の(i)を適用できます。 $-4$ は $3$ の平方非剰余なので、 $3$ は $\mathbb{Z}[\sqrt{-1}]$ の素元となります。

ちゃんと法則通りになっていますね！

イデアルを使わない素数生成多項式の証明

準備が整いましたので、そろそろ本題の証明にいきましょう。

$m$ を平方因子を持たない負の整数であって、 $m\equiv 1 \pmod{4}$ であるものとします。 $K = \mathbb{Q}(\sqrt{m})$ を虚2次体とすると、 $K$ の整数環は $m \equiv 1 \pmod{4}$ より

$\mathcal{O}_K = \mathbb{Z}\left[\frac{1+\sqrt{m}}{2}\right] = \left\{ a + b\frac{1+\sqrt{m}}{2} \; \middle| \; a, b \in \mathbb{Z} \right\}$

と表されます。

一般論として、 $\mathcal{O}_K$ がUFDであることの必要十分条件は、 $K$ の類数が $1$ であることです。したがって、UFDのときに素数生成多項式になることを示せば十分です。

定理2（UFDである虚2次体に付随する素数生成多項式）

$m$ を平方因子を持たない負の整数であって、 $m\equiv 1 \pmod{4}$ であるものとし、 $K = \mathbb{Q}(\sqrt{m})$ を虚2次体とする。また、 $f(X) = X^2 + X + \frac{1-m}{4}$ とする。

このとき、もし $K$ の整数環 $\mathcal{O}_K$ が一意分解整域（UFD）であるならば、整数 $0 \leq n < \frac{1-m}{4} - 1$ に対して $f(n)$ はすべて素数。

（証明）
$0 \leq n < \frac{1-m}{4} - 1$ に対して、 $f(n)$ が合成数であるものが存在すると仮定して、その $n$ を固定します。

このとき、 $f(n)$ の最小の素因数 $p$ が存在して、 $p^2 \leq f(n)$ が成り立ちます。すなわち

$\displaystyle p^2 \leq f(n) < f\left(\frac{1-m}{4} - 1\right) = \left(\frac{1-m}{4}\right)^2$

より

$\displaystyle p < \frac{1-m}{4} \tag{1}$

となります。

一方、 $K$ の判別式は $d = m$ です。ここで、 $\mathcal{O}_K$ はUFDなので、下記枠内の議論により $p$ は $\mathcal{O}_K$ の素元 $\pi$ を用いて $p = \pm \pi \pi'$ と表されます。

（∵） $p = 2$ と $p \neq 2$ で場合分けします。

$p = 2$ のとき：

$m \equiv 1 \pmod{4}$ より $m \equiv 1 \pmod{8}$ または $m \equiv 5 \pmod{8}$ のいずれかです。もし、 $m \equiv 5 \pmod{8}$ であるならば $m = 8k + 5$ と表されますが

$f(n) = n^2 + n + \frac{1-m}{4} = n(n+1) + (2k+1) \equiv 1 \pmod{2}$

より $2\not\mid f(n)$ です。したがって、 $2\mid f(n)$ であるならば、 $d = m \equiv 1 \pmod{8}$ です。したがって、定理1の (ii) より $p$ は2つの相異なる素元に分解します。

$p \neq 2$ のとき：

$p \mid f(n) = n^2 + n + \frac{1-m}{4}$ より

$\displaystyle n^2 + n + \frac{1-m}{4} \equiv 0 \pmod{p}$

であり、4倍して

$\displaystyle (2n + 1)^2 \equiv m \pmod{p}$

です。よって、 $p \mid m$ であるか $d = m$ は $p$ の平方剰余です。ゆえに、定理1の (i) または (iii) より $p$ は2つの（相異なるとは限らない）素元に分解します。

$\pi$ は $\mathcal{O}_K = \mathbb{Z}[\frac{1+\sqrt{m}}{2}]$ の元なので、有理整数 $a, b$ を用いて

$\displaystyle \pi = a + b\frac{1+\sqrt{m}}{2}$

と表されます。ここで、 $b = 0$ ならば $p = \pi \pi' = a^2$ より、 $p$ が素数であることに反するので $b \neq 0$ として良いことに注意します。

また、 $\pi$ のノルムは定義より $N(\pi) = \pi \pi'$ であり、また虚2次体なので正の値をとります。 $p > 0, \; N(\pi) > 0$ より

$p = \pi \pi'$

です。これに $\pi = a + b\frac{1+\sqrt{m}}{2}$ を代入すると、

$\begin{align} p = \pi \pi' &= \left( a + b\frac{1+\sqrt{m}}{2} \right)\left( a + b\frac{1-\sqrt{m}}{2} \right) \\ &= a^2 + ab + \frac{1-m}{4}b^2 \end{align}$