インテジャーズ

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

インテジャーズ

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

1093と3511について

1093 3511

10933511は知られている唯二*1のWieferich素数です。

このことについては既に記事を書いています:
integers.hatenablog.com

しかし、その歴史について勘違いしていた(知らなかった)ことがあったので再び記事にしたいと思います。

Wieferich素数の定義

定義を復習しましょう。Fermatの小定理
tsujimotter.hatenablog.com

より、奇素数pに対して

2^{p-1}\equiv 1 \pmod{p}

が成り立ちます。それでは

2^{p-1}\equiv 1 \pmod{p^2}

は成り立つでしょうか?

答えは「成り立つことも成り立たないこともある」です。この合同式が成り立つようなpのことをWieferich素数と言い、冒頭に述べた通りp=1093, 3511のみ知られています。

Abelの問題

それを読んで数学者を志した者も多い高木貞治の名著『近世数学史談』。

私は高校生の頃に数学教師に戴いて、一夜で一心不乱に読んだことを覚えています。

この本の15節「パリからベルリンへ」の中に次のような記述があります:

第三巻にアーベルが提出した問題に次のようなものがある. 『\muは素数, \alpha1よりも大で\muよりも小なる整数とするとき, \alpha^{\mu -1}-1\mu^2で割り切れることがあるか?』

第三巻とはCrelle誌の第三巻です。\alpha =2を考えれば\muはすなわちWieferich素数なので、Abelの問の答えは「Yes」です。

今見返すと、10933511という数は近世数学史談には書いていません。私がこれらの数をいつ知ったかは覚えていないですが、Abelはこの問題を提出しているぐらいなので10933511については勿論知っているだろうとてっきり思っていました*2

MeissnerとBeegerが発見

これが最初に述べた「勘違い」で、これらの数が発見されたのは1829年に没したAbelよりずっと後だったのです。1093, 3511という数自体は小さいので誰でも知っていたのかと思っていましたが、よく考えてみると、扱うのは2^{1092}2^{3510}ですから、コンピュータのない時代にこれらの数を発見することは容易ではありません。

しかも、Wieferich素数の名前の由来になったWieferichの定理が出版されたのは1909年ですから、Wieferichの定理が証明されたときでさえWieferich素数は一つも知られていなかったのです!!

1093を発見したのはMeissnerで1913年、3511を発見したのはBeegerで1922年だそうです(当時あった剰余表を用いてMeissnerは2000以下の素数、Beegerは3700以下の素数について計算)。その後、現在に至るまで3つ目が見つかっていません。

コンピュータに頼らない証明

10933511が実際にWieferich素数であることを証明しようと思うとき、愚直にコンピュータで2^{p-1}-1を計算して実際にp^2で割り切れることを確認するという方法があるでしょう。

誰かに\frac{2^{1092}-1}{1093^2}および\frac{2^{3510}-1}{3511^2}の数値を教えていただいて、ここに掲載したいという願望がありますが、とりあえずコンピュータの知識がない私には計算できません*3

そこで、コンピュータにはできるだけ頼らず、既に計算された剰余表なども用いずに、使うとしても関数電卓ぐらいで理解できる証明を紹介したいと思います*4

1093がWieferich素数であることのLandauによる証明.
p=1093とする。3^7=2187=2p+1なので、

3^{14} = (2p+1)^2 \equiv 4p+1 \pmod{p^2} ー①

を得る。また、2^{14}=16384=15p-11なので

2^{28}=(15p-11)^2 \equiv -330p+121 \pmod{p^2}

であり、

3^2\cdot 2^{28} \equiv -2970p+1089 =-2969p-4 \equiv -1876p-4 \pmod{p^2}

を得る。4で割ると3^2\cdot 2^{26} \equiv -469p-1 \pmod{p^2}なので、

3^{14}\cdot 2^{182} \equiv -(469p+1)^7 \equiv -3283p-1 \equiv -4p-1 \pmod{p^2}.

①と合わせることにより、3^{14}\cdot 2^{182} \equiv -3^{14} \pmod{p^2}となるので、2^{182} \equiv -1\pmod{p^2}が示された。1092=182\times 6なので、

2^{1093-1} \equiv 1 \pmod{1093^2}

である。 Q.E.D.


3511がWieferich素数であることのGuyによる証明.
q=3511とする。

q-1=3510=2\cdot 3^3\cdot 5\cdot 13. ー②

3^8=6561=2q-461より

3^{10}=18q-4149 = 17q-638

であり、

\begin{align}3^{10}\cdot 11 &= 187q-7018 = 185q+4 \\ &\equiv 4+q(185+q) \\ &= 2^2(1+924q) \pmod{q^2}\end{align} ー③

を得る。

2^6\cdot 5\cdot 11 = 3520 = 9+q \equiv 9-3510q = 3^2(1-390q)\pmod{q^2}. ー④

2\cdot 13^3 = 4394=q+883より、2^313^3 = 4q+3532 = 5q+215^5=3125=q-386。よって、

\begin{align}5^7 &=25q-9650 = 22q+883 \\ &\equiv q+883+q(5q+21) \\ &= 2\cdot 13^3+2^3\cdot 13^3q\pmod{q^2}\end{align}

であり、

5^7(1-4q) \equiv 2\cdot 13^3\pmod{q^2}

を得る。2^{12}=4096=q+585より

2^{13}\cdot 3 = 6q+3510=7q-1. ー⑤

こうして得られた②〜⑤を等号

\begin{align}&2^{1755}(2\cdot 3^3\cdot 5 \cdot 13)^3\cdot (3^{10}\cdot 11)^{10}\cdot (3^2)^{10}\cdot 5^7\\ &= (2^2)^{10}\cdot (2^6\cdot 5\cdot 11)^{10}\cdot (2\cdot 13^3)\cdot (2^{13}\cdot 3)^{129}\end{align}

に代入すれば、

\begin{align}&2^{1755}(q-1)^3\{2^2(1+924q)\}^{10}\cdot (3^2)^{10}\cdot 5^7 \\ &\equiv (2^2)^{10}\cdot \{ 3^2(1-390q)\}^{10}\cdot 5^7(1-4q)(7q-1)^{129} \pmod{q^2}\end{align}

が得られるので、両辺を

\displaystyle \frac{(-1-q)^3(1-924q)^{10}}{(2^2)^{10}\cdot (3^2)^{10}\cdot 5^7}

倍すれば

\begin{align}2^{1755} &\equiv (1+q)^3(1-924q)^{10}(1-390q)^{10}(1-4q)(1-7q)^{129} \\ &\equiv 1-q(-3+9240+3900+4+903) \\ &= 1-4q^2 \\ &\equiv 1 \pmod{q^2}\end{align}

なる合同式に到達する。3510=1755\times 2なので、結局

2^{3511-1}\equiv 1 \pmod{3511^2}

が示された。 Q.E.D.


職人芸ですね。

*1:唯一という単語を一般化して使ってみました。

*2:なお、5^{2-1}=5 \equiv 1\pmod{2^2}\alpha < \muを満たしません。Abelの問題に答えるならば、3^{11-1}=59049, \ 59048=11^2\times 488が一番簡単かもしれません。

*3:追記)記事を公開して1時間もしないうちにtsujimotterさんが計算してくださいました! tsujimotter.hatenablog.com

*4:Fermat数F_5641で割り切れることについても同様の賢い証明法を紹介したことがあります: integers.hatenablog.com