インテジャーズ

インテジャーズ

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

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

オイラーの論文

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-xxx=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-xx5の倍数、従って、平方数なので、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で割った余りで場合分けする。

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

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

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

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

となる。

C8で割った余りは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

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

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 p4で割った余りが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)

となる。ここで、ka-cd-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}

と約分できるので、100000919^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

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


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

3413と言えば

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

ですね。

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

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

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

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

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

*5:B0以上なので有限回の計算で停止する。

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

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