INTEGERS

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

オイラーの定理：1000009は素数ではない

整数整数-1000009 整数-293 整数-3413

オイラーの論文

L. Euler, Utrum hic numerus $1000009$ sit primus necne inquiritur, Nova acta academiae scientiarum Petropolitanae 10 (1797), 63–73.

で証明されている次の定理の証明を解説します：

定理 (オイラー) $1000009$ は素数ではない。

オイラーによる証明*1. 一見して

$1000009=1000^2+3^2$

がわかるが、 $1000009$ が二平方和として他の表示を持たないかどうかを探索しよう。

つまり、整数 $x$ に対して $1000009-xx$ が $x=3, 1000$ を除いて平方数になるかどうかを調べる*2。

オイラーは使っていないが、よくやるように「平方数であること」を「 $=\Box$ 」と表現することにする。

$1000009-xx=\Box$

と仮定しよう。平方数の一の位は $0, 1, 4, 5, 6, 9$ しかあり得ないので、上の式を $10$ で割った余りで考えると

$\begin{align} &9-0 \equiv 9, \quad 9-9\equiv 0 \pmod{10} \\ &9-4\equiv 5, \quad 9-5\equiv 4 \pmod{10}\end{align}$

という状況しかあり得ない。

対称性から $1000009-xx$ は $5$ の倍数、従って、平方数なので、 $25$ の倍数であると仮定してよい。

$xx \equiv 9 \pmod{25}$

なので、こうなるのは

$x \equiv \pm 3 \pmod{25}$

のときしかあり得ない。 $xx$ の値のみが問題になってくるので、 $x$ が負の場合も考えることにすれば、 $x=25a+3$ と書けるとしてよい( $a$ は整数)。

代入することによって

$1000000-6\cdot 25a-25^2aa=\Box$

であり、 $25$ で割ることによって

$40000-6a-25aa=\Box$

となる。 $a$ が偶数か奇数で場合分けしよう。

$a$ が偶数の場合は $a=2b$ と書いて、これを代入してから $4$ で割ることにより

$A=10000-3b-25bb=\Box$

となる。

$a$ が奇数の場合は更に $4$ で割った余りで場合分けする。

$a$ を $4$ で割った余りが $1$ の場合は $a=4c+1$ と書いて、代入すれば

$B=39969-224c-400cc=\Box$

となり、 $a$ を $4$ で割った余りが $3$ の場合は $a=4d-1$ と書いて、代入すれば

$C=39981+176d-400dd=\Box$

となる。

$C$ を $8$ で割った余りは $5$ であるが、平方数を $8$ で割った余りは $0, 1, 4$ にしかなり得ないので、 $C=\Box$ のケースは起こり得ない。

$A, B$ について調べる必要があるが、まずは $A$ について調べる。 $b$ が偶数か奇数で場合分けしよう。

$b$ が偶数のとき。 $b$ が単偶数*3の場合は $A$ が偶数なのに $4$ で割れないので平方数になり得ない。

よって、 $b=4c$ と書く。このとき、

$\displaystyle \frac{A}{4}=2500-3c-100cc=\Box$

であるが、これが $0$ 以上の値となるのは $\left|c\right| \leq 5$ の場合に限る。

$c=0$ のときは $b=0$ 、すなわち $a=0$ なので、 $x=3$ となって $1000009=1000^2+3^2$ の場合となるので除外ケース。

$c=\pm1$ のときは

$\displaystyle \frac{A}{4}=2397, \ 2603$

であり、これは(少なくともオイラーにとっては)見るからに平方数でない。

$c=\pm 2$ のときは $A/4$ が偶数なのに $4$ で割れないので平方数ではない。

$c=\pm 3$ のとき

$\displaystyle \frac{A}{4}=2500-900\pm 9 = 1600\pm 9$

は平方数ではない。

$c=\pm 4$ のとき

$\displaystyle \frac{A}{4}=2500-1600\pm 12 = 900\pm 12$

は平方数ではない。

$c=\pm 5$ のとき

$\displaystyle \frac{A}{4}=2500-2500\pm 15 = 0\pm 15$

は平方数ではない。

$b$ が奇数の場合。更に $4$ で割った余りで場合分けする。

$4$ で割った余りが $1$ の場合は $b=4d+1$ と書いて

$\displaystyle \frac{A}{4}=9972-212d-400dd=\Box$

なので、 $4$ で割って

$\displaystyle \frac{A}{16}=2493-53d-100dd=\Box$

を得る。これが $0$ 以上になるのは $\left|d\right| \leq 5$ かつ $d \neq 5$ の場合のみである。

$d=0$ のときは(オイ(ry)見るからに平方数ではない。

$d=\pm 1$ のとき $A/16=2393\pm 53$ は平方数ではない。

$d=\pm 2$ のとき $A/16=2093\pm 106$ は平方数ではない。

$d=\pm 3$ のとき $A/16=1593\pm 159$ は平方数ではない。

$d=\pm 4$ のとき $A/16=893\pm 212$ は平方数ではない。

$d=-5$ のとき $A/16=-7+265$ は平方数ではない。

$4$ で割った余りが $3$ の場合は $b=4d-1$ と書いて

$\displaystyle \frac{A}{4}=9978+188d-400dd$

となるが、これは偶数なのに $4$ で割れないから平方数になり得ない。以上によって、 $A$ は( $x\neq 3$ とすると)平方数になり得ないことが示された。

あとは $B$ について調査すればよい。ここでは、 $c \geq 0$ として

$B=39969\pm 224c-400cc$

を $c=0, 1, 2, 3, 4, \dots$ と順番に計算していく。

さて、 $c=0, 1, 2, 3, 4$ とすると、 $400cc-224c$ は

$0, 176, 1152, 2928, 5504$

であり、差は

$176, 976, 1776, 2576$

と推移している。 $400cc+224c$ は

$0, 624, 2048, 4272, 7296$

であり、差は

$624, 1424, 2224, 3024$

と推移している。

どちらも差は $800$ ずつ増加していることがわかる*4。このことに注意すれば、簡単に $B$ を順次計算できる*5。

f:id:integers:20170510235141p:plain:w400

探索しているのは引き算の結果が平方数になる場合であるが、これを眺めるとただ一つだけ平方数があることがわかる：

$2209=47^2.$

これは(もとの $c$ の定義に戻ると) $c=-10$ の場合なので、 $a=-39$ であり、 $x=25a+3=-972$ である。

$1000009-xx=55225=235^2$

なので、 $1000009$ は

$1000009=1000^2+3^2=972^2+235^2$

と二通りの二平方和としての表示があることが判明した。オイラーは次を示している：

二平方和の定理*6 $p$ が $4$ で割った余りが $1$ であるような素数であれば、 $p$ は順序を除いて丁度一通りに二平方和として表すことができる。

よって、 $1000009$ は素数ではない。 Q.E.D.

素数でないことが判明したので素因数分解をしたくなります。オイラーは昔の論文で次の議論を行っていたことを思い出しましょう：

文字は全て整数で、 $N=a^2+b^2=c^2+d^2$ のとき、

$a^2-c^2=d^2-b^2$

なので

$(a-c)(a+c)=(d-b)(d+b)$

となる。ここで、 $k$ を $a-c$ と $d-b$ の最大公約数とすると、互いに素な整数 $l, m$ が存在して

$a-c=kl, \quad d-b=km$

と書ける。このとき、

$l(a+c)=m(d+b)$

なので、或る整数 $n$ が存在して

$a+c=mn, \quad d+b=ln$

と書けることがわかる。このとき、

$(k^2+n^2)(m^2+l^2)=2(a^2+b^2+c^2+d^2) = 4N$

が成り立つ。

定理 (オイラー) $1000009$ の素因数分解は $1000009=293\times 3413$ である。

オイラーによる証明. 前定理の証明において

$1000009=1000^2+3^2=972^2+235^2$

を示した。よって

$1000^2-235^2=972^2-3^2$

$(1000-235)(1000+235)=(972-3)(972+3)$

$765\cdot 1235 = 969\cdot 975$

を得る。ここで、

$\displaystyle \frac{1235}{975}=\frac{969}{765}=\frac{19}{15}$

と約分できるので、 $1000009$ は $19^2+15^2$ と共通因子を持ち、それは $293$ である。そうして、 $1000009$ は

$1000009=293\cdot 3413$

と分解される。 Q.E.D.

先の計算において $a=1000, b=3, c=972, d=235$ であり、 $k=51, n=65, l=15, m=19$ となっているので、

$\displaystyle 1000009=\frac{51^2+65^2}{2}\cdot \frac{19^2+15^2}{2} = 3413\cdot 293$

が得られるという寸法です。二平方和に沿った気障な方法もなくはないですが、 $293$ や $3413$ は小さいので素数であることは既知としてよいでしょう。

ちなみに、 $293$ と言えばボウリングのスコアとして得られる最大の素数ですが、ファン・デル・ヴェルデン数でもあります。

$3413$ と言えば

$3413=1^1+2^2+3^3+4^4+5^5$

ですね。

なお、 $1000009$ は素数大富豪では出せません*7。

*1:オイラーは $1000009$ が素数であると思ってこの計算を行っていたら実は合成数だったということらしい(当時の素数表にこの数が入っていた)。なので、単に合成数であることを示すだけならもっと省略できる( $A$ や $C$ の考察はいらない)が、オイラーが論文に書いた計算を全て見ることにする。オイラーは $1000009$ の後に $1000081$ に移ってこちらは素数であることを証明している。これについてはまたの機会にまとめたい。

*2:昔は $x^2$ のことを $xx$ と書いていた。

*3: $4$ で割った余りが $2$ であるような偶数。

*4:実験的に見えるが証明は簡単。

*5: $B$ は $0$ 以上なので有限回の計算で停止する。

*6:二平方和の定理については次の記事を参照してください。 integers.hatenablog.com

*7:エデンの園素数 integers.hatenablog.com