素数全書練習問題1.16 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

有名な Cauchyの素数生成多項式の問題である。

まずはちょこっと計算により、 $x^2+x+41$ の値(-40≦x≦39)を出してみた。ただし、負の整数部分については単に折り返しているだけなので実質は0≦x≦39である。

41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601

41より小さな素数は無論でてこないが、41は13番目の素数で、1601は252番目なので 41から1601までは240個の素数があり、ここに出てこないものは200個ぴったりである。意外と隙間が多い。このCauchyの素数生成多項式は虚二次体 $\mathbb{Q}(\sqrt{-163})$ の数論に関係しているとのことで興味深いが、まずは先に問題を片づける。

f(x)を整数係数の定数でない多項式とするとき、整数xを動かすとf(x)の値は無限個の合成数の値をとることを証明せよ、が問題である。
題意を満たすf(x)について、十分大きなNをとるとx≧Nのとき f(x)は全て素数となる。p=f(N)として、f(N+kp)=f(N)+p・g(p,k,N) と展開できる。ここにg(x,y,z)は整数係数の多項式であり、恒等的に0ではない。k≧0を動かすと左辺は素数を動くが、一方、右辺はf(N)=pなのでpの倍数である。これが成立するにはg(p,k,N)=0 でなければならないが、kの方程式とみたときは有限個の解しかないため矛盾である。□

再び、Cauchyの素数生成多項式に戻る。なぜこれが0≦x≦39で素数を生成するのかざっくりと解説してみたい。

$x^2+x+41=(x+\frac{1+\sqrt{-163}}{2})(x+\frac{1-\sqrt{-163}}{2})$

と分解されるが、左辺の値が右辺では虚二次体 $\mathbb{Q}(\sqrt{-163})$ の中で（正確には、 $\mathbb{Q}(\sqrt{-163})$ の整数環 $\mathit{O}_{-163}$ の中で）分解されていることになる。もし、左辺が合成数で２つの整数の積に分解されるとすると左辺と右辺では2通りの分解の表示が得られていることになる。虚二次体の整数環の中で因数分解（正確には既約元による分解）の一意性が成立するのは実は有限個しかなく、整数環 $\mathit{O}_{-163}$ はその中の一つである。因数分解の一意性が成立しない有名な例としては、 $\mathit{O}_{-5}$ における $2\cdot 3=(1-\sqrt{-5})(1+\sqrt{-5})$ がある。2,3, $1-\sqrt{-5}$ , $1+\sqrt{-5}$ はいずれも既約元であり、どの２つも同伴でなく（一方にある単元＝可逆元を掛けたものになっていない）、この既約元分解は一意でない。

ただし、通常の意味の素数はかならずしも整数環の中で既約元であるとは限らないので注意が必要であるが、整数環 $\mathit{O}_{-163}$ におけるノルム $\mathcal{N}$ を考えると、 $\mathcal{N}(A+\frac{1\pm \sqrt{-163}}{2}B)=A^2+AB+41B^2$ なので、41より小さい素数は既約元である。それは p=mn なら $\mathcal{N}(p)=\mathcal{N}(m)\mathcal{N}(n)$ となり、 $p^2\ge 41^2$ が出るからである。
また、同じ論法で $x+\frac{1\pm \sqrt{-163}}{2}$ が $(A+\frac{1\pm \sqrt{-163}}{2}B)(C+\frac{1\pm \sqrt{-163}}{2}D)$ と分解されたとすると、 $x^2+x+41=(A^2+AB+41B^2)(C^2+CD+41D^2)=({(A+\frac{1}{2}B)}^2+\frac{163}{4}B^2){((C+\frac{1}{2}D)}^2+\frac{163}{4}D^2)$ なので、B≠0かつD≠0ならば $x^2+x+41\ge (\frac{163}{4})^2=1660.5625$ でなければならず、もし、B＝0またはD＝0ならば、AD=±1等となり、分解は自明なものになっている。よって、 $x^2+x+41\le 1660$ ならば $x+\frac{1\pm \sqrt{-163}}{2}$ は既約元である。

さて、Cauchyの素数生成多項式の値cが1660以下であったとする。(実際にx=39の値1601＜1660＜41×41=1681である。）cが合成数で 2つ以上の素数の積に因数分解されたとして、素因子の一番小さなものをpとすると、 $p^2\le c < 41^2$ なのでpは41より小さい素数である。よって、それは整数環 $\mathit{O}_{-163}$ の中でも既約元である。
一方、先の議論から $x+\frac{1 \pm \sqrt{-163}}{2}$ も既約元であり、Cauchyの素数生成多項式の分解の右辺は既約元分解であるが、左辺の分解に含まれる素数pも既約元であり、分解の一意性に矛盾している。□