tsujimotterのノートブック

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

電子計算機を使わないで発見された最大の素数 (2^148+1)/17（Ferrierの素数）

数学 素数 整数論 アドベントカレンダー

日曜数学 Advent Calendar 2021 の17日目の記事です。


今日は

\displaystyle N = \frac{2^{148}+1}{17} = 20988936657440586486151264256610222593863921 \tag{1}

という数について考えたいと思います。

この数、桁数が 44桁 もある巨大な数なのですが、なんと 素数 であることが分かっています。

1951年に素数であることが証明されたのですが、面白いことに

電子計算機を使わないで発見された最大の素数

という二つ名がつけられています。そう聞くとなかなか興味深く思えてきますよね！　一体どのようにして証明されたのでしょうか！？


今日は、この数が素数であることを判定する、Ferrier（以降、フェリアーと呼ぶことにします *1）による方法を紹介したいと思います。

「素数である」という事実は後で紹介するWikipediaにも書いています。しかいながら、素数であることを証明する方法は、インターネット上を探してもなかなか見つかりません。今回、色々頑張って参考になる本を見つけたので、その内容をベースに紹介したいと思います。


Prime Numbers and Computer Methods for Factorization (Progress in Mathematics)

Prime Numbers and Computer Methods for Factorization (Progress in Mathematics)

Amazon

なお、フェリアーの方法にこだわらないのであれば、ミラーラビン法を使えばコンピュータを使って一瞬で素数判定できます。

たとえば、以下のサイトで "20988936657440586486151264256610222593863921" を判定してみてください。
tsujimotter.info

実際、このような結果が出て、素数であることがわかるでしょう。

なお、ミラーラビン法は厳密に言えば「確率的素数判定法」であり、上記の判定も（非常に低確率ですが）誤りである可能性があります。一方で、ミラーラビン法の前身である「ミラー法」であれば（一般化リーマン予想の仮定の下で）確定的に判定できます。このぐらいの桁数であれば、数秒もあれば判定できます。（実際にやってみました。）


ところで、ミラーラビン法の元となったミラー法は1976年に提案されていますので、フェリアーの1951年当時には存在しなかったことになります。

さらにいえば、コンピュータだったからこそ一瞬だったわけで、ミラーラビン法を手計算や機械式計算で行うのは至難の技かと思います。あまりおすすめはしませんが、興味がある方はやってみてください。


目次

きっかけ

Ferrierの素数を知ったきっかけは鈴木貫太郎さんのYouTube動画でした。
www.youtube.com

動画ではこの数の桁数を求める計算を行っていましたが、そのコメント欄に次のようなことが書かれていました：

『この数は「電子計算機を用いずに導かれた最大の素数」としてちょっと有名な数だそうですね。』


なんですって！？

気になって調べてみると、たしかにWikipediaにもそのようなことが書かれています！
ja.wikipedia.org


これは面白い！

どういう経緯で、そしてどんな方法でこの大きな素数を素数だと判定できたのでしょうか。気になって調べてみたというのが今回の記事の経緯です。

単に素数判定といってもそれほど簡単なわけではなく、本当にさまざまな道具・定理が登場します。とても面白いので、ぜひ最後までご覧ください。



巨大な素数発見の歴史

フェリアーの素数の位置付けを理解するために、巨大な素数発見の歴史を簡単にまとめてみましょう。関連する歴史については、以下のページに詳しく書いてありました。

http://www.numericana.com/answer/primes.htm#history


フェリアー以前の話です。まず、1876年にリュカが

2^{127}-1

という 39桁 の素数を発見しています。この数は、いわゆるメルセンヌ数と呼ばれるタイプの数になっていて、このタイプの素数を（高速に）判定できるリュカテスト（リュカ本人が発明）が用いられました。

そこから75年もの間、この数が人類が発見した最も大きな素数であり続けました。


1951年の5月〜6月にかけて、突破口が訪れます。ミラーとホイーラーによって 41桁と42桁 の素数が立て続けに 11個 も発見されたのです。

114\cdot (2^{127}-1) + 1,
124\cdot (2^{127}-1) + 1,
388\cdot (2^{127}-1) + 1,
408\cdot (2^{127}-1) + 1,
498\cdot (2^{127}-1) + 1,
696\cdot (2^{127}-1) + 1,
738\cdot (2^{127}-1) + 1,
774\cdot (2^{127}-1) + 1,
780\cdot (2^{127}-1) + 1,
934\cdot (2^{127}-1) + 1,
978\cdot (2^{127}-1) + 1

そのときに使われたのが、EDSAC と呼ばれる「世界初の（実用的な）プログラム内蔵方式の電子計算機」でした。まさにコンピュータの時代の幕開けといったところでしょうか。


Copyright Computer Laboratory, University of Cambridge.

一方、面白いことに同じ年である1951年に、フェリアーが冒頭で紹介した

\displaystyle N = \frac{2^{148}+1}{17}

を発見しました。これは 44桁 の素数でした。


さらにほぼ同時期に、ミラーとホイーラーによって今度はなんと 79桁 の素数が発見されました。

180 \cdot (2^{127} - 1 )^2 + 1

怒涛の勢いで最大素数が発見されています。同じ1951年に、75年間更新されなかった最大素数の記録が、これほどまでにたくさん更新されたというのはすごいことでえすね。1951年は、巨大な素数発見の歴史において大豊作の年だったというわけです。


これらの素数の発見の順序は、あまり明確ではないようなのですが、どうも次のような順番だったようです。

  1. ミラーとホイーラー41桁・42桁
  2. ミラーとホイーラー79桁
  3. フェリアー44桁

つまり、ミラーとホイーラーが最大の座を常に先行しており、フェリアーが最大素数の座につくことはなかったことになります。本来ならばフェリアーの素数が最大素数の記録に残ることはないはずでした。

ところが、ミラーとホイーラーは79桁の素数を発表した際に、フェリアーの発見した44桁を付記した上で、どちらも7月初旬に見つけたと発表したのです。これがフェリアーの素数が最大素数の記録に載ることになった経緯です。



このように、たまたま巨大素数の発見の歴史に名を連ねたフェリアーの素数ですが、実はまた別の理由によっても注目を集めています。彼の素数は 「電子計算機」を用いずに計算された という経緯があるからです。

ここでいう「電子計算機を使わない」という意味ですが、機械式計算機で計算されたことを意味します。いわゆる手回し計算機ですね。


私物の機械式計算機です

しかしながら、フェリアーの素数ほどの巨大な素数を判定するのに、電子計算機が使われていないというのは、基本的に電子計算機を用いて素数探索が行われている現代においては驚きの成果と言えます。

これ以降も「電子計算機を使わないで発見された最大の素数」の記録は更新されていません。今後これを抜く素数は現れないのではないかと思われます。



道具その１：Pocklingtonの定理

それでは、実際にフェリアーの素数を判定する方法について説明したいと思いますが、そのために必要な道具を ２つ 紹介します。


１つめの道具はPocklingtonの定理です。

その前に、まず基本的な判定方法として、フェルマーテスト と呼ばれる方法について説明します。


p を素数とします。 p と互いに素な任意の整数 a に対して

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

が成り立つ、というのがフェルマーの小定理でした。


逆に、 N を正の整数として、 N 未満の a をランダムにいくつか取り

a^{N-1} \equiv 1 \pmod{N} \tag{3}

がいずれの a でも成り立たないのであれば、 N は素数「だろう」と判定するのがフェルマーテストです。

(3) が成り立つ a が一つでもあれば、（フェルマーの小定理の対偶により）合成数であることが確定します。


一方で、フェルマーの小定理の逆

任意の N と互いに素な a について a^{N-1} \equiv 1 \pmod{N} \; \Longrightarrow \; N は素数

は必ずしも成り立ちません。

たとえば、 N = 561 という数は互いに素な任意の a について条件を満たしますが、 561 = 3\times 11\times 17 となり素数ではありません。こういう数を、カーマイケル数と言ったりしますね。



ここで、どういう条件を加えたらフェルマーの小定理の逆が成立するのか？という問題が生まれます。

この問題に対して、一つの面白い条件を与えるのが Pocklingtonの定理 です。

Pocklingtonの定理
N を2以上の整数とし、 N-1 = Rq^n（ここで、 q を素数とし、 q は R を割り切らない）とする。

もし、ある整数 a が存在して

a^{N-1} \equiv 1 \pmod{N} \; かつ \; \operatorname{GCD}(a^{(N-1)/q} - 1, \,N) = 1

が成り立つならば、 N の素因数 p は p = q^n m + 1 の形に限定される。


条件がたくさんあるので複雑な主張に見えますが、1個ずつ条件を考えれば理解できるかと思います。

まず、フェルマーテストの条件

a^{N-1} \equiv 1 \pmod{N} \tag{3再掲}

が入っていますね。

あとは、 N-1 の素因数 q を考えて、それが

\operatorname{GCD}(a^{(N-1)/q} - 1, \,N) = 1 \tag{4}

という付加条件を満たすのであれば、 N の素因数 p は

p = q^n m + 1 \tag{5}

という形に限定されるというわけです。（ n は q が N を割り切る回数に一致する。）


あとは、この p として、 N 未満のものが存在しないことがわかれば（もっというと、 \sqrt{N} 以下まで考えれば良い）、 N が素数であることが判定できるわけです。



N の素因数を直接考える代わりに、 N-1 の素因数 を考えているのが面白いですね。 N の素因数分解が難しくても、 N-1 の分解は比較的容易にできる、というケースはあります。実際、あとでやるように、フェリアーの素数がそのような形になっています。



それでは、Pocklingtonの定理を証明しましょう。

（証明）
p を N の素因数とする。ここで、 e を a の \bmod{p} における位数とする。つまり、 e を
a^{e} \equiv 1 \pmod{p}

を満たす最小の e > 0 とする。

一方で、 (3) の条件 a^{N-1} \equiv 1 \pmod{N} より、 \bmod{p} をとると

a^{N-1} \equiv 1 \pmod{p}

が成り立つ。したがって、位数の最小性により e \mid N-1 が成り立つ。

ここでもし e が (N-1)/q も割り切るのであれば、 a^{(N-1)/q} \equiv 1 \pmod{N} になるが、これは条件 \operatorname{GCD}(a^{(N-1)/q} - 1, \; N) = 1 に反する。したがって、 e \nmid (N-1)/q が成り立つ。

つまり

e \mid N-1 = R q^n \; かつ \; e \nmid (N-1)/q = R q^{n-1}

が言えた。このことは

q^n \mid e

を意味する。

また、フェルマーの小定理より

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

が成り立つので e \mid p-1 である。したがって、 q^n \mid p-1 である。

以上から、 p = q^n m + 1 と表せることが示された。

（証明終わり）


道具その２：Legendreの定理

今回証明したいのは、 N = \frac{2^{148} + 1}{17} という形の数の素数性です。これを議論するためには、 17N の素因数が 17 と N だけであることを示す必要があります。

ここで、 17N = 2^{148} + 1 という数は

X^n + Y^n

という形をしています。

X^n - Y^n
X^n + Y^n

というタイプの数について、素因数の形についての情報を教えてくれるのがLegendreの定理です。


さて、この形の数は、 X, Y を変数と思ったときの「多項式の因数分解」を使って素因子のヒントを割り出すことができます。

たとえば n = 2 のときは、よく知られているように

X^2 - Y^2 = (X - Y)(X + Y)

と分解できますね。 X^2 + Y^2 の方はこれ以上は（ \mathbb{Q} 上では）分解できません。（つまり、既約というわけです。）


より一般に、 n = uv と表すと X^n - Y^n は

X^{uv} - Y^{uv} = (X^u - Y^u) \{ (X^u)^{v-1} + (X^u)^{v-2}(Y^u) + \cdots + X^u (Y^u)^{v-2} + (Y^u)^{v-1} \}

と分解されます。

一方、 n = st（ t は奇数）と表せるとき X^n + Y^n は

X^{st} + Y^{st} = (X^s + Y^s)\{ (X^s)^{t-1} - (X^s)^{t-2} Y^s + \cdots - X^s (Y^s)^{t-2} + (Y^s)^{t-1} \}

と分解されます。

ただし、２番目の方は t が奇数という条件が付いていることに注意します。そうでないと、右辺の符号を \pm に交互に置いたときに不整合が起きてしまうからです。


したがって、 N = X^n \pm Y^n という数が、多項式の中で分解ができるのであれば、 N の素因数 p はその分解されたいずれかの因子を割ることになるわけです。多項式の分解によって得られる因子のことを 代数的因子 と呼ぶことにしましょう。


さてこのとき、Legendreの定理は次のような定理です。

Legendreの定理
(i) N = a^n + b^n とし a, b は互いに素であるとする。 p を N の任意の素因数とすると、 p は次のいずれかとなる：
  • p = 2kn + 1（ただし、 k は整数）
  • a^n + b^n の代数的因子であって、 a^m \pm b^m（ m < n）の形のものを割り切るような p である

(ii) N = a^n - b^n とし a, b は互いに素であるとする。 p を N の任意の素因数とすると、 p は次のいずれかとなる：

  • p = kn + 1（ただし、 k は整数）
  • a^n - b^n の代数的因子であって、 a^m \pm b^m（ m < n）の形のものを割り切るような p である

（証明）
(i) のケースだけ証明する（(ii)の方もほぼ同様に進む）。

N = a^n + b^n（ \operatorname{GCD}(a, b) = 1）と仮定し、 p を N の素因子とする。すると

a^n + b^n \equiv 0 \pmod{p}

と表せる。このとき、 p \mid a ならば p \mid b でもあり、したがって p \mid \operatorname{GCD}(a, b) である。　

したがって、 (a, b) = 1 より p \nmid a, b であるから、 a, b \in (\mathbb{Z}/p\mathbb{Z})^\times である。 a^n + b^n \equiv 0 \pmod{p} より、 b^{-n} をかけて

(ab^{-1})^n \equiv -1 \pmod{p}

である。 x = ab^{-1} とおくと

x^n \equiv -1 \pmod{p}

である。

ここで、 x の \bmod{p} における位数を d とする（つまり、 x^d \equiv 1 \pmod{p} なる最小の d > 0 をとる）。フェルマーの小定理より x^{p-1} \equiv 1 \pmod{p} であるから、 d \mid p-1 がいえる。よって d = \frac{p-1}{k} なる k が存在する。

ここで、 x^n \equiv -1 \pmod{p} より x^{2n} \equiv 1 \pmod{p} であるから、同様に d \mid 2n であるから n = l \frac{d}{2} である。もし仮に、 l が偶数であれば、 l = 2l' として n = 2l' \cdot \frac{d}{2} = l' d となり、これは x^n \equiv -1 かつ x^d \equiv 1 に反する。ゆえに、 l は奇数である。

したがって

\displaystyle n = (2l' - 1) \frac{d}{2}

と表せる。

さらに、もし仮に l' > 1 だとすると、 \frac{d}{2} < n となり d は \bmod{p} における x の位数であるから x^{\frac{d}{2}} \equiv -1 \pmod{p} であり、 x = ab^{-1} より

a^{\frac{d}{2}} + b^{\frac{d}{2}} \equiv 0 \pmod{p}

である。これは p が「代数的因子 a^\frac{d}{2} + b^{\frac{d}{2}}」を割り切るパターンである。

一方、 l' = 1 とすると

\displaystyle n = \frac{d}{2} = \frac{p-1}{2k}

であり、これは p = 2kn + 1 を導く。

（証明終わり）

本題：フェリアーの素数が素数であることの証明

それでは本題の証明にいきましょう。つまり

\displaystyle N = \frac{2^{148}+1}{17} \tag{1再掲}

が素数であることを証明しましょう。以下、 N と書いたらこの数を表すことにします。

なお、この節の内容については正直言って分からないことだらけです。私がよく分かっていない部分は、分かっていないと明示した上で、先に進むことにします。その点ご了承ください。

初手からどうしたらよいか悩むと思いますが、Pocklingtonの定理を適用するために N-1 を計算するのが上手いやり方です。

\displaystyle \begin{align*} N-1 &= \frac{2^{148}+1}{17} - 1 \\ &= \frac{2^{148}+1 - 17}{17} \\ &= \frac{2^{148} - 16}{17} \\ &= \frac{2^4(2^{144} - 1)}{17} \\ &= \frac{2^4(2^{72} - 1)(2^{72} + 1)}{17} \end{align*} \tag{6}

最初にこれを見たときは「うわー、なるほどー、まじかー、その手があったかー」という感想でした。自力で証明しようと思ったときは、まったく思いつかなかったので、こんなうまいこと分解できるものなのかと感心しましたね。

Pocklingtonの定理を使うためには、 N-1 の素因数が必要になるわけですが、これが 2^4 か 2^{72}-1 か 2^{72}+1 のいずれかの約数であることが分かってしまうわけですね。


N-1 の「大きめの素因数」を探すために、 2^{72} - 1 か 2^{72}+1 の中の素因数を探索したいと思います。

結論をいうと、 2^{72}+1 の素因数として

q = 487824887233 \tag{7}

が見つかります。しかし、いったいどうやってこれを見つけたのか、そしてこれが素数であることがわかるのか・・・。

q を見つけるのはLegendreの定理を使えばできそうです。しかしながら、 q が素数であることについては、正直なところよい方法がわかりません。このことについては、記事の最後で補足的に議論したいと思います。ここではいったん先に進みましょう。


さて、これにて N-1 が、互いに素な因数 q, R を用いて

N - 1 = q R \;\;\;\;\;\; (q = 487824887233) \tag{8}

と書けることが分かりました。



ここで、 3 を用いると

3^{N-1} \equiv 1 \pmod{N} \tag{9}

が成り立つそうです。（いったいどうやって示す？）


また、フェリアーは

\operatorname{GCD}(3^{17(N-1)/q} -1, \; N) = 1 \tag{10}

であることも示しました。（いったいどうやって示す？）

式 (10) から

\operatorname{GCD}(3^{(N-1)/q} -1, \; N) = 1 \tag{11}

であることが、枠内の議論によって導かれます。

(10) \; \Longrightarrow \; (11) を示すために
\operatorname{GCD}(3^{(N-1)/q} -1, \; N) = d

として d = 1 を導きます。

約数の定義より

d \mid 3^{(N-1)/q} -1 かつ d \mid N

が成立します。前者より

3^{(N-1)/q} \equiv 1 \pmod{d}

が成り立つわけですが、この両辺を 17 乗して

3^{17(N-1)/q} \equiv 1 \pmod{d}

すなわち

d \mid 3^{17(N-1)/q} - 1

が成立します。このことは

d \mid \operatorname{GCD}(3^{17(N-1)/q} - 1, \; N)

を意味しますが、式 (10) よりこれは d = 1 でしかありえません。


式 (9)、かつ、式 (11)、つまり

3^{N-1} \equiv 1 \pmod{N} \; かつ \; \operatorname{GCD}(3^{(N-1)/q} -1, \; N) = 1

が成立することから、 a = 3 としてPocklingtonの定理の仮定を満たします。

したがって、 N の任意の素因数 p は

p = q m + 1 \tag{12}

の形に限定されることが分かりました。

q = 487824887233 はかなり大きな数なので、このような形にできたのは大きいですね。



さて一方、 N を 17 倍した 17N = 2^{148} + 1 は、 X = 2, \; Y = 1 として

17N = X^{148} + Y^{148} \tag{13}

のように表せます。今考えたいのは 17N の 17 以外の素因子です。これはLegendreの定理が使える形になっていますので、式 (13) の代数的因子を考えます。

まず、指数について 148 = 2^2 \cdot 37 と表せますので、 148 = s t（ t は奇数）の形の非自明な分解を考えると、

s = 4, \;\; t = 37

の形しかありえません。そこで

X^{148} + Y^{148} = (X^4 + Y^4) \times \{ (X^4)^{36} - (X^4)^{35} Y^4 + \cdots - X^4 (Y^4)^{35} + (Y^4)^{36} \} \tag{14}

なる分解を考えます。このとき X^4 + Y^4 = 2^4 + 1 = 17 なので、 17 が代数的因子 X^4 + Y^4 の素因子となります。（この場合は 17 自身が X^4+Y^4 に一致するケース。）

それ以外の素因子 p \mid N は、Legendreの定理により必ず

p = 296k + 1 \tag{15}

の形に限定されます。


つまり、式 (12) と式 (15) によって、 N の任意の素因数 p は

\begin{align*} p &= 487824887233 m + 1 \\ &= 296 k + 1 \end{align*}

の形で表せるということがわかったわけです。

487824887233 と 296 は互いに素なので、中国剰余定理より

p = Q y + 1 \;\;\;\;\;\; (y = 1, 2, 3, \cdots) \tag{16}

と表せることがわかりました。ここで、 Q = 296\times 487824887233 = 144396166620968 です。


式 (16) の p を y を変数と見て p(y) と表します。

すると、 p(1), p(2), \ldots, p(11) は素数ではありません。しかもありがたいことに、結構小さな素数で割り切れます。

実際、次のように、 29 以下の素数で割り切れます：

\begin{align*} 3 \mid p(1) &= 144396166620969 \\ 7 \mid p(2) &= 288792333241937 \\ 5 \mid p(3) &= 433188499862905 \\ 3 \mid p(4) &= 577584666483873 \\ 17 \mid p(5) &= 721980833104841 \\ 11 \mid p(6) &= 866376999725809 \\ 3 \mid p(7) &= 1010773166346777 \\ 5 \mid p(8) &= 1155169332967745 \\ 7 \mid p(9) &= 1299565499588713 \\ 3 \mid p(10) &= 1443961666209681 \\ 29 \mid p(11) &= 1588357832830649 \end{align*}

したがって、 N の素因数 p が存在するとしたら、それは p(12) = 1732753999451617 以上ということになります。つまり

p > p(12) - 1 = 1732753999451616 \tag{17}

ということですね。



最後に、素因数分解の フェルマー法 という方法を使います。

N の非自明な素因数 p があるとき N = p \cdot \frac{N}{p} と表せます。ここで、 p < \frac{N}{p}（つまり、 p < \sqrt{N} ということ）と仮定しておきます。このような素因数が存在すると仮定して、矛盾を導きます。

N が奇数であれば、 p も N/p も奇数です。したがって両者の和も差も偶数です。よって

\displaystyle \begin{align*} A &:= \frac{p + N/p}{2} \\ B &:= \frac{p - N/p}{2} \end{align*} \tag{18}

とおくと、これは整数であり

\displaystyle \begin{align*} p &= A - B \\ N/p &= A + B \end{align*} \tag{19}

とできます。

すなわち

\displaystyle N = p \cdot \frac{N}{p} = (A-B)(A+B) = A^2 - B^2 \tag{20}

と表せます。

ここで

\displaystyle 2A = (A - B) + (A + B) = p + \frac{N}{p}

です。 p を最小の素因子とすると、式 (17) と合わせて

1732753999451616 < p < \sqrt{N}

が成り立ちます。したがって

\displaystyle 2A = p + \frac{N}{p} < \sqrt{N} + \frac{N}{1732753999451616} < 1.3 \times 10^{28} \tag{21}

が得られます。


一方で、 N の因子である p と N/p は、式 (16) よりどちらも Qy + 1 型の数でなければなりません。（ N/p は合成数かもしれませんが、その素因数はやはり Qy + 1 型なので、結果的に N/p も Qy + 1 型になります。）

したがって、 p = Qy + 1, \;\; N/p = Qz + 1 とおくと、次の計算が成り立ちます：

\begin{align*} N+1 &= (Qy + 1)(Qz + 1) + 1 = Q^2yz + (Qy + 1) + (Qz + 1) \\ &= Q^2 yz + p + N/p \\ &= Q^2 yz + 2A \\ & \equiv 2A \pmod{Q^2} \end{align*} \tag{22}

ここで、 N + 1 を Q^2 で割ったあまりを考えると、

N+1 \equiv 18859780871263549663161494450 \pmod{Q^2} \tag{23}

となりますが、これが 2A と合同より 2A > 1.8\cdot 10^{28} であることがわかります。これは不等式 (21) の評価 2A < 1.3\times 10^{28} に矛盾します。


したがって、 N に非自明な素因数は存在しない、すなわち N が素数であることが証明されました。


おわりに

いかがだったでしょうか。一部証明が簡潔していない部分は残りましたが、 N = \frac{2^{148}+1}{17} が素数であると思えるような根拠は説明できたのではないかと思います。

使った道具もたくさんあって、その意味でも面白かったですね。初等整数論の技術の見本市という感じでした。実際、次のような定理・道具が使われていました：

  • フェルマーの小定理
  • フェルマーテスト
  • Pocklingtonの定理
  • Legendreの定理
  • 中国剰余定理
  • フェルマーの素因数分解法

こんなに面白い数学的な事実を知ることができて、とても楽しかったです。

それでは今日はこの辺で！


P.S.
ちなみに、今回の話を居酒屋で彼女にしたのですが、それがツイートになり、そしてバズりました。笑





補足： 2^{72}+1 の素因数分解

途中の議論において、 N-1 が素因子として q = 487824887233 なる大きな素数を持つことを主張しましたが、どうやってそんなことが示せるのでしょうか。

私の力では証明しきれなかったのですが、「もしかするとこういうことなんじゃないか」というアイデアだけ述べたいと思います。


N-1 = \frac{2^4(2^{72}-1)(2^{72}+1)}{17} より、 2^{72}-1, \; 2^{72}+1 のいずれかに存在する大きな素因子があることを期待して素因数分解します。

なお、下記枠内の議論により、 2^{72}-1, \; 2^{72}+1 は共通の素因数を持ちませんので、 q が入っているのはどちらか一方です。（実際、 2^{72}+1 に入っています。）

2^{72} + 1 と 2^{72} - 1 は、差をとると
(2^{72} + 1) - (2^{72} - 1) = 2

なので、最大公約数は 1 です。つまり、 2^{72} + 1 と 2^{72} - 1 は互いに素。

共通の素因数はありませんので、素因数 q が 2^{72} - 1 を割り切るならば、 2^{72} + 1 を割り切ることはありません。逆も然りです。


2^{72} + 1 の素因数 p を考えたいと思いますが、ここでLegendreの定理を使います。

まず、代数的因子の方ですが、 72 = 2^3 \cdot 3^2 なので 72 = 24 \cdot 3 = 8 \cdot 9 という2通りの分け方ができます。したがって

\begin{align*} 2^{72} + 1 &= (2^{24} + 1) \times \{ (2^{24})^2 - 2^{24} + 1 \} \\ &= (2^{8} + 1) \times \{ (2^{8})^8 - (2^{8})^7 + \cdots - 2^8 + 1 \} \end{align*}

なる2通りの分解が得られます。ここでさらに 2^{24} + 1 の代数的因子を考えると 257 = 2^8 + 1 \mid 2^{24} + 1 であることも分かります。


よって、 2^{24} + 1 = 16777217 を割り切る素因子と (2^{24})^2 - 2^{24} + 1 = 281474959933441 を割り切る素因子の2通りを考えれば良いことになります。


なお、先ほどの議論により前者は 257 で割り切れるので

\displaystyle \frac{2^{24} + 1}{257} = 65281

を考えればよいわけですが、この素因子 p も 2^{24}+1 にLegengreの定理を適用することで、 p = 48k+1 型に限定されることがわかるので、結果として 65281 = 97 \times 673 がすぐに見つかります。


問題は、後者の

\displaystyle \frac{2^{72} + 1}{2^{24}+1} = (2^{24})^2 - 2^{24} + 1 = 281474959933441

の方です。Legendreの定理を 2^{72}+1 に適用すると、この数の素因子 p は p = 144k + 1 型に限定されます。

したがって、いくつかの k を試せば p = 144\cdot 4 + 1 = 577 で割り切れることがわかります。すると

281474959933441 = 577 \times {\bf 487824887233}

となり、確かに q = 487824887233 が出てきます。


結果をまとめると

\displaystyle 2^{72} + 1 = 97 \times 673 \times 577 \times {\bf 487824887233}

という分解が得られたわけですが、まだ q = 487824887233 が素数だということは分かりません。


先ほどの議論により、 q = 487824887233 が割り切れるとすると、その素因子は p = 144k + 1 型に限定されますので、 \sqrt{q} = 698444.620\cdots までひたすら調べていけば確かに示せるはずですが・・・。そんな面倒なことをやったのでしょうか。。。



参考文献

今回の記事の証明は、基本的にこちらの本の内容を参考にしています。

Prime Numbers and Computer Methods for Factorization (Progress in Mathematics)

Prime Numbers and Computer Methods for Factorization (Progress in Mathematics)

Amazon

*1:Ferrierのカタカナ表記については、定番のものはなさそうに思えます。今回はHardy and wrightの本の表記を参考にしました：

数論入門 I (シュプリンガー数学クラシックス 第)

数論入門 I (シュプリンガー数学クラシックス 第)

Amazon