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

tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

オイラーの素数生成多項式の秘密

素数 素数と2次体の整数論 整数論 数学 オイラー イデアル類群・類数

今日はオイラーが発見した,

 f_q(x) = x^2 + x + q

という多項式についてお話したいと思います。


ある特別な  q に対して,多項式の  x に整数  0, 1, 2, 3, \cdots を入れていくと,「素数」が次から次へとたくさん出てくるのです。まるで 「魔法の多項式」 です。

これだけでも十分面白いのですが,なんとこれが 「類数」 という「一見まったく関係のなさそうな概念」と結びつくのです。私がこの事実を知ったのは,およそ2年ほど前です。それ以来,その秘密が知りたくてたまらなくなりました。

2年経って,いろいろな勉強をして,ようやく理解のための土台が出来てきたという実感を得ました。今こそ解説にチャレンジしたいと思います。


とはいえ,なかなかに難しい話ですし,私が理解しているレベルのほぼ最前線です。そのため,わかりやすく嚙み砕く余裕はほとんどありません。整数論の知識はかなり求められますし,普段の記事と比べてもだいぶレベルが高いかもしれません。その点ご了承ください。

目次

  1. 問題の確認
  2. 準備
  3. 主定理の証明( (1) ⇒ (2) )
  4. 主定理の証明( (2) ⇐ (1) )
  5. おわりに
  6. おまけと参考文献

問題の確認 *

試しに,この多項式の  q を固定して, x に整数  x = 0, 1, 2, 3, \cdots を入れてみましょう。


たとえば, q = 11 のとき,

 f_{11}(0) = 0^2 + 0 + 11(素数)
 f_{11}(1) = 1^2 + 1 + 11 = 13(素数)
 f_{11}(2) = 2^2 + 2 + 11 = 17(素数)
 f_{11}(3) = 3^2 + 3 + 11 = 23(素数)
 f_{11}(4) = 4^2 + 4 + 11 = 31(素数)
 f_{11}(5) = 5^2 + 5 + 11 = 41(素数)
 f_{11}(6) = 6^2 + 6 + 11 = 53(素数)
 f_{11}(7) = 7^2 + 7 + 11 = 67(素数)
 f_{11}(8) = 8^2 + 8 + 11 = 83(素数)
 f_{11}(9) = 9^2 + 9 + 11 = 101(素数)
 f_{11}(10) = 10^2 + 10 + 11 = 121 = 11^2(合成数)

となって, x 0 から  9 までの間は,すべて素数となりました。


一方で, q = 13 においては,

 f_{13}(0) = 0^2 + 0 + 13(素数)
 f_{13}(1) = 1^2 + 1 + 13 = 15(合成数)
 f_{13}(2) = 2^2 + 2 + 13 = 19(素数)
 f_{13}(3) = 3^2 + 3 + 13 = 25 = 5^2(合成数)
 f_{13}(4) = 4^2 + 4 + 13 = 33 = 3\times 11(合成数)
 f_{13}(5) = 5^2 + 5 + 13 = 43(素数)

となって,素数になったりならなかったりしますね。いろいろ実験してみると,多項式の値が素数になりやすい  q と そうでない  q が存在することがわかります。


いったいどんな素数のときに  f_q(x) が素数になりやすくなるのでしょう。実は, q がある特別な素数のとき以下が成り立ちます。

 q = 2, 3, 5, 11, 17, 41 のとき,連続する  q-1 個の整数  n = 0, 1, 2, \cdots, q-2 に対して, f_q(n)すべて素数である.


これらの  q は,オイラーの幸運数と呼ばれています。その  q を使った  f_q(n)オイラーの素数生成多項式と呼ばれています。*1


リストの一番大きい数である  q = 41 では, f_q(0) = 41 から  f_q(39)=1601 までの

 40 個もの間,連続して素数が出続ける

ことになります。たしかにこれは「幸運数」といってよいでしょう。


この文章を読んでいる読者のみなさまは,これらの「幸運な  q 」がいったいどういう数なのか気になるかと思います。実は,意外なものと結びつくのです。

 q = 2, 3, 5, 11, 17, 41 のとき, m = 1-4qヘーグナー(Heegner)数 である.ただし,ヘーグナー数  m は,虚二次体  \mathbb{Q}(\sqrt{m}) の類数が  1 となるような  m のこと.

私はこの事実を知ったときに,驚いて顎が外れそうになりました。

いったいどうして,幸運数類数 と結びつくのでしょうか。


私たちが知りたいことは,以下の定理に集約されます。

主定理
 q を素数とし, f_q(x) = x^2 + x + q とおく.また, m = 1-4q とする( m < 0 である)。このとき,次の2つの条件は同値である.

(1)  m は平方因子を持たず,虚二次体  \mathbb{Q}(\sqrt{m}) の類数は  1 である.
(2) 連続する  q-1 個の整数  n = 0, 1, \cdots, q-2 に対して  f_q(n) は素数である.

 (1) \Longrightarrow (2) の証明は 1912 年にフロベニウスが,逆の  (2) \Longrightarrow (1) は 1913 年にラビノヴィッチが証明したそうです。

念のため確認しておくと, (1) \Longrightarrow (2) は,

  •  \mathbb{Q}(\sqrt{m}) の類数が1なら  f_q(n) はぜんぶ素数だよ」

ということを意味していて, (2) \Longrightarrow (1) は,

  •  f_q(n) が全部素数になるのは, \mathbb{Q}(\sqrt{m}) の類数が1のときだけだよ」

ということを意味しています。


類数が  1 の虚二次体については,以下の定理が知られていますので, q の候補としては  q = 2, 3, 5, 11, 17, 41 だけであることがわかります。

ベイカー・スターク(Baker - Stark)の定理
平方因子を含まない負の整数  m に対して,虚二次体  \mathbb{Q}(\sqrt{m}) の類数が  1 であるのは, m = -1, -2, -3, -7, -11, -19, -43, -67, -163 の9個に限る.


ベイカー・スタークの定理だけでも,いろいろと話したいことはありますが,今日はこの定理については既知として進めましょう。


それでは,本題の主定理の証明にいきましょう。

準備 *

証明の前に記号と補題の準備をしましょう。「二次体の整数論」と「イデアル類群」についてのおさらいです。結構長いので,復習の必要がない方は「主定理の証明( (1) ⇒ (2) )」まで飛んでください。

二次体の整数環  \mathbb{Z}[\omega_K]

 K = \mathbb{Q}(\sqrt{m}) とします。つまり  K \mathbb{Q} \sqrt{m} を添加した体,すなわち二次体を表します。また, m = 1-4q < 0 より, K は虚二次体であることに注意します。

ここで, K の整数環  \mathbb{Z}[\omega_K] を考えます。二次体の理論により,一般に  \omega_K は以下のように定まります。

 \displaystyle \omega_K = \begin{cases} \sqrt{m} & (m \equiv 2, 3 \pmod 4) \\ \frac{1+\sqrt{m}}{2} & (m \equiv 1 \pmod 4 \end{cases}

今回は, m = 1-4q なので, m \equiv 1 \pmod{4} ですね。したがって,

 \displaystyle \omega_K = \frac{1+\sqrt{m}}{2}

で固定です。

ノルム  N(a + b\omega_K)

 K のノルムを考えます。 a, b \in \mathbb{Z} とし, K の数  a + b\omega_K のノルムを  N(a + b\omega_K) と表記し,以下で定義します。

 N(a + b\omega_K) = (a+b\omega_{K})(a+b\omega_K')

ここで, \omega_K の共役  \omega_K'

 \displaystyle \omega_K = \frac{1-\sqrt{m}}{2}

より,

 \begin{eqnarray} N(a + b\omega_K) &=& (a+b\omega_{K})(a+b\omega_K') \\
 &=& a^2 + ab(\omega_K + \omega_K') + b^2 \omega_K \omega_K' \\
 &=& a^2 + ab + b^2 \frac{1-m}{4} \\
 &=& a^2 + ab + b^2 q
\end{eqnarray}


となります。これより,特に  a = n, \; b = 1 として,

 N(n+\omega_K) = n^2 + n + q = f_q(n)

が成り立つことに注意しましょう。

 [\alpha, \beta ] という表記と標準基底

まず,基底を以下の記号で定義します。

 [\alpha, \beta ] = \left\{ x\alpha + y \beta \; \middle| \; x, y \in \mathbb{Z} \right\}

注意してほしいのは,基底自体は必ずしも  \mathbb{Z}[\omega_K] のイデアルになりません。

この基底を使うと,  \mathbb{Z}[\omega_K] の任意のイデアル  A を以下のように表すことができます。

 A = c [a, b + \omega_K] (ただし, a \mid N(b+\omega_K), \;\; 0 \leq b < a

このような表し方を,標準基底といいます。


また,標準基底で表した素イデアルについて以下が成り立ちます。

補題1
 p は有理素数とする.標準基底  P = [p, n+\omega_K]  p を割り切る  \mathbb{Z}[\omega_K] の素イデアル.

となります。この補題は,主定理の証明で利用していきます。

ところで,「 p は有理素数」とあえて書きました。 \mathbb{Z} 上の素数と  \mathbb{Z}[\omega_K] 上の素数(「素元」ということも多いようですが)が登場します。紛らわしいですね。

 \mathbb{Z} 上の素数  \Longleftrightarrow 有理素数
 \mathbb{Z}[\omega_K] 上の素数  \Longleftrightarrow 素数

と表記することにしましょう。

イデアル類群と類数

あとは,類数の話が出てきますから,当然イデアル類群が関係します。


まず,二次体  K の判別式を以下で定義します。

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

先ほどと同じように  m \equiv 1 \pmod{4} なので,

 d_K = m

です。


次に,集合  S_K を考えます。

 \displaystyle S_K = \left\{ p \mid p\leq M_K \;\; かつ \;\; \chi_{d_K}(p) \neq 1 \;\; となる有理素数 \; p \right\}


 M_KMinkowski の境界といって,定義は以下の通りです。

 M_K = \begin{cases}
 \sqrt{\frac{d_K}{2}} & (d_K > 0) \\
 \sqrt{\frac{|d_K|}{3}}  & (d_K < 0)
  \end{cases}

今回は,虚二次体なので  M_K = \sqrt{\frac{|d_K|}{3}} ですね。


 \chi_{d_K}(p) は以下の式で定義される指標です。

 \displaystyle \chi_{d_K}(p) = \begin{cases}
 \left(\frac{d_K}{\;p\;} \right) & (p \nmid 2d_K \;\; \unicode[sans-serif]{x306E} とき) \\
 \left(\frac{2}{|d_K|}\right)  & (p = 2 \;\; かつ \;\; 2 \nmid d_K \;\; \unicode[sans-serif]{x306E} とき) \\
 \;\;\;\; 0  & (p \mid d_K \;\; \unicode[sans-serif]{x306E} とき)
  \end{cases}

指標の意味をとらえるために,以下の補題を用意します。これも証明で使います。

補題2
 d_K を二次体  K の判別式, \chi_{d_K} K に付随する指標とする.このとき,有理素数  p で生成される  \mathbb{Z}[\omega_K] の単項イデアル  (p) の素イデアル分解は,以下で与えられる.

  1.  \chi_{d_K}(p) = 1 \; \Longleftrightarrow \; (p) = PP' P, P' \mathbb{Z}[\omega_K] の素イデアルで, P \neq P'

  このことを「 p \mathbb{Z}[\omega_K]完全分解する」という.

  1.  \chi_{d_K}(p) = -1 \; \Longleftrightarrow \; (p) \mathbb{Z}[\omega_K] の素イデアル .

  このことを「 p \mathbb{Z}[\omega_K]惰性する」という.

  1.  \chi_{d_K}(p) = 0 \; \Longleftrightarrow \; (p) = P^2 P \mathbb{Z}[\omega_K] の素イデアル.

  このことを「 p \mathbb{Z}[\omega_K]分岐する」という.


以上により,指標  \chi_{d_K} は,有理素数  p \mathbb{Z}[\omega_K] において「完全分解/惰性/分岐する条件」を表す記号だったことがわかります。


さて,これにて  \mathbb{Z}[\omega_K] において「惰性しない有理素数」を集めた集合である  S_K が定義できたわけですが,これを次のように使うとイデアル類群を作れます。

補題3
イデアル類群  \mathscr{C}_K は, S_K に属する有理素数を割る素イデアルの類により生成される。特に, S_K = \emptyset ならば  \mathscr{C}_K = \{\mathscr{P}_K\} である。

イデアル類群  \mathscr{C}_K の位数を「類数」といいます。したがって, S_K = \emptyset であれば,類数が  1 になるわけですね。


さぁ,ようやく準備が整いました!そろそろ本題にいきましょう!


主定理の証明(  (1) \Longrightarrow (2)*

 (1) を仮定し, 0 \leq n \leq q-2 を満たす整数  n f_q(n) が合成数 であるものが存在する とします。

このとき, p f_q(n) の最小の素因数 とすれば,

 p^2 \leq f_q(n) < f_q(q-1) = q^2

となります。

 f_q(n) < f_q(q-1) f_q の単調性から。また,
 f_q(q-1) = (q-1)^2 + (q-1) + q = q^2

に注意します。

したがって,

 p < q \tag{3}

です。


ここで  p \mid f_q(n) だから,

 p \mid f_q(n) = N(n+\omega_K)

です。よって  P=[p, n+\omega_K] とすれば,補題1より  P p を割る  \mathbb{Z}[ \omega_K ] のイデアルである。


 (1) より  K の類数は  1 である(すなわち,単項イデアル環) から,

 P = (a+b\omega_K)

となる整数  a, b(ただし, b \neq 0)が存在します。

このとき,

 \displaystyle \begin{eqnarray} N(a+b\omega_K) &=& a^2 + ab + \frac{1-m}{4} b^2 \\ &=& \left(a+\frac{b}{2}\right)^2 - \frac{m}{4}b^2 \\ &\geq& \frac{1-m}{4} \end{eqnarray}

ところが,

 N(a+b\omega_K) = N(P) = p

であるから,

 \displaystyle p = N(a+b\omega_K) \geq \frac{1-m}{4} = q

より,

 p \geq q \tag{4}

となってしまいます。

これは, (3) すなわち,

 p < q \tag{3}

に矛盾します。

したがって, f_q(n) が合成数であるという仮定は誤り であり, (2) が成り立ちます。

(証明終わり)


主定理の証明(  (2) \Longrightarrow (1)*

 (2) を仮定し m は平方因子を持たない」「虚二次体  K = \mathbb{Q}(\sqrt{m}) の類数は  1 である」をそれぞれ示します。

なお, q = 2 のときは明らかに  (2) (1) は成り立つので,以下  q > 2 とする。

 q = 2 とする. m = 1-4\cdot 2 = -7 であり, \mathbb{Q}(\sqrt{-7}) の類数は  1 である.

 m は平方因子を持たない」の証明

仮に  m が平方因子を持ち

 m = m_1 \ell^2(ただし, \ell > 1

と仮定します。 m は奇数より, \ell も奇数です。そこで,

 \displaystyle n = \frac{\ell - 1}{2}

とおくと, n は整数です。

この  n を使って,

 \displaystyle \begin{eqnarray} f_q(n)  &=& \left( \frac{\ell - 1}{2} \right)^2 + \left(\frac{\ell - 1}{2}\right) + \frac{1-m_1 \ell^2}{4} \\ &=& \frac{\ell^2 (1-m_1)}{4} \end{eqnarray}

を作ると,この数は合成数です。

 f_q(n) = \frac{\ell^2 (1-m_1)}{4} は合成数」の証明:

まず, n は整数より  f_q(n) = \frac{\ell^2 (1-m_1)}{4} も整数.したがって, \ell^2 (1-m_1) 4 で割り切れる.

一方, \ell は奇数より, 4 を割り切るのは  (1-m_1) の方である. \ell > 1 より, f_q(n) は合成数.


また, 0 \leq n \leq q-2 である こともふまえると,これは条件  (2) に反します

よって, m は平方因子を持たないことがわかります。

 0 \leq n \leq q-2 の証明:

 -m_1 \geq 1 より,

 \displaystyle q = \frac{1-m_1\ell^2}{4} \geq \frac{1+\ell^2}{4}
 \displaystyle \therefore -\frac{\ell^2}{4} \geq -q + \frac{1}{4}

また,

 \begin{eqnarray} f_q(q-1) - f_q(n) &=& q^2 - \left( \frac{\ell^2 (1-m_1)}{4} \right) \\ 
&=& q^2 - \left(\frac{\ell^2 - 1}{4} + q\right) \\ 
&=& q^2 - q + \frac{1}{4} - \frac{\ell^2}{4} \\
&\geq & q^2 - q + \frac{1}{4} - q + \frac{1}{4} \\
& = & q^2 - 2q + \frac{1}{2} \\
& = & q(q - 2) + \frac{1}{2} \\
& > & 0  \hspace{48px} (\because q > 2 ) \end{eqnarray}

よって, f_q(q-1) > f_q(n) である. f_q の単調性から  q-1 > n.したがって, q-2 \geq n が得られた.

「虚二次体  K = \mathbb{Q}(\sqrt{m}) の類数は  1 である」の証明

 (2) を仮定 し, S_K =  \emptyset であることを導きます。

(i)  S_K 2 を含まない

 q = f_q(0) は素数であるから, q > 2 より  q は奇数です。 q = 2Q + 1 とおくと,

 d_K = 1-4q = 1-4(2Q+1) = 5 - 8(1+Q) \equiv 5 \pmod 8

 d_K < 1 より,

 |d_K| = -d_K \equiv 3 \pmod 8

平方剰余の第2補充則より,

 \displaystyle \left(\frac{2}{\;|d_K|\;} \right) = -1

が成り立ちます。

平方剰余の第2補充則:
 p を奇数とするとき,以下が成り立つ.
 \displaystyle p \equiv 1, 7 \pmod{8} \; \Longleftrightarrow \; \left(\frac{2}{\;p\;} \right) = 1
 \displaystyle p \equiv 3, 5 \pmod{8} \; \Longleftrightarrow \; \left(\frac{2}{\;p\;} \right) = -1

ただし, \displaystyle \left(\frac{a}{\;m\;} \right) はヤコビ記号で, a は整数,  m は奇数をとる.


したがって,指標の定義より,

 \displaystyle \chi_{d_K}(2) = \left(\frac{2}{\;|d_K|\;} \right)  = -1

なので, 2 \mathbb{Z}[\omega_K] で惰性します.したがって, 2\not\in S_K です。

(ii)  S_K は 奇素数 を含まない

 S_K が奇素数を含むとすると補題2により, (p) \mathbb{Z}[\omega_K] において,

 (p) = PP'

と素イデアル分解します。

ここで, P を標準基底で表して,

 P = [ p, n+\omega_K], \;\;\; 0 \leq n < p \

とします。このとき, p \mid N(n+\omega_K) = f_q(n) ですが, p の取り方より,

 \displaystyle p \leq M_K = \sqrt{\frac{|d_K|}{3}} = \sqrt{\frac{4q-1}{3}} < q

これと  n < p とを合わせて, n \leq q-2 が得られます。


ここで, n^2 + n \geq 0 であることに注意すれば,

 f_q(n) = n^2 + n + q \geq q

であることが導けます。つまり, f_q(n) \geq q > p です。よって, p f_q(n) の自明でない素因数( p \neq 1 かつ  p \neq f_q(n))であることがわかります。

しかし,これは  (2) の条件( f_q(n) は素数)に矛盾する ので, S_K は奇素数を含まない ことがわかります。つまり,

 S_K = \emptyset

です。


したがって 補題3 より,類数は  1 であることが示されます。よって  (1) が導かれました。

(証明終わり)


おわりに *

いかがだったでしょうか。類数と幸運数のつながりがつかめましたでしょうか。

この問題は,私が「類数」という概念を知り,関心を持った記念の問題です。これを機に「代数的整数論」に興味を持って,その世界に足を踏み入れることになったのでした。その世界があまりにも広すぎることに気づいて,何度もくじけそうになりました。

私のここ2年ほどの悩みは,

「類数が1」という条件を、
どのように利用しているか

だったわけですが,以前よりはずいぶんと見通しがついたように思います。

 (1) \Longrightarrow (2) においては「類数が1であればすべてのイデアルが単項イデアルである」というよくあるパターンを用いるのです。

一方の  (2) \Longrightarrow (1) においては,たまたま  M_K 以下の有理素数が惰性して,結果として  S_K が空集合になり,類数が1になる,という具合らしいのです。この「たまたま」と言っているあたりが,(たぶん私の理解不足なのですが)少々歯切れが悪い気がしてしまいます。もう少し直感的な証明があるといいなぁ,と思います。


とはいえ,この解説が(わかりやすかったかどうかはさておいて)自分の手で書くことができたということは,私もずいぶんと成長したということであり,感慨深いものがあります。わからなかったら是非何度も読み返していただければと思います。わたしも書きながら何度もこんがらがりました。笑


それでは,今日はこの辺で。


おまけと参考文献 *

もともと今回の話を知ったのは,Wikipedia の「素数」の記事内の項目「素数生成式」の記述でした。

素数 - Wikipedia

読んでみると,

オイラーの発見した式、 f(n) = n^2 + n + 41 は、n = 0, …, 39 において全て素数となる。これは、虚二次体  \mathbb{Q}(\sqrt{-163}) の類数が 1 であることと関係している

と書いてありました。

「ほんとかよ!」と思って参考文献を見てみると,"Ribenboim 第3章" とあります。早速探してみると,それっぽい本が4冊もあるのですね・・・。とりあえず,それらを一通り買ってみました。どれも面白かったです(笑)

結局,該当の本は以下のものであることが判明しました。

素数の世界―その探索と発見

素数の世界―その探索と発見

「第3章 素数を定義する関数は存在するか」という箇所に「  X^2 + X + q の形の多項式に関する興味深い命題」として命題と背景となる数学史が述べられていました。残念ながら詳しい証明は載っていません。


ちなみに読む意味がなかったかと言うと,まったくもってそんなことはありません!かなりのヒントは得られましたし, X^2 + X + q に限らない素数生成多項式について述べられていました。

面白かったものをいくつか紹介します。

 f_1(X) = 2X^2 + p
 f_2(X) = 2X^2 + 2X + \frac{p+1}{2}, \;\; p \equiv 1 \pmod 4
 f_3(X) = pX^2 + pX + \frac{p+q}{4}, \;\; p < q, \; pq \equiv 3 \pmod 4

Frobenius は  \mathbb{Q}(\sqrt{-2p}) の類数が  2 であるとき  f_1 は素数生成多項式になること,また,  \mathbb{Q}(\sqrt{-p}) の類数が  2 であるとき  f_2 は素数生成多項式になることを示したそうです。Hardy は,この逆を証明し,さらに  f_3 についても結果を残しています。

ほかにも, f(X) = aX^2 + bX + c の形の素数生成多項式について,いくつか知られているそうです。今度機会があれば紹介します。


具体的に証明の方法が述べられているのは,以下の本の第5章「Euler の有名な素数生成多項式と虚2次体の類数」です。

我が数、我が友よ―数論への招待

我が数、我が友よ―数論への招待

ただ,ちょっと私にはまだ難しく,ざっくりとしか理解できていません。(「まえがき」から著者の数への愛が伝わってくる,本当に素敵な本です)


ちなみに,ついでに買ったこちらは,今回の話には関係ありませんが,これまた興味深い話がたくさん載っていました。

少年と素数の物語 I ?その扉をひらく?

少年と素数の物語 I ?その扉をひらく?

少年と素数の物語 II ?はるかなる旅へ?

少年と素数の物語 II ?はるかなる旅へ?

特に,第1巻の「フェルマー数は素数ですか」の話は私は大好きです。この話は,以下の記事でも触れています。
tsujimotter.hatenablog.com


いろいろ経て,最終的にはこの本の最後の方に(比較的)分かりやすい証明が載っていることに気づきました。今回の話は,この本の内容をベースに再構成しています。私がこの本を勉強していたのは「実はこの素数生成多項式について知りたかったから」と言っても過言ではありません。

素数と2次体の整数論 (数学のかんどころ 15)

素数と2次体の整数論 (数学のかんどころ 15)

  • 作者: 青木昇,飯高茂,中村滋,岡部恒治,桑田孝泰
  • 出版社/メーカー: 共立出版
  • 発売日: 2012/12/21
  • メディア: 単行本
  • 購入: 2人 クリック: 2回
  • この商品を含むブログを見る



*1:オイラーが 1772 年に,この事実についてベルヌーイあてに手紙を送ったのが由来のようです。