ソフィー・ジェルマンの冒険（遊びの数論38）
他のメモへのリンク集。リンク集を飛ばして、このページの前書きへ。本文の目次へ。21、22などの数字は、メモの番号です。
21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
きちんとまとまった記事ではなく、雑多なメモ。誤字脱字・間違いがあるかもしれません。
- 目次。約10の項目があります。2025などの数字は、メモの日付です。
- 2025-02-06 ジェルマン素数とその周辺 リアル「ベルばら」
- 2025-02-08 ジェルマン素数とその周辺（その2） 定理3・定理4
- 2025-02-09 賞金15万ドルをもらう便乗チート？ 余談
- 2025-02-09 ジェルマン素数とその周辺（その3） 定理5
- 2025-02-11 ジェルマン素数とその周辺（その4） 定理4とPSP
- 2025-02-13 ジェルマン素数とその周辺（その5） 定理4の分析
- 2025-02-15 Hardy–Wright の「定理101」を改善
- 2025-02-17 幅 + 高さが 10 cm の長方形の面積
- 2025-02-22 「30 の約数だが 10 の約数ではない数」は？
- 2025-02-24 1387 と 1729 6億3531万8657の秘密
- 2025-03-01 Hardy–Wright の「定理101」を拡張 定理6
- 2025-03-06 (4⋅3)3 + 1 = (4⋅3 + 1)(44⋅3 + 1) さざ波のささやき
- 2025-03-19 x3 + y3 = 1729 のいろんな解 10⋅10⋅10 + 9⋅9⋅9 = 19⋅91
- 2025-03-10 再びメルセンヌ数とジェルマン素数 1000京は20桁
- 目次の終わり。このページの最初の項目が続きます。
2025-02-06 ジェルマン素数とその周辺 リアル「ベルばら」
18世紀のパリで生まれパリで死んだ Marie-Sophie Germain（マリー・ソフィー・ジェルマン）。その数奇な人生は、数論の歴史における「ベルサイユのばら」ともいえる。
フランス革命が勃発しバスティーユが陥落したとき、 Sophie は13歳の少女だった。自宅にこもって独学を始めたのも、革命の大混乱のため外出は危険だったかららしい。革命後の恐怖政治の時代、学問は心の慰め・避難所ともなっただろう。
当時「数学は女のすることではない」というのが社会常識だった。数学者になりたいという Sophie は、両親の強い反対に遭った。他の数学者に手紙を書くときには、ムッシュー・ルブラン（M LeBlanc）という偽名を使い、男性に成り済ました。「女と知られると真面目に読んでもらえないかも」と心配したらしい。 LeBlanc はありふれた姓だが、フランス語で「白」という意味――可憐なペンネームの選択だ。
史実として Germain の業績は国際的な強い影響力を持ち、100年以上にわたって Fermat の最終定理の研究を方向づけることになる。 Legendre の整数論の一部も、実質的には Germain が書いたらしい。――そんな人が、女だからという理由で最高学府 École Polytechnique に入学できないというのは、理不尽だ。革命では「自由・平等」をモットーに民衆が勝利したということになってるけど、実情はあまり平等でもなかったようだ。
Germain はドイツの Gauß に対しても正体を秘密にして、「LeBlanc」で通していた。ところがナポレオン戦争でフランスがドイツに攻め込んだとき、「どうか Gauß 様には、危害を加えませんよう」と将軍に懇願し、その結果…。将軍は直々に Gauß の安否を確かめに行き「ご友人の Sophie Germain 様が心配しておられました」などと告げたのだろうか。 Gauß は「はてな、自分にはそんな名の友人はいないぞ。 Sophie Germain って誰だろう」と不審に思い、それがきっかけで LeBlanc の正体がばれてしまった。さいわい Gauß は、 Germain の正体を知って驚きこそすれ、女だからといって軽視するような人ではなかった。もとより数論の定理は普遍的なもので、人種・性別などによって評価が変わるものではない。けれど Germain はこのとき、「女と知られたら、それで終わりかもしれない。でも Gauß の身の安全が第一」と、内心のジレンマを感じていたに違いない。
21世紀の現代では「女は数学をできない」などと考える人は、ほとんどいないだろう。実際、女の研究者は珍しくないし、数学教師はむしろ女性の方が多いかも。けれどこの種の問題が、なくなったわけでもない。不合理な社会通念・制度のせいで苦しむ人、他の人と少々違うというだけでいじめられる者は少なくないし、構造的な不平等――強者・強国による横暴――も、総体的には、どんどんひどくなっていくようだ。
しかし新しい世代の若い人々は、昔の人より多様性について受容的で、考え方も柔軟だろう。古い常識にとらわれず、「画一化・愚民化教育」の箱の外に出てくる人も多いに違いない――自分が心から面白いと思える分野に情熱を傾け、地道な努力を続け、さまざまなことを学んで視野を広げつつ。国益・既得権益が絡む国レベルの交渉では、山積する社会問題・環境問題の解決は難しそうだが、「地球人」が個人レベルで取り組むなら、道が開ける可能性は十分にある。100人オーダーの各国首脳と違い、「地球人」は何十億人もいる。自由な情報交換から、いろいろなアイデア、画期的なアイデアが出てくるかもしれない。
Mersenne 数への応用と拡張
p と 2p+1 がどちらも素数のとき、 p は Sophie Germain 素数と呼ばれる。例えば p = 11 と 2p+1 = 23 はどちらも素数なので、 11 は Sophie Germain 素数。一方、 p = 7 のとき 2p+1 = 15 は素数でないので、 7 は（素数ではあるが） Sophie Germain 素数ではない。
数論では人名にちなむ用語が多いが、普通は研究者の姓を冠する（例: 「Fermat の小定理」「Mersenne 素数」）。「Sophie Germain 素数」に限って、慣用的にフルネームが使われ Sophie という女性名を特筆することには、「優れた女性研究者の出現を記念する」という歴史的意味があるのだろう。けれど、女だから別扱いするということ自体、 Germain を苦しめた過去の軛（くびき）*1でもあるし、いちいち「Sophie Germain 素数」と書くのは面倒でもあるので、ここでは簡略に Germain 素数と呼ぶことにする。
Germain 素数の概念は、歴史的には Fermat の最終定理の研究と関連して生じてきたのだが、それ自体としても興味深く、他の幾つかの話題とも関連する。以下では Mersenne 数――それは 2n − 1 の形の数（n: 正の整数）である――との関係について記した上で、それをもう少し広い文脈から再分析してみたい。
*1 軛（くびき・ヤク）の字には「厄」が含まれているが、これは形声文字の音を表す部分で、災厄という意味ではないらしい。「共役複素数」などの「共役」は歴史的には代用の文字で、昔は「共軛」と表記されていた。「共にくびきにつながれ車を引く馬（あるいは牛）のように」互いに連携している――というほどの意味だろう。
巨大素数を見つけたら賞金6000万円
Mersenne 数は、素数になることも、ならないこともあるが、素数になる場合（Mersenne 素数）、一般には非常に巨大。現時点の新記録は M136279841 で、ほんの数カ月前（2024年10月）に素数であることが判明したが、約4100万桁もある。既知の最大の素数なので、当然ギネスブックのようなものにも載るだろうし、一般メディアのニュースにもなる。しかも EFF（電子フロンティア財団）*2は「1億桁以上の素数を最初に発見した人に15万ドル。10億桁以上の素数を最初に発見した人に25万ドル」といった巨額*3の懸賞金まで付けている。 Mersenne 数が素数か否かの判定は、数論としても計算機科学としても興味深い問題であり、場合によっては――もし十分大きな Mp が素数であることを突き止めれば――それだけで、大金持ちになれるかもしれない。
Mersenne 数の素数判定は、原理的には LLT という簡単なアルゴリズムを使って、誰でも実行できる。Mersenne 素数探しをする場合、n が素数でなければ Mn も素数でないので、素数 p に話を絞って Mp を考えればいい。
*2 1990年に設立された非営利団体 the Electronic Frontier Foundation は、インターネットに代表されるデジタル世界における「市民の自由」の擁護を目的としている。デジタル技術は便利である半面、情報が集約されるため、スパイウェア・監視社会・全体主義・ストーカー被害・プライバシー侵害といった特有の問題につながりやすい。 EFF は論説・自己防衛ガイドのようなものを公開したり、弾圧への対抗技術の開発を支援したりもしているが、特に技術者や不当な扱いを受けている人を弁護する立場から、多くの訴訟に関与・参加している。
*3 https://www.eff.org/awards/coop 現時点では、まだ1億桁に到達していない。二つの賞金を合わせると、合計40万ドル。1ドル150円として賞金総額6000万円。 EFF がこの懸賞金を付けているのは、分散コンピューティングを支援するため。ネット上において、草の根的、P2P的な（国や大企業に支配されない）つながりが、市民的自由の要となる――というような発想なのだろう。
その Mp は素数か？
5 以上の Mp が素数になるためには p が素数であることが必要。逆に p が素数だからといって Mp が素数になるとは限らない。素数かどうかを判定する方法が LLT だが、 LLT は仕組みは単純だけど計算量が多く、しかも Mersenne 素数の分布はまばらなので、素数が見つかる「確率」は、かなり低い。現状、1年以上かけて、新しい Mersenne 素数がやっと一つ見つかるかどうか、といった程度。
ところが特定の条件が満たされる場合には、 LLT を使うまでもなく、「素数でない」という判定が成り立つ。次の通り。
定理1 p が Germain 素数で、しかも p が 4 の倍数より 1 小さいなら、
Mersenne 数 Mp = 2p − 1
は、 2p+1 で割り切れる。従って、 M3 = 7 を例外とすると（この例外については後述）、このような Mp は素数ではない。
〔例〕 p = 11 は Germain 素数で、しかも 4 の倍数 12 より 1 小さい。従って、 M11 = 211 − 1 = 2047 は 2p+1 = 23 で割り切れる。実際 2047 = 23 × 89。
この定理は簡潔で美しい。「素数でない Mersenne 数を素因数分解すること」も重要な問題なので、このように素因数の一つが確定するのは、素晴らしい。
証明 仮定により p = 4k − 1 と書くことができる。それが Germain 素数なのだから、
2p + 1 = 2(4k − 1) + 1 = 8k − 1
も素数。その素数を q とすると q = 2p + 1、つまり p = (q−1)/2。
さて、素数 q = 2p+1 は上記のように 8k−1 型なので、第二補充法則と Euler の基準から、
2(q−1)/2 ≡ +1 (mod q) つまり 2p ≡ 1 (mod q)
∴ 2p − 1 ≡ 0 (mod q)
となる。∎
4k − 1 型の Germain 素数（愛称*4: チョコレート・ソフィー）は、100 以下に四つある:
① p = 3 ⇒ q = 2p+1 = 7 も素数
② p = 11 ⇒ q = 2p+1 = 23 も素数
③ p = 23 ⇒ q = 2p+1 = 47 も素数
④ p = 83 ⇒ q = 2p+1 = 167 も素数
このうち①～③の各 p, q が素数であることは、一目瞭然だろう。④の p = 83 に自分自身以外の素因数 d があるとすれば、それは 10 未満なので*5、 d = 2, 3, 5, 7 の可能性があるが、 83 が 2 or 3 or 5 で割り切れないことは明白*6。 7 で割り切れないことも、容易に確かめられる。同様に q = 167 に 1 と自分自身以外の素因数 d があるとすれば、それは 13 未満だが*7、 167 が 2, 3, 5, 11 で割り切れないことは一目瞭然*8、 167 は 13 の倍数 132 = 169 より 2 小さいので 13 で割り切れるわけもなく、実質 7 で割り切れないことだけを確かめればいい（その確認は難しくない）。
定理1から:
① M3 = 23 − 1 = 7 は q = 7 で割り切れる
② M11 = 211 − 1 = 2047 は q = 23 で割り切れる
③ M23 = 223 − 1 = 838万8607 は q = 47 で割り切れる
④ M83 = 283 − 1 = 9𥝱6714垓0655京6917兆0333億9764万9407 は q = 167 で割り切れる
①で「M3 は q = 7 で割り切れる」といっても、 7 は M3 自身であり、 M3 は 1 と自分自身でしか割り切れない数、つまり素数。これは Mp が素数かどうかの判定という意味では、例外的ケースに当たる。②以降では q は Mp 自身ではなく、従って Mp は合成数（素数でない）。
*4 「4 の倍数より 1 大きい数」（言い換えると 4 で割って 1 余る数）を「バニラ」、 「4 の倍数より 1 小さい数」（言い換えると 4 で割って 3 余る数）を「チョコレート」または「チョコ」と呼ぶ。例えば、5 と 13 は「バニラ素数」、 3 と 7 と 11 は「チョコレート素数」。これらは筆者が勝手に使っている表現で、正式な用語ではない！
*5 もしも 83 = d × e と分解されるとしたら（d, e: 素数）、 d, e の少なくとも一方は 10 未満。なぜなら d, e が両方とも 10 以上なら d × e は 100 以上なので 83 と等しくなるわけない。二つの因数を小さい順に d, e と呼ぶことにすると、 d は 10 未満。実際には 83 は 10 未満の素数 2, 3, 5, 7 のどれでも割り切れないので、 83 = d × e という分解は不可能。もしも 83 = d × e × f のように三つの素因子に分解されるとしたら、最小の素因数 d はますます小さくならねばならず、そのような分解はますます不可能（同様に、四つ以上の素因子に分解される可能性はない）。結局 83 は 1 と自分自身以外の因数を持たず、つまり素数だ。
*6 桁の和が 3 の倍数でない数は 3 で割り切れない。 83 の場合、桁の和 8 + 3 = 11 は 3 の倍数ではない。この和では、 3 の倍数の桁 3, 6, 9 があれば、それを無視してもいい。つまり 83 では「8 は 3 で割り切れないから、 83 も 3 で割り切れない」。
*7 もしも 167 = de と分解されるとしたら（d, e: 素数）、 d, e の少なくとも一方は 13 未満。なぜなら d, e が両方とも 13 以上なら de は 132 = 169 以上なので 167 と等しくなるわけない（*5参照）。
*8 1 + 7 = 8 は 3 で割り切れないので 167 は 3 で割り切れない（*6参照）。さて3桁の数が 11 で割り切れるためには、「外側の二つの桁の和」が「真ん中の桁」と等しくなるか、またはこの和が「真ん中の桁」よりちょうど 11 大きくなる必要がある。 167 の場合 1 + 7 = 8 は、真ん中の桁「6」と等しくないし、「6」より 11 大きいわけでもないので、 167 は 11 で割り切れない。 167 の場合、筆算方式で考えても、 11 では割り切れないことは簡単に分かる（まず商が 1 で 57 が残って、その 57 を 11 で割れば、商が 5 で 2 余る）。
4 の倍数より 1 大きい Germain 素数は？
Germain 素数を利用した定理1は、一部の Mp が合成数であることを判定し、その一つの素因数を見つけるのに役立つが、 p が Germain 素数なら必ず成り立つわけではなく、 p について「4 の倍数より 1 小さい」という付帯条件が付いている。 Germain 素数の中には「4 の倍数より 1 大きい」タイプもある。小さい順に、最初の二つの例は:
p = 5 ⇒ q = 2p+1 = 11 も素数
p = 29 ⇒ q = 2p+1 = 59 も素数
このタイプの Germain 素数（愛称: バニラ・ソフィー）は、「チョコレート・ソフィー」と違って Mersenne 数との関係では役立たない。実際、 p = 5 のとき、
M5 = 25 − 1 = 31
は素数であり、 2p+1 = 11 で割り切れないし、 p = 29 のとき、
M29 = 229 − 1 = 536870911 = 233 × 1103 × 2089
は合成数だが、 2p+1 = 59 で割り切れるわけではない。
「バニラ・ソフィー」は 2p − 1 との関係では役立たないが、「1」の前の符号を逆にした 2p + 1 の形の数の分解において、役立つことがある。次の通り。
定理2 p が Germain 素数で、しかも p が 4 の倍数より 1 大きいなら、 2p + 1 は 2p+1 で割り切れる。
〔例1〕 p = 5 は、このタイプの Germain 素数。 25 + 1 = 33 は 2p+1 = 11 で割り切れる。
〔例2〕 同様に p = 29 とすると、 229 + 1 = 536870913 は 2p+1 = 59 で割り切れる。
証明は、定理1の証明とほとんど同じ（一部の符号が変わるだけ）。
証明 仮定により p = 4k + 1 と書くことができる。それが Germain 素数なのだから、
2p + 1 = 2(4k + 1) + 1 = 8k + 3
も素数。その素数を q とすると q = 2p + 1、つまり p = (q−1)/2。
さて、素数 q = 2p+1 は上記のように 8k+3 型なので、第二補充法則と Euler の基準から、
2(q−1)/2 ≡ −1 (mod q) つまり 2p ≡ −1 (mod q)
∴ 2p + 1 ≡ 0 (mod q)
となる。∎
例1の 33 = 3 × 11 は、定理2を使うまでもなく一目瞭然だが、例2の数を分解したい場合、定理2は役立つだろう。完全に素因数分解すると:
229 + 1 = 3 × 59 × 3033169
100 以下の範囲には、上記 5, 29 の他にも「バニラ・ソフィー」があと三つある:
① p = 41 ⇒ q = 2p+1 = 83 も素数
② p = 53 ⇒ q = 2p+1 = 107 も素数
③ p = 89 ⇒ q = 2p+1 = 179 も素数
これらの Germain 素数 p に対応する 2p + 1 は、それぞれ q = 2p+1 で割り切れる:
① 241 + 1 = 3 × 83 × 8831418697
② 253 + 1 = 3 × 107 × 28059810762433
③ 289 + 1 = 3 × 179 × 62020897 × 18584774046020617
今回の内容をまとめると: p が「チョコレート・ソフィー」なら 2p − 1 は 2p+1 で割り切れ、 p が「バニラ・ソフィー」なら 2p + 1 は 2p+1 で割り切れる。特に前者（定理1）は有名な性質で、 Mersenne 数の文脈では基本的事実の一つ。
次回は話を膨らませて、 p と 4p+1 が両方素数の場合や、 p と 6p+1 が両方素数の場合、一般に p と ℓp+1 が両方素数の場合（ℓ: 正の偶数）について考えみたい。本来の Germain 素数は ℓ = 2 の場合の p だが、それを「もう少し一般化した構造」の中の一つのケースとして捉えると、新しい発見もあるかもしれない。
〔参考文献・画像の出典〕 Sophie Germain (1776 - 1831) - Biography - MacTutor History of Mathematics
https://mathshistory.st-andrews.ac.uk/Biographies/Germain/
〔追記〕 定理2はトリビアルだが、比較的知られていないらしい。 Henri Lifchitz は1998年、
https://web.archive.org/web/20080620004140/http://www.primenumbers.net/Henri/fr/NouvTh1fr.htm
において、これを Nouveau test
と呼んでいる。実は、数世紀前の1730年代に、既に Euler は定理1・定理2に気付いていた（証明はしていない）。
https://scholarlycommons.pacific.edu/euler-works/26/
参照。（2025年2月20日）
2025-02-08 ジェルマン素数とその周辺（その2） 定理3・定理4
1876年、フランスの Édouard Lucas （エドワーゥ・ルュカ）は、途方もない手計算の末、39桁の数 P = 2127 − 1 が素数であることを証明した。これは「人類が知っている一番大きな素数」の新記録となり、75年もの間、誰もこの記録を破ることができなかった。
20世紀後半に入った1951年、別々の二つの勢力によって、ついに世界記録が更新される。フランスの Aimé Ferrier は、 2148 + 1 が 17 で割り切れること、その44桁の商が素数であることを突き止め、7月14日付けで公表。この日付は単なる偶然かもしれないが、「世紀の記録」公表の日付として、意図的に革命記念日（バスチーユの日）を選んだのかもしれない。素数性の検証では、機械式の卓上計算機が使われたという。異論の余地もあるけど、これは一応「手計算」とされる（機械式計算機は、紙と鉛筆・対数表・そろばん・計算尺などと同様、手動の道具だからだろう）。
同じ1951年、英国の J. C. P. Miller (Jeffrey Charles Percy Miller) と D. J. Wheeler (David John Wheeler) のチームは初期の大型電子計算機を使い、 ℓP + 1 の形の素数を探索（ℓ = 2, 4, 6, ···）。この型の数は、もちろん P = 2127 − 1 より大きい（ℓ の値に応じて約2倍、4倍、6倍、··· ）。そのうち、6月7日の時点で見つかっていた最大の素数は ℓ = 934 のケース（42桁）だった。42桁では世界最大にならない。 ℓ = 978 で自己ベストを更新したものの、依然42桁。
ℓP + 1
の形式では、 ℓ を 2 増やすごとに39桁の 2P が足し算されるだけなので、42桁より上に行くには ℓ をかなり大きくする必要がある。 Miller たちは、
ℓ(P2) + 1
の形の素数の探索も開始。こっちなら「旧・世界記録の P が2乗された77桁の数」が出発点なので、この型の素数が見つかれば Ferrier の44桁のはるかに上を行くことができる。
そしてとうとう、79桁の数、
180(P2) + 1
が素数であることを突き止め、英国チームは「既知の一番大きい素数の発見者」のタイトルを75年ぶりにフランスからもぎ取った。
この79桁の数と Ferrier の44桁の数は、どちらも1951年7月付けで素数性が記されている。どっちが先なのか、確実な記録は残っていない。仮に Ferrier の計算の方が先なら、世界記録は Lucas → Ferrier → Miller チームの順に更新されたことになるし、 Ferrier の方が後なら（44桁の計算が済んだとき、既に79桁が達成されていたのなら）、 Ferrier の44桁は一度も世界記録に届かなかったことになる。 Miller たちは「early July」と報告していて、 Ferrier の公式日付は「7月14日」なので、文字通りに解釈するなら Miller たちの方が少し早かったようだが…
Ferrier による机上での計算と、大型コンピューターを使った Miller たちの力技。この二つを直接比較するのは、不適切かもしれない。1951年の微妙なゴール順序と無関係に、 Ferrier の44桁の数は、数学史の片隅に記録されてもいいだろう。「手計算で素数性が証明された史上最大の数」として。
Fermat test は強くない
p を 3 以上の素数とする。 Fermat の小定理から、
2p−1 ≡ 1 (mod p)
が成り立つ。
これは「2p−1 を p で割ると必ず 1 余る」という意味。例えば p = 5 として、 24 = 16 を 5 で割ると 1 余る。あるいは p = 11 として 210 = 1024 を 11 で割ると 1 余る。それでは逆に、 n が素数か素数でないか不明だとして、もし、
2n−1 ≡ 1 (mod n)
が成り立ったなら、何が言えるだろうか？
この問いは、 Fermat の小定理の逆とか Fermat test とか呼ばれる有名問題で、その条件が満たされるなら、 n が素数である可能性が高い。でも、残念ながら「必ず素数」とまでは、言い切れない。素数でないくせに Fermat test に合格してしまうような「偽物の素数」が（比較的まれとはいえ）一定の割合で存在している…。では Fermat test は素数性判定に全く役立たないのか、というと、そうでもない。第一に、 Fermat test に合格しない数については「絶対に素数でない」と断言できる。つまり「素数だ、という確定判断」はできないけど、「素数でない、という確定判定」は可能。第二に、 Fermat test を強化・改善する方法がいろいろあって、強化版を使うことで、「偽物の素数」をほぼ（あるいは完全に）排除できる。
〔注〕 この問題は、もともとは純粋な数論の話題だったのだが、現在では「インターネット上のセキュアな通信」のような目的で、日常的にも（エンドユーザーからは見えないところでだが）この種の理論が活用されている（暗号学的応用）。
Fermat test が確実になる一例
定理3 p を 3 以上の素数とする。 n = 2p + 1 は、もし、
2n−1 ≡ 1 (mod n)
を満たすなら、必ず素数である（従って、その場合 p は Germain 素数）。
n = 2p + 1 の形の場合には――言い換えると、
p = (n−1)/2 が素数
という付帯条件が成立する場合には――、 n についての Fermat test の結果は100%正しい、というわけ。これは面白そうな定理だ！
〔注〕 英国チームが電子計算機を使って世界記録に挑戦したとき、当時の「世界記録」の素数 p = 2127 − 1 を基準に、 n = 2p + 1, 4p + 1, 6p + 1, ··· の素数性が検討された。それは、定理3を拡張した定理4に基づき、「世界記録の p よりもっと大きい素数を見つけよう」という試みであった。
証明 n = 2p + 1 なので、 p は n を割り切らない――より具体的に、 n を p で割ると 1 余る。つまり:
n ≡ 1 (mod p) ‥‥①
今 2x ≡ 1 (mod n) を満たす最小の正の整数 x を e とする。すなわち（数論の用語を使うと）、 mod n での 2 の位数を e とする。位数の基本性質として、
2x ≡ 1 (mod n)
が成り立つなら x は e の倍数で、成り立たないなら x は e の倍数ではない。ところが、定理の仮定によると、
2n−1 ≡ 1 (mod n)
が成り立つ。よって n−1 は e の倍数。あるいは、同じことだが（仮定から n−1 = 2p なので）、 2p は e の倍数。言い換えると、
e は 2p の約数 つまり e は 1, 2, p, 2p のいずれか
だ。
さて p ≥ 3 従って n = 2p + 1 ≥ 7 なので、
22 = 4 ≡ 1 つまり 3 ≡ 0 (mod n)
ということは、あり得ない（上の式は「3 は n の倍数」という意味を持つが、 n は 7 以上なので、それは不合理）。この 22 ≢ 1 という事実から（再び位数の基本性質を使うと）、 2 は e の倍数ではない。要するに e は 1 でも 2 でもないので、
e = p または e = 2p
である。どちらにしても e は p の倍数（1倍または2倍）。
Euler の定理から 2φ(n) ≡ 1 (mop n) なので†、 φ(n) は e の倍数。その e は p の倍数なのだから、結局 φ(n) は p の倍数でなければならない。もし仮に n が素数なら φ(n) = n−1 なので、 Euler の定理は Fermat の小定理と同じ意味になって、
φ(n) は p の倍数 つまり n−1 = 2p は p の倍数
という主張は、当たり前の内容。つじつまが合う。
一方、 n が素数でないとすると矛盾が生じる。すなわち、もしも n が素数でなかったら、
n = A2 とか n = A3 等々
あるいは、
n = AaBb とか n = AaBbCc 等々
のように n は、何らかの形で「2個以上の（必ずしも相異ならない）素数の積」に分解されるはず。ここで A, B などは相異なる素数で、指数 a, b などは 1 以上の整数。
例えば、仮に n = A2B1C1 だとして、 p はその n を割り切らないのだから（①参照）、素数 p は、素数 A, B, C のどれとも異なる（もしも p = A または p = B または p = C だとしたら、 p は n = A2B1C1 を割り切ることになってしまい、定理の前提に反する）。
さて、もしも n が上記のように何らかの形で素因数分解されるなら、 φ 関数の性質から、 φ(n) の値は、
A1(A − 1) とか A2(A − 1) 等々
あるいは、
Aa−1Bb−1(A − 1)(B − 1) とか Aa−1Bb−1Cc−1(A − 1)(B − 1)(C − 1) 等々
になるが、この値が p の倍数であるということ（つまり p がこの積を割り切るということ）と、
素数 p は素数 A, B, C, ··· のどれとも異なる
ということから、 p は残りの因数、
(A − 1) あるいは (A − 1)(B − 1) あるいは (A − 1)(B − 1)(C − 1) 等々
を割り切る。その結果、（p が素数であることを考慮すると） A − 1, B − 1, C − 1, ··· のうち、少なくとも一つは因子 p を持たなければならない。言い換えると、 p は A − 1 または B − 1 または C − 1 などのうち、少なくとも一つを割り切る。従って、 n の素因子 A, B, C, ··· のうち、少なくとも一つ（それを U としよう）について、次の関係が成り立つ:
p は U − 1 を割り切る
∴ U − 1 ≡ 0 (mod p) つまり U ≡ 1 (mod p)
n の素因数 U について、もし n ≠ U とすると（ここでは n は素数でないと仮定してるので、そういうことになる）、 n = UV と書けるはず（U は n より小さい素数、 V は 2 以上の整数）。そのとき、
U ≡ 1 (mod p)
という関係（上記）と、①の n = UV ≡ 1 (mod p) という事実から、 V についても、
V ≡ 1 (mod p)
となる‡。すなわち U, V は、どちらも p の倍数より 1 大きく、
U = up + 1, V = vp + 1
という形を持つので（u, v はどちらも 1 以上の整数）、その仮定上では、
n = UV = (up + 1)(vp + 1) = uvp2 + up + vp + 1
∴ 2p = n − 1 = uvp2 + up + vp
となり、両辺を p で割ると、
2 = uvp + u + v
となってしまう。これは不合理―― p は 3 以上、 u, v はどちらも 1 以上なのだから、上の式の右辺は最小でも 1⋅1⋅3 + 1 + 1 = 5 であり、左辺の 2 と等しくなるわけがない。
結論: 「n は素数でない」と仮定すると矛盾が生じるので、 n = 2p + 1 は素数。∎
一つ一つの主張はどれも単純で基本的だけれど、それらを繊細に組み合わせて結論を導いている。
† p は奇数なので n = 2p + 1 は奇数。従って 2 と n は互いに素。
‡ U は up + 1 の形を持つ。 V を p で割った余りを r として V = vp + r と書くと、
UV = (up + 1)(vp + r) = uvp2 + up + vp + r = p(uvp + u + v) + r
となるが、 n = UV を p で割った余りは 1 なので r = 1 となる。
ところで n = 2p + 1 を法として、結局 2 の位数 e は p なのか 2p なのか？
この n は素数なので、 Fermat の小定理から、
2n−1 = 22p ≡ 1 (mod n)
であることは間違いない。問題は、その平方根が、
2p ≡ ±1 (mod n)
のどちらの符号になるか？ これは Euler の基準の形なので、第二補充法則によれば、（ア）もし n = 8k ± 1 の形なら符号は + になって e = p であり、（イ）もし n = 8k ± 3 の形なら符号は − になって e = 2p である。 n = 2p + 1 であることを考慮すると、 p = 4k − 1 の形なら n = 8k − 1 の形になって（ア）が生じ、 p = 4k + 1 の形なら n = 8k + 3 の形になって（イ）が生じる。
〔例1〕 p = 3 のときの n = 2p + 1 = 7 について、 2n−1 = 64 を n で割ると 1 余るので、定理3から n = 7 は素数（結論自体は当たり前）。このとき 2(n−1)/2 = 2p = 8 を n で割っても 1 余るので、位数は p = 3。これは（ア）の例であり、 y2 ≡ 2 (mod n) は解を持つ。具体的には y = 3 のとき 32 = 9 ≡ 2 (mod 7) だ。ところで 21 = 2 ≡ 1 ないし 22 = 4 ≡ 1 は mod 1 か mod 3 でしか成り立たない。定理3の場合、 mod n の n は最小でも 7 なので、 2 の位数が 1 or 2 という事態は生じ得ない。
〔例2〕 p = 5 のときの n = 2p + 1 = 11 について、 2n−1 = 1024 を n で割ると 1 余るので、定理3から n = 11 は素数（結論自体は当たり前）。このとき 2(n−1)/2 = 2p = 32 は n の倍数 33 より 1 小さいので、位数は（p = 5 ではなく） 2p = 10。これは（イ）の例であり、 y2 ≡ 2 (mod n) は解を持たない。
〔例3〕 p = 11 のときの n = 2p + 1 = 23 について、 2n−1 = 4194304 を n で割ると 1 余るので、定理3から n = 23 は素数（結論自体は当たり前）。このとき 2(n−1)/2 = 2p = 2048 を n で割っても 1 余るので、位数は p = 11。これは（ア）の例であり、 y2 ≡ 2 (mod n) は解を持つ。具体的には y = 5 のとき 52 = 25 ≡ 2 (mod 23) だ。
ちょっとマニアックな話
定理3の系 合成数でありながら 2n−1 ≡ 1 (mod n) を満たすような整数 n を考える（擬素数の一種で PSP(2) と呼ばれるもの）。このとき (n−1)/2 は決して素数ではない。言い換えると、もし p が素数なら 2p + 1 は PSP(2) ではない。
1000 以下の PSP(2) は n = 341, 561, 645 の三つだが、いずれも n−1 は 4 の倍数、従って (n−1)/2 は偶数なので、それらが素数でないことは明白。最初の「面白い」例は n = 680627 = 107 × 6361 だ。この数は合成数だが Fermat test に合格する。対応する (n−1)/2 = 340313 は、一見したところ素数かもしれないように思えるが、定理3によれば、もしも p = 340313 が素数なら、 n = 2p + 1 = 680627 は本物の素数でなければならない。これは事実に反するので p = 340313 は合成数と結論される。果たして、
340313 = 53 × 6421
と素因数分解される。
定理3の一般化
英国チームが世界記録に挑んだとき、最初に使ったアルゴリズムと本質的に同じもの。「75年間、破られなかった世界記録が、こんな初等的なアプローチで破られた」というのは、意外な感じもする。とはいえアルゴリズムは簡単でも、手計算でのブルートフォースは困難だろう。電子計算機の発明の恩恵として、巨大なべき剰余の計算を湯水のように使えるようになった。
定理4 p を 3 以上の素数、 ℓ を 2 以上 4p + 4 未満の偶数とする。もし奇数 n = ℓp + 1 が、
2n−1 ≡ 1 (mod n)
を満たし、しかも、
2ℓ ≢ 1 (mod n)
が成り立つなら、 n は素数である。
定理4においては、 ℓ を偶数に限らずに任意の正の整数としても構わない。しかし ℓ が奇数なら n = ℓp + 1 は 4 以上の偶数なので、大前提となる条件 2n−1 ≡ 1 (mod n) は、決して満たされない。つまり ℓ を「正の整数」としても、定理の他の条件から、自動的に ℓ は「正の偶数」に限られてしまう。（実際上、 4 以上の偶数は素数でないので、素数性を判定するまでもない。）
条件 2n−1 ≡ 1 (mod n) だけでは、「偽物の素数」（PSP(2)）が合格してしまう可能性がある。検査される数を Germain 風の ℓp + 1 の形に限定し、かつ、付帯条件、
2ℓ ≢ 1 (mod n)
と ℓ の範囲制限を課すことによって、定理4では「偽物の素数」が弾かれる。
この付帯条件は、偽物の素数を排除するには十分だが、実はぎりぎりの必要十分条件ではなく、過剰に強い。つまり、本物の素数が排除されてしまうケースがある。例えば p = 31, ℓ = 22 の場合、
n = 22⋅31 + 1 = 683
は本物の素数†。ところが定理4に当てはめると、
2ℓ = 222 = 4194304
を n = 683 で割った余りはたまたま 1 なので、付帯条件により、この n は（本物の素数なのに）不合格になってしまう！
巨大素数の探索において、甘過ぎる検査（偽物の素数が合格する可能性がある）と厳し過ぎる検査（本物の素数が不合格になる可能性がある）では、後者の方が良いだろう。アルゴリズムがシンプルな方が計算量的にも有利なので、定理4は「理想」ではないとしても、一定の実用性を持つ。
† この種の特別な素数は、以下のような数と関連あるようだ。
https://oeis.org/A333245 Primes p such that the order of 2 mod p is less than the square root of p
https://oeis.org/A283461 Second-largest prime factor of 2^n - 1, if composite, or 1 otherwise
https://oeis.org/A354183 Primes p such that p divides 2^((p-1)/x) - 1, where x is the greatest prime factor of p - 1
〔追記〕 定理4とその証明について、最初 Wright [3] あるいは Hardy–Wright の定理101と同様の内容を紹介していたが、不等式の改善が可能なので、改善版に置き換えた。（2025年2月19日）
定理4の証明は、定理3の証明とほぼ同様に進む（実際、定理4で ℓ = 2 とした場合が定理3）。どちらの証明も全く同様の根拠に基づく部分については、以下では説明を簡略にする（定理3の証明参照）。
証明 n = ℓp + 1 なので、 p は n を割り切らない――より具体的に、 n を p で割ると 1 余る。つまり:
n ≡ 1 (mod p) ア
mod n での 2 の位数を e とすると、 n−1 は e の倍数。あるいは、同じことだが、 e は ℓp の約数。
一方、付帯条件によって、 ℓ は e の倍数ではない。要するに、 e は ℓp の約数だが ℓ の約数ではない。例えば ℓ = 6 とすると、
e は 6p の約数だが 6 の約数ではない ⇒ e = p か 2p か 3p か 6p
となり、いずれにしても e は p の倍数。 ℓ が 6 以外の一般の整数の場合も、同様に考えると e は p の倍数でなければならない†。つまり p は e を割り切る。
今、矛盾を導くため、 n が合成数だと仮定する。例えば、
n = AaBbCc イ
と素因数分解されるとしよう。 p は e を割り切り、その e は φ(n) を割り切るので、p は、
φ(n) = Aa−1Bb−1Cc−1(A − 1)(B − 1)(C − 1)
を割り切る。しかし、素数 p は n を割り切らず（ア参照）、従って素数 A, B, C のどれとも異なるので（もしもそのどれかだったら、イによって p は n の約数になってしまい、仮定に反する）、 p は Aa−1Bb−1Cc−1 を割り切らない。従って、残りの因子 A − 1, B − 1, C − 1 のうちの少なくとも一つが p で割り切れる。 p が割り切る因子（もし複数あるなら、任意に選んだその一つ）を仮に U − 1 と呼ぶと‡、 U は n の素因数 A, B, C のどれかで、 n = UV と書くことができる（V は 2 以上の整数）。
U − 1 ≡ 0 つまり U ≡ 1 (mod p)
が成り立つが、アから n = UV ≡ 1 (mod p) なので、 V ≡ 1 (mod p) でもある。従って、
U = up + 1, V = vp + 1
と書くことができる（U は素数なので u は 1 以上。 V は 2 以上なので v も 1 以上）。つまり:
n = UV = (up + 1)(vp + 1) = uvp2 + up + vp + 1
∴ ℓp = n − 1 = uvp2 + up + vp
両辺を p で割ると:
ℓ = uvp + u + v
ところが、仮定により n = (up + 1)(vp + 1) は奇数なので、 up + 1 と vp + 1 はどちらも奇数。従って up と vp はどちらも偶数。 p は奇数なので、 u, v はどちらも偶数、よってどちらも 2 以上。このことから、
ℓ = uvp + u + v ≥ 2⋅2p + 2 + 2 = 4p + 4
となるが、これは定理の仮定に反し不合理。すなわち「n は合成数」と仮定すると矛盾が生じるので、 n = ℓp + 1 は素数。∎
† 「「30 の約数だが 10 の約数ではない数」は？」参照。 ℓ が s 個の（必ずしも相異ならない）素因数から成るとして、それを
ℓ = q1q2···qs
と表現すると、整数 ℓp は、
ℓp = q1q2···qsp
と素因数分解される。 e はこの ℓp の約数なのだから、
q1, q2, ···, qs のうちの 0 個以上の積、または、その p 倍
に等しい（「0 個の積」は 1 とする）。しかし e は ℓ の約数ではないのだから、 e = 1 ということはあり得ず、 e が q1, q2, ···, qs のうちの一つ（または二つ以上の積）に等しいということも、あり得ない（もしもあり得たら、 e は ℓ の約数になってしまう）。つまり、 e は、
q1, q2, ···, qs
のうちの 0 個以上の積としては表現不可能で、それ以外の何らかの素因数を含む。 e は、
ℓp = q1q2···qsp
を割り切るのだから、 e は、
q1, q2, ···, qs または p
のうちの 1 個以上の積としてなら表現可能。よって「それ以外の何らかの素因数」とは p であり、 e は必ず素因数 p を含む。従って、最小でも e = p、 一般には、
e = (ℓ の約数) × p = (q1, q2, ···, qs のうちの 0 個以上の積) × p
となる。 q1, q2, ··· の中に p に等しい素数が含まれる可能性はあるが、その場合でも e が p の倍数であることに変わりはない: e は ℓ を割り切らないのだから、もし ℓ が因子 p を一つ含むなら e は因子 p を二つ含み、 e は p2 の倍数（n = 1387 の具体例参照）。
‡ n の素因数分解がどんな形であろうと、 φ(n) は U − 1 に相当する因子を持つ。 n = Aa なら φ(n) = Aa−1(A − 1) だし、 n = AaBb··· なら、
φ(n) = Aa−1Bb−1···(A − 1)(B − 1)···
なので、因子 A − 1, B − 1, ··· のうち（この形の因子の個数は、 n が持つ相異なる素因数の個数に等しい）、どれか一つが U − 1 となる。例えば n = AaBb のとき、もし U = B なら V = AaBb−1 となり（なぜなら n = UV）、あるいは例えば n = AaBbCc のとき、もし U = A なら V = Aa−1BbCc となる。
Hardy–Wright, §6.14, Theorem 101 では n = ℓp + 1 の場合と n = ℓp2 + 1 の場合が、まとめて証明されている。ここでは n = ℓp + 1 の場合だけを取り出して定理4とし、便宜上、そのうち ℓ = 2 のケースを定理3とした。 Hardy–Wright が手元になくても、より詳しい内容を [3] で自由に閲覧できる（このメモの ℓ は、 Hardy–Wright の h、 [3] の k に当たる）。ただし Hardy–Wright も [3] も、必ずしも見通しが良いとはいえない。
References:
[1] Which came first: 180(2127-1)2 + 1 or (2148+1)/17?
https://t5k.org/notes/FirstIn1951.html
[2] The Largest Known prime by Year: A Brief History
https://t5k.org/notes/by_year.html
[3] Wright, “The Calculation of Large Primes”
https://archive.org/details/sim_mathematical-gazette_1953-05_37_320/page/104/mode/1up
Cf. Hardy–Wright, §6.14, Theorem 101. Some editions of H–W may have a typo in the notes to §6.14: for 190p2 + 1
, read 180p2 + 1.
2025-02-09 賞金15万ドルをもらう便乗チート？ 余談
2025年2月現在、既知の最大素数は約4100万桁の Mersenne 数（それを M とする）。最初の1億桁素数には、賞金15万ドル（2250万円）が懸かっている。
Mersenne 数で1億桁までいくのは、可能だとしても、まだまだ時間がかかるだろう。ところで M3 はざっと1億2000万桁なので、もしも ℓM3 + 1 型の素数が見つかったら Mersenne 素数の探索より先に1億桁を突破でき、賞金をもらえるかも…
その方法だが、立方数以外の偶数 ℓ = 2, 4, 6, 10, 12, ··· を小さい順に試して、 n = ℓM3 + 1 について 2n−1 (mod n) を計算する（べき剰余なので、直接 2n−1 を計算する必要はない）。どこかで ≡ 1 になれば、その n は素数である可能性が高い。素数であることを確定させるには 2ℓ (mod n) を計算して ≡ 1 でないことを示せばいい（定理6参照）。
理論は簡単だが、実装上これがうまくいくかどうかは、第一に mod n での簡約をどこまで速くできるかに懸かっている。真面目に割り算したら、遅過ぎるだろう。 n は ℓ(2p − 1)3 + 1 の形なので、2進数で特徴的なビットパターンを持つ。ビット演算をうまく利用して、割り算を高速化できれば…。第二に、掛け算（累乗）についても、極力高速化するべきだろう。この部分は、アルゴリズムも実装もオープンソースで公開されているので、それを流用すればいいだろう。
1億桁を扱える計算資源がある方は、検討してみてもいいでしょう。
この方法で成功した場合、「世界中のボランティアが協力して、何年もかけて見つけた M」を踏み台にすることについて「ずるい」という批判が出るかもしれない。でも「既知の巨大素数を踏み台にしてはいけない」というルールはないので、賞金はもらえると思われる。実際、1951年に Miller & Wheeler が世界記録を更新（79桁）したときには、当時知られていた最大（39桁）の素数 P = 2127 − 1 を踏み台にして ℓP2 + 1 にブルートフォースをかけ、 ℓ = 180 で成功している（定理5参照）。
〔注〕 万一この方法で本当に成功して大ニュースになった場合、「チート」のアイデアをここで読んだことは、秘密にしといてくださいね。変な騒ぎに巻き込まれたくないので…（笑）
2025-02-09 ジェルマン素数とその周辺（その3） 定理5
1950年まで、既知の最大の素数は39桁の P = 2127 − 1 だった。1951年に「世界記録の素数」は 180P2 + 1 となった。79桁。 P2 を利用したのだから不思議ではないが、一気に旧・記録の2倍を超す桁数だ。
この 180P2 + 1 の素数判定に使われたアルゴリズムを紹介・証明する。
定理5 p を 3 以上の素数、 ℓ を 4p − 2 未満の正の偶数とする。もし奇数 n = ℓp2 + 1 が、
2n−1 ≡ 1 (mod n)
を満たし、しかも、
2ℓ ≢ 1 (mod n)
が成り立つなら、 n は素数である。
定理4とよく似た同じ内容だが、定理4の n = ℓp + 1 が定理5では n = ℓp2 + 1 に置き換わり、 ℓ の範囲がわずかに異なる。
1951年の記録更新では、 p として既知の素数 2127 − 1 が使われ、電子計算機によって条件を満たす ℓ が探索された。見つかった ℓ = 180 は、条件を満たす最小の ℓ だ。最初は定理4に基づき ℓp + 1 型素数が探索され、それも成功したのだが、さらに上を行くべく ℓp2 + 1 型素数の探索が行われたらしい。純粋な数論というより、半分は「記録競争」のようなもの。まぁ、それもまた一興。古来、数論には、パズルや遊びの要素が絡んでいる。
〔追記〕 定理5とその証明について、最初 Wright [3] あるいは Hardy–Wright の定理101と同様の内容を紹介していたが、不等式の改善と証明の簡単化が可能なので、改善版に置き換えた。（2025年2月19日）
証明 定理5の条件下において、もしも n が合成数だったら n = UV = (up + 1)(vp + 1) と書ける――というところまでは、定理4の証明と全く同様（u, v はどちらも 2 以上の偶数）。すなわち n − 1 = ℓp2 は e の倍数だが、 ℓ は e の倍数ではないので、 e は素因子 p を持つ。従って、
φ(n) = Aa−1Bb−1··· (A − 1)(B − 1)···
は（e の倍数なので）素数 p で割り切れるが、 n = AaBb··· は素因子 p を含まないので、 A − 1, B − 1, ··· の少なくとも一つが p で割り切れる。その一つを U − 1 として n = UV とすると、 U, V はどちらも「kp+1型」。
ところが、もしも奇数 n が、
n = UV = (up + 1)(vp + 1) u, v は正の整数
という形を持つとしたら、 ℓ ≥ 4p − 2 であることが必要（理由）。これは定理5の仮定と矛盾する。すなわち、定理5の条件下では「n が合成数であること」は不可能。∎
2025-02-11 ジェルマン素数とその周辺（その4） 定理4とPSP
p を 3 以上の素数、 ℓ を 2 以上 p 未満の偶数とする。 n = ℓp + 1 が Fermat test に合格し、かつ付帯条件 2ℓ ≢ 1 (mod n) を満たすなら、 n は素数（定理4）。
この付帯条件が「偽物の素数」を弾いてくれること、従って（定理4の条件下に限れば）、 Fermat test の弱さをそれなりに補ってくれることを、具体的な数値例で観察する。
合成数なのに Fermat test に合格してしまうような数 n は、 Fermat 擬素数（ぎそすう）、あるいは単に擬素数（pseudoprime: 略語 PSP）と呼ばれる†。要するに「偽物の素数」。条件 2n−1 ≡ 1 (mod n) は Fermat test の一種で、「2n−1 を n で割ると 1 余るか？」という検査だ。 n を奇数に限るなら、「2n − 2 が n で割り切れるか？」と言い換えることもできる。例えば、 24 = 16 を 5 で割ると 1 余るので、素数 n = 5 はこの条件を満たす。あるいは、同じことだが、 25 − 2 = 32 − 2 = 30 は 5 で割り切れるので 5 は条件を満たす。
素数は、必ず上記のテストに合格する。ところが、合成数なのにこのテストに合格するような数もある。そのような偽物の素数を PSP(2) で表すことにする。1万以下の素数は 9592 個。10万以下の PSP(2) は 78 個。割合でいえば、本物の素数と比べ、かなり少ない。
100万・1000万・1億以下の PSP(2) は、それぞれ245個・750個・2057個。1兆・1京···までの範囲には‡ 10万1629個・474万4920個···。割合でいえば微々たるものだが、個数は多い。このような「擬素数」の存在のため、 Fermat test には、「偽物の素数」が「恐らく素数」と判定されてしまう可能性が、つきまとう。整数（特に巨大整数）の確定的な素数判定において、無視できない問題だ。
† Poulet の数（nombre de Poulet）とも呼ばれる。 Paul Poulet （ポル・プゥレ） はベルギーの研究者。20世紀前半、1億以下の PSP(2) の一覧表（誤りも含まれるが、大部分正しい）を手計算で作った。 341 が PSP(2) であること（従って Fermat の定理の逆、いわゆる「中国予想」が、成り立たないこと）は、1819年、フランスの Frédéric Sarrus （フレデリク・サルュ） により発見された（行列式の「Sarrus の規則」の人）。ちなみに、フランス語では語末の子音字は発音されないことが多いが、 [k] と [l] は発音される（前者は文字 c, k, q に対応）。「中国予想」は、実際には19世紀後半の清の数学者・李善蘭（Lǐ Shànlán）の一時的な誤記に過ぎず、李自身が誤りを認識して、後の著書には Fermat の定理の逆を含めていない。しばしば「19世紀初めの Sarrus によって中国予想が否定された」という趣旨の記述が見られるが、時間的順序に矛盾があり、史実に反する。
‡ https://oeis.org/A055550
定理4は、 Germain 素数 p に対応する素数 2p+1 や、それを一般化したような 4p+1, 6p+1, ··· の形の素数の検出に限っては、「擬素数を弾いてくれる」というメリットを持つ（副作用として、たまに本物の素数まで弾いてしまうが）。 n が PSP(2) でない場合、 Fermat test だけでも「恐らく素数」という結論が出るけど、定理4を適用することで、「恐らく素数」から「確定的に素数」になる。これはありがたい。
n が PSP(2) の場合、定理4の働きは面白い。 Fermat test は「恐らく素数」という結論を出すが、定理4は「いや、素数ではないだろう！」と駄目出しをしてくれるのだ。しかし、その場合でも、理論上（定理4だけでは）「その n は確定的に合成数」とまではいえない。
〔例1〕 n = 60701 = 101 × 601 は素数ではないが、 2n−1 を n で割った余りは 1 なので――記号で書けば 260700 ≡ 1 (mod 60701) なので――、 Fermat test は「恐らく素数」という判定を下す。ところが、素数 p = 607 を使って n = 60701 = 100p + 1 と書けるので（そして 100 は p より小さいので）、定理4による判定を適用できる。定理4の付帯条件によれば、
2100 ≢ 1 (mod 60701)
が成り立てば n は素数だが（十分条件）、成り立たなければ n は素数とは限らない。この場合、
2100 ≡ 1 (mod 60701)
なので付帯条件は成り立たず、 n = 60701 は「素数ではないだろう」と（正しく）判定される。
〔例2〕 同様に n = 13741 = 7 × 13 × 151 は素数ではないが、 Fermat test では「恐らく素数」と判定される。 n = 13741 = 60 × 229 + 1 と見て（p = 229 は素数）、定理4を使うと、
260 ≡ 1 (mod 13741)
なので、 Fermat test の判定は覆され、 13741 は「素数ではないだろう」と判定される。
〔例3〕 n = 11305 は明らかに素数でないが、 Fermat test では「恐らく素数」と判定される。 n = 11305 = 72 × 157 + 1 と見て（p = 157 は素数）、定理4を使うと、
272 ≡ 1 (mod 11305)
なので、 Fermat test の判定は覆され、 11305 は「素数ではないだろう」と判定される。
こうした例では、定理4は、それなりに有用だと感じられる。半面、10万以下の PSP(2) は 78 個あるのに、定理4を利用して「駄目出し」ができるケースは、そのうち 26 個しかない。というのも、与えられた n を ℓp + 1 の形で書くこと自体、一般には簡単なことではなく、常に可能とも限らない（特に定理4の条件がある場合には）。例えば、最小の PSP(2) は n = 341 = 11 × 31 だが†、素数 p = 5 を使って、これを n = 341 = 68p + 1 と書くことは可能。でも ℓ = 68 は 4p + 4 = 24 より小さくないので、この ℓ に定理4を適用することはできない。実際、もしも前提 ℓ < 4p + 4 を無視して無理やり定理4を適用したとすると、
268 ≡ 256 ≢ 1 (mod 341)
となり、付帯条件が満たされて、 341 は素数と判定されてしまう。
そもそも例3の 11305 のような場合、こんなことをするまでもなく、素数でないこと（5 で割り切れること）は一目瞭然だし、例2についても、実用上は、試行除算で約数 7 を見つける方が手っ取り早いだろう。
定理4は、使い方によっては役立つが（実際、世界記録更新に利用されたこともある）、実用上の汎用性はあまり高くなく、素数性判定に活用できる場面は、かなり限られている。しかしこの定理は、それ自体として大変興味深い。
付記 通常、擬素数 PSP(2) は、 2n−1 ≡ 1 (mod n) を満たす合成数 n と定義される。その場合、自動的に n は奇数に限られる。というのも、偶数 n = 2, 4, 6, ··· を法として 2n−1 ≡ 1 が成り立つことはない。実際、その場合、左辺 2n−1 は偶数。それを偶数 n で割った余りは偶数で、右辺の奇数 1 と合同になることは不可能。代わりに条件の合同式の両辺を 2 倍して「2n ≡ 2 を満たす合成数 n」と定義した場合、条件を満たす偶数 n も存在する（n は奇数、という限定を付けなければ）。つまり、その（弱い）定義を使うなら、「偶数の擬素数」も存在する（oeis.org/A006935 参照）。最小の例 161038 = 2 × 73 × 1103 は、 D. H. Lehmer によって1949年に発見された。一説に pseudoprime という用語を使い始めたのも Lehmer だという‡。
† 210 − 1 = 1023 = 341 × 3 は 341 で割り切れる。今 k を 2 以上の整数として、簡潔化のため 10k を y と書くと、
210k − 1 = (210)k − 1 = yk − 1 = (y − 1)(yk−1 + yk−2 + ··· + 1)
= (210 − 1)(yk−1 + ··· + 1) = (341 × 3) × (yk−1 + ··· + 1)
も、 341 で割り切れる。特に k = 34 とすると、 2340 − 1 ≡ 0 (mod 341) つまり 2340 ≡ 1 (mod 341)。
‡ https://oeis.org/A001567 での Amiram Eldar のコメント。 https://users.renyi.hu/~p_erdos/1949-07.pdf も参照。
2025-02-13 ジェルマン素数とその周辺（その5） 定理4の分析
具体的な数値例を使って、定理4の仕組みを少し違う角度から検討。定理4の二つの合同式が成り立つとき、 n = ℓp + 1 は、必ず「kp+1型」の素因数 U を持つ。もし n が素数なら、 U とは n 自身であり、 V = n/U = 1 となる。もし n が合成数なら、 V = n/U は 1 より大きい。
V も「kp+1型」の整数（素数とは限らない）。そこから「n が合成数であるためには ℓ がある程度大きいことが必要」という結論を導くことができる。従って、もし上記の二つの合同式が成り立ち、しかも ℓ が十分小さいときには、「n が合成数であることは論理的に不可能」で、n は素数と断定される。
p を 3 以上の素数、 ℓ を 2 以上の偶数とする。奇数 n = ℓp + 1 が素数かどうか知りたい。定理4は、二つの条件と一つの不等式に整理される。
第一の条件 n が「2 を底とする Fermat test」に合格すること。つまり、
2n−1 = 2ℓp ≡ 1 (mod n)
が成り立つこと。
第二の条件 ℓ が「mod n での 2 の位数」の倍数ではないこと。つまり、
2ℓ ≢ 1 (mod n)
が成り立つこと。
不等式 ℓ は十分に小さい。 ℓ < p なら十分。範囲をさらに広げて ℓ < 2p や ℓ < 4p でもいい。ぎりぎりの限界は ℓ < 4p + 4 だ。
Fermat の小定理の逆に基づく素数性テストでは、第一の条件は当然だろう。第一の条件が満たされないなら（つまり Fermat test に合格しないなら）、それ以上の検査をするまでもなく、直ちにその n は素数ではないと断定できる。一方、第二の条件の意味・役割は、直ちに明らかではない。
n が素数なら、その唯一の素因数は n = ℓp + 1 自身なので、 n が「kp+1型」の素因数を持つことは自明。 n が合成数の場合でも、上記の二つの条件が満たされるなら、 n は必ず「kp+1型」の素因数 U を持つ。具体的な数値例を使って、その理由を検証してみたい。
n = 341 は「偽物の素数」――最小の PSP(2)―― であり、素数でないのに第一の条件 2340 ≡ 1 (mod 341) を満たす。しかも、素数 p = 5 を使って n = 68p + 1 と表現可能で、この ℓ = 68 は、第二の条件を満たす。 mod 2 での n の位数 e = 10 の倍数ではないから。
〔補足〕 210 = 1024 を n = 341 で割ると 1 余るが（341 × 3 = 1023）、 25 = 32 や 22 = 4 を 341 で割った余りは 1 ではない。すなわち mod 341 での 2 の位数 e は 10。 ℓ = 68 は、 e = 10 の倍数ではないので、位数の基本性質から 268 ≢ 1 (mod 341) であり、第二の条件が満たされる。
341 は合成数で、 11 × 31 と素因数分解される。ここで素因子 11 と 31 は、どちらも「kp+1型」だ（ここでは p = 5 なので、これは「5k+1型」を意味する）。この例では不等式 ℓ < p が不成立なので、定理4を使って「n は素数」という結論を出せないけれど（実際、素数ではない）、それでも n の素因子は「kp+1型」になっている。なぜだろうか？
まず、上記二つの条件下では、 mod n での 2 の位数 e は、 p の倍数となる（n = 341 の例では e = 10, p = 5）。
〔理由〕 既に確かめたように、 mod 341 での 2 の位数 e は 10。第一の条件から 2340 ≡ 1 (mod 341) なので、位数の基本性質によって、 340 = n − 1 = ℓp は e の倍数。第二の条件から ℓ = 68 は e の倍数ではない。―― ℓp = 68 × 5 (= 340) は e の倍数なので、因子として、 e = 10 = 2 × 5 の素因数を全て含んでいるが、 ℓp の因子 ℓ = 68 は e の倍数ではないので、 ℓ が因子として e の素因数の全てを含むことは、あり得ない。ゆえに e の素因数の一部（または全部）は、 ℓp のうち（ℓ の部分にではなく） p の部分に含まれる。「含まれる」といっても p は素数なのだから、 p の唯一の素因数は p 自身。つまり e の素因数の一つは p であり、言い換えれば e は p の倍数。
一方、 Euler の定理から 2300 ≡ 1 (mod 341) が成り立つ。ここで指数の 300 は、 φ(n) = φ(341) = φ(11 × 31) = 10 × 30。位数の性質から、この φ(n) は e の倍数だが、その e は上で見たように p の倍数なので、 φ(n) は p の倍数。言い換えれば、 p は φ(n) を割り切る。
他方において、仮定から n = ℓp + 1 なので、 n は p の倍数ではない（p で割れば 1 余る）。言い換えれば、 p は n を割り切らない。
一般に A, B を素数として、もし仮に n = AaBb と分解されるなら、 φ 関数の基本性質から、
φ(n) = φ(AaBb) = Aa−1Bb−1(A − 1)(B − 1)
となる。素数 p は、この値を割り切るのだから、右辺の因子、
Aa−1, Bb−1, A − 1, B − 1
の少なくともどれか一つは p の倍数でなければならない。
しかし p は n = AaBb を割り切らないのだから、素数 p は A とも B とも異なる。よって、
Aa−1 と Bb−1
は p の倍数ではない。この事実は、 a = 1 や b = 1 の場合にも真。実際、 A1−1 = A0 = 1 が素数 p の倍数でないことは明白。 B1−1 についても同様。
従って、 A − 1 と B − 1 の少なくとも一方が p の倍数だ――言い換えると、 A − 1 と B − 1 の少なくとも一方（それを U − 1 としよう）は、素因子 p を含む。
〔数値例〕 n = 341 = 11 × 31 の場合、 A = 11, B = 31 とすると（A = 31, B = 11 としてもいいが、結論は同じ）、
n = A1B1
∴ φ(n) = A0B0(A − 1)(B − 1) = 10 × 30
となる（この場合、 n は因子として素数の2乗・3乗などを含まないので、 A0B0 の部分は最初から無視することができるが、一応、一般公式に当てはめた形で、その部分も記した）。 A − 1 = 10 と B − 1 = 30 は、どちらも素因子 p = 5 を持つので、どちらを U − 1 としても構わない。
U − 1 が素因子 p を持つということは、
U − 1 ≡ 0 (mod p) つまり U ≡ 1 (mod p) カ
を含意する。すなわち U は p の倍数より 1 大きい。ここで U は、 n の素因数 A, B のどちらかなので、n は
「p の倍数より 1 大きい」素因数 つまり 「kp+1型」の素因数
を持つ、と結論される！
のみならず、 U が n の素因子なら U/n は当然、整数（それを V としよう）。 n = UV について、素因子 U ばかりか、余因子 V も、同じ「kp+1」の形を持つ（k の値は一般には異なる）。というのも、仮定により n = ℓp + 1 なので、 n を p で割れば 1 余る。すなわち:
n ≡ 1 (mod p) つまり UV ≡ 1 (mod p) キ
二つの合同式カ・キが両立するためには、 V ≡ 1 (mod p) でなければならない。 341 = 11 × 31 の例で、二つの素因子が両方 5k + 1 型なのはそのため（一般に n が二つの素数 A, B の積に等しい場合、第一・第二の条件が満たされるなら、 A, B はどちらも「kp+1型」素数）。
以下では、第一・第二の条件が満たされていることを大前提とする。 n が三つ以上の素数の積から成る場合にも、そのうち少なくとも一つの素数（それを U とする）は必ず「kp+1型」だが（上記の議論と同様）、残りの素因子の一つ一つは「kp+1型」とは限らない。その場合でも、合同式カ・キは成り立つから、余因子 V = n/U は「kp+1型」となる（この場合の V は、「n の三つ以上の素因子のうち U を除いたもの」の積、つまり二つ以上の素数の積だから、素数ではない）。
数値例として、 n = 645 を考える。この n は、三つの素数の積 3 × 5 × 43 に等しい。 p = 7 として 645 = 92p + 1 と表現すると（ℓ = 92）、第一・第二の条件が満たされる。第一の条件 2644 ≡ 1 (mod 645) を確かめることは、手計算では少々面倒だが、コンピューターを使えば一瞬。第二の条件の成立は、直接計算でも検証できるし、 mod 645 での 2 の位数 e が 28 であること、そして ℓ = 92 が e の倍数でないことからも明らか。
〔補足〕 228 = 268435456 = 645 × 416179 + 1 なので 228 ≡ 1 (mod 645) であり、 e は 28 の約数。しかし 214 = 16384 = 645 × 25 + 259 や 27 = 128 や 24 = 16 などを 645 で割った余りは 1 ではないので、 e = 28。 ℓ = 92 = 3 × 28 + 8 は e の倍数ではない。
n の三つの素因子のうち、 43 は「kp+1型」（つまり 7 の倍数より 1 大きい）。残りの二つの素因子 3, 5 は、どちらもこの型ではない。しかし、 U = 43 の余因子 645/U = 3 × 5 = 15 は、 U と同じく、 7 の倍数より 1 大きい（素数ではないが）。
n の素因子の中には、「kp+1型」のものが少なくとも一つある。というのも、第一の条件から n − 1 = ℓp は e = 28 の倍数。第二の条件から ℓ は e の倍数ではない。よって e は、素因子として、 ℓ の素因子のうちの 0 個以上の他に、必ず p を含む。すなわち、 e は p の倍数。
次に Euler の定理から、
φ(645) = φ(3 × 5 × 43) = (3 − 1)(5 − 1)(43 − 1) = 336
という数は e = 28 の倍数だが（336 = 28 × 12）、 e の倍数は素数 p = 7 の倍数でもあるので、 3 − 1 と 5 − 1 と 43 − 1 の三つの因子の中には 7 の倍数が少なくとも一つ、存在しなければならない。実際、 3 − 1 = 2 と 5 − 1 = 4 は 7 の倍数ではないが、 43 − 1 = 42 は 7 の倍数。よって、
43 − 1 ≡ 0 (mod 7) つまり 43 ≡ 1 (mod 7)
となり、素数 43 は「7k+1型」。 n = 645 を n = ABC と（相異なる）三つの素数に分解したとき、
φ(n) = (A − 1)(B − 1)(C − 1)
の右辺の三つの因子の中に、 p の倍数が存在する。
のみならず、 n = 92p + 1 自身も「7k+1型」なので（なぜなら p = 7）、 n から「7k+1型」の素因数 U = 43 を取り除いた余因子 V = 645/43 = 15 も、「7k+1型」になる。
n の素因数が幾つあるとしても、同様にその一つ U は「kp+1」の形を持ち、余因子 V = n/U も同じ形を持つ。従って、
n = UV, U = up + 1, V = vp + 1
と書くことができる。もし n が素数なら（言い換えると n の素因数が一つだけなら）、 n = U, V = 1 = 0p + 1 となり、そのとき v = 0 だが、もし n が合成数なら u, v はどちらも 1 以上。 n が合成数であることは可能だが、その場合、 ℓ の範囲に一定の制限が付く。というのも、
n が合成数 ⇒ u, v は 1 以上
⇒ n = UV = (up + 1)(vp + 1) = uvp2 + up + vp + 1 ≥ p2 + 2p + 1
⇒ ℓp = n − 1 ≥ p2 + 2p
となり、この最後の不等式の両辺を p で割ると、
ℓ ≥ p + 2
となる。
n が合成数であるためには、 ℓ が p + 2 以上であることが必要
なのだ！
従って、もし ℓ が p + 1 以下なら（そして第一・第二の条件が満たされているなら）、そのときには「n が合成数であることは不可能」であり、すなわち「n は素数でなければならない」。定理4による素数判定が確実なのは、「第一・第二の条件に加えてこの不等式が成り立つなら、 n が合成数であることは、論理的に不可能だから」だ。
〔注〕 実際には、さらに強く ℓ ≥ 4p + 4 が必要。なぜなら u, v は偶数で 2 以上。
別の数値例。 p = 13, ℓ = 91896, n = 1194649 = ℓp + 1。 この n は、素数 1093 の平方に等しい。 mod n での 2 の位数 e = 364。 e は n − 1 = ℓp を割り切るが、 ℓ を割り切らない。よって p は e を割り切る（e = 364 = 28p）。一方、
φ(n) = φ(10932) = 1093(1093 − 1) = 1193556
は e の倍数なので、 p の倍数でもある。 p は n = 10932 を割り切らないので、 1093 − 1 を割り切る（1092 = 84p）。そのことから、
U = 1093 = 84p + 1 ≡ 1 (mod p)
V = n/U = 1093 ≡ 1 (mod p)
となって、 n = UV = (84p + 1)(84p + 1) = (84p + 1)2 となる。第一・第二の条件は満たされるものの、 p と比べて ℓ が非常に大きいので、「n は素数」という判定はできない（実際、素数ではない）。
U, V がどちらも「kp+1型」になる点に変わりはないが、この例では n が平方因子を持つ。 n が素数の平方である結果として、 n = UV の U と V が一致。一般に n = Aa のとき、 φ(Aa) = Aa−1(A − 1) となる（A は素数、 a は正の整数）。
さらに別の数値例。 p = 13, ℓ = 301143444, n = 3914864773 = ℓp + 1。 この n は 29 × 113 × 10932 と素因数分解される。 mod n での 2 の位数は、再び e = 364。 e は n − 1 = ℓp を割り切るが、 ℓ を割り切らない。よって p は e を割り切る（e = 364 = 28p）。一方、
φ(n) = φ(29 × 113 × 10932) = 1093(29 − 1)(113 − 1)(1093 − 1)
は e の倍数なので、 p の倍数でもある。 p は n = 10932 を割り切らないので、 29 − 1 または 113 − 1 または 1093 − 1 の少なくとも一つを割り切る（1092 = 84p）。そのことから、
U = 1093 = 84p + 1 ≡ 1 (mod p)
V = n/U = 29 × 113 × 1093 = 275520p + 1 ≡ 1 (mod p)
となって、 n = UV = (84p + 1)(275520p + 1) となる。
〔参考文献〕 Pseudoprimes to base 2 that are not squarefree, including the even pseudoprimes
https://oeis.org/A158358
2025-02-15 Hardy–Wright の「定理101」を改善
Wright は、次のような趣旨の補題を記した。「p を 3 以上の素数とする。奇数 ℓp + 1 あるいは奇数 ℓp2 + 1 が
(up + 1)(vp + 1) u, v は正の整数
の形の積に分解されるためには、 ℓ が p 以上であることが必要。」
この性質は、 Hardy & Wright の定理101でも使われている。確かに ℓ ≥ p は必要だが、タイトな評価ではない。「2数の積が奇数なら、2数はどちらも奇数」という単純な観察から、約4倍の強さのタイトな評価を得ることができる。
奇数 n = ℓp + 1 が、
n = (up + 1)(vp + 1) u, v は正の整数
と分解されるとき、 up + 1 と vp + 1 はどちらも奇数、よって up と vp はどちらも偶数。従って（p は奇数なので）、 u, v はどちらも 2 以上の偶数（同様の理由から ℓ も 2 以上の偶数）。
ℓp = n − 1 = uvp2 + up + vp の両辺を p で割ると:
ℓ = uvp + u + v ≥ 2⋅2⋅p + 2 + 2 = 4p + 4
つまり ℓ についての条件 ℓ ≥ p は確かに必要だが、より強く ℓ ≥ 4p + 4 であることを要する。一般の場合に、この不等式をさらに強くすることはできない。
〔例〕 p = 11 として、奇数 n = 529 = 48p + 1 を考える（ℓ = 48）。
n = (2p + 1)(2p + 1) = 232
と分解される。このような分解が可能な必要条件は ℓ ≥ 4p + 4 = 48 なので、 ℓ = 48 は「ぎりぎりセーフ」。
今、 n の因子の少なくとも一方は素数であると仮定する。上の例のような u = v = 2 という状況は、 p が Germain 素数で n が (2p + 1)2 の場合に限って生じる。
この補題は、 n が PSP(2) の場合に――つまり n が 2n−1 ≡ 1 (mod n) を満たす合成数の場合に――、理論上重要な意味を持つ。 PSP(2) が素数 q の平方に等しいケースは二つしか知られていない（q = 1093 と q = 3511）。どちらの q も 2p + 1 の形を持たない。すなわち n が PSP(2) の場合に u = v = 2 の「ぎりぎり」が生じるのは、可能だとしても極めてまれ。もしかすると、不可能と証明されているのかも。そこで、
n は PSP(2) であり (2p + 1)2 の形ではない
と仮定した場合、特定の p に対して生じ得る最小の n は、
n = (2p + 1)(4p + 1)
であり（u, v の一方が 2 で他方が 4）、そのとき:
ℓ = uvp + u + v ≥ 8p + 6
このバージョンの不等式で、実際に等号が成り立つケースが存在する。 p = 23, ℓ = 190 の、
n = 190p + 1 = 4371 = 3 × 31 × 47 = 47 × 93 = (2p + 1)(4p + 1)
がその例で、 4371 は PSP(2)。 mod n での 2 の位数 e = 230 は ℓ より大きく、 4e = 5(ℓ − 6) を満たす。
〔追記〕 等号が成り立つような分解が可能な n は、 1013 = 10兆未満の PSP(2) の中に二つある。一つは上記の 4371 で、もう一つは、 p = 45053, ℓ = 360430 の、
n = 360430p + 1 = 16238452791 = 3 × 11 × 43 × 127 × 90107 = (2p + 1)(4p + 1)
だ。 mod n での 2 の位数 e = 3153710 は ℓ の約 8.75 倍で、 4e = 35(ℓ − 6) を満たす。（2025年2月17日）
〔追記2〕 等号が成り立つ三つ目のケースは、 p = 12659963, ℓ = 101279710 の、
n = ℓp + 1 = 1282197381250731 = 3 × 11 × 43 × 127 × 281 × 25319927 = (2p + 1)(4p + 1)
だ（128兆 = 1.28 × 1015 台）。 mod n での 2 の位数 e = 886197410 は ℓ の約 8.75 倍で、再び 4e = 35(ℓ − 6) を満たす。。このような n は、 1018 = 100京未満（p ≤ 353553391）には、上記の三つだけ。（2025年2月19日）
〔追記3〕 6.99垓 = 6.99 × 1020 台に四つ目の例が見つかった。
n = 699511006871330877471 = ℓp + 1 = (2p + 1)(4p + 1)
p = 9350875673, ℓ = 74807005390
mod n での 2 の位数 e = 51523324958230 は ℓ の約 688.75 倍で、 4e = 2755(ℓ − 6) を満たす。五つ目の例は 386垓 = 3.86 × 1022 台:
n = 38622918204908771172351
p = 69482837993, ℓ = 555862703950
対応する e = 3474141899650 は ℓ の約 6.25 倍で、 4e = 25(ℓ − 6) を満たす。六つ目の例は 1030垓 = 1.03 × 1023 台:
n = 103415234565529894320951
p = 113696544893, ℓ = 909572359150
対応する e = 434030875301782850 は ℓ の約 477181.25 倍で、 4e = 1908725(ℓ − 6) を満たす。ここまでの六つの例では、どれも p ≡ 3 (mod 10)、従って ℓ ≡ 10 (mod 20), n ≡ 11 (mod 20) だ。（2025年2月26日）
〔追記4〕 (2p + 1)(4p + 1) 型の七つ目の擬素数は、p = 1812558716333 のときの、
n = 26282952801248737440033111 ≈ 2.6 × 1025
ℓ = 14500469730670, e = 3267263965300375810
だ。 e は ℓ の約 225321.25 倍で、 4e = 901285(ℓ − 6) を満たす。（2025年3月4日）
奇数 n = ℓp2 + 1 が、
n = (up + 1)(vp + 1) u, v は正の整数
と分解されるときも、上記と全く同様に u, v は 2 以上の偶数。そのとき、
ℓp2 = n − 1 = uvp2 + up + vp
の両辺を p で割ると:
ℓp = uvp + u + v ‥‥❶
❶から、 u + v = ℓp − uvp = (ℓ − uv)p は、奇数 p の倍数。 u + v は（偶数と偶数の和なので）、 2 の倍数でもあり、従って最小でも 2p に等しい:
u + v ≥ 2p ‥‥❷
和が 2p 以上の二つの正の偶数 u, v について、積 uv の最小値は、 u, v の一方が 2 に等しく他方が 2p − 2 に等しい場合であり†:
uv ≥ 2(2p − 2) = 4p − 4 ‥‥❸
❶に、❸と❷を適用すると:
ℓp = (uv)p + u + v ≥ (4p − 4)p + 2p = 4p2 − 2p
∴ ℓ ≥ 4p − 2
† その理由については「幅 + 高さが 10 cm の長方形の面積」の「応用例」を参照。
このときにも ℓ ≥ p は確かに必要だが、上記の（もっと強い）不等式が成り立つ必要がある。一般の場合に、この不等式をさらに強くすることはできない。
〔例〕 p = 3, ℓ = 10 として:
n = 10p2 + 1 = 91 = 7 × 13 = (2p + 1)(4p + 1)
これは ℓ ≥ 4p − 2 の等号が成り立つ「ぎりぎり」のケース。
n = ℓp + 1 の場合と異なり、 n = ℓp2 + 1 の場合には u = v = 2 は不可能。なぜなら❷から u + v ≥ 2p ≥ 2⋅3 = 6 なので、 u と v の和は最小でも 6。
n が PSP(2) の例として p = 41, ℓ = 660 のとき:
n = 660p2 + 1 = 1109461 = 83 × 13367 = (2p + 1)(326p + 1)
この ℓ は、理論上の最小値 4p − 2 = 162 と比べて約 4.07 倍の大きさを持つ。
[References]
Wright,
https://archive.org/details/sim_mathematical-gazette_1953-05_37_320/page/104/mode/1up
Pseudoprimes to base 2 that are not squarefree,
https://oeis.org/A158358
Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1,
https://oeis.org/A001220
Wieferich prime,
https://t5k.org/glossary/page.php?sort=WieferichPrime
2025-02-17 幅 + 高さが 10 cm の長方形の面積
長方形の面積は「幅 × 高さ」。幅や高さを変えれば、どんな面積にもなる（ように思える）。でも、幅・高さが決まってないとして、もし「幅と高さの和」が決まってる場合、その長方形は、無制限にどんな面積にもなり得るだろうか？
問題 幅と高さの和が 10 cm の長方形の面積は、最大で何 cm2 か。最小で何 cm2 か（幅と高さは、どちらも 0 以上とする）。
この問題は、小学校の算数だけで解くことも可能。「2次関数のグラフ」（放物線）あるいは「2次方程式」と関連付けて、考えることもできるだろう。微分を使って、機械的に解くこともできる（ちょっと味気ないかもしれないが）。
とりあえず、具体的な数値例で様子を見る…
| 幅 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 高さ | 9 | 8 | 7 | 6 | 5 | 4 | 3 |
| 面積 | 9 | 16 | 21 | 24 | 25 | 24 | 21 |
幅と高さが両方 5 cm のとき（つまり長方形が正方形になるとき）、面積が最大の 25 cm2 になるようだ。
これは、そう不思議でもない。だって、もし幅が 0、高さが 10 だったら、面積は 0 × 10 = 0 になってしまうし、もし幅が 10、高さが 0 だったら、やはり面積は 10 × 0 = 0 になってしまうので、「幅 + 高さが一定の長方形」は、細長ければ細長いほど面積がゼロに近づくような感じがする（横に細長い場合でも、縦に細長い場合でも）。とすると、面積がでかくなるようにしたければ「細長さがなくなる」ようにした方が良さそう。「細長さのない長方形」の究極は「正方形」だろう。
予想 幅 + 高さが 10 cm の長方形は、幅 = 高さ = 5 cm のとき、面積が一番大きくなる。言い換えると、幅 + 高さが 10 cm の長方形の面積が、 25 cm2 を超えることはない。
この予想が正しいことは、いろんな方法で証明できる。以下では3種類のアプローチを考えてみたい。
〔付記〕 「幅 + 高さが一定の長方形」は、周囲の長さも一定（幅と高さの和の2倍）。地面に長方形の領域を作るとして、その領域を「伸び縮みしないロープ」で囲って示す場合、ロープの長さが一定なら、無限に広い領域を囲むことは不可能だろう（例えば 1 m のロープで 100 m2 の土地を囲むのは、どう考えても無理だろう）。「周囲の長さが一定の長方形」の面積には、何らかの限界があるはずだ。
算数編
幅 + 高さ = 10 の長方形の「幅」を 5 + A とすると、「高さ」は 5 − A だ。同様に、「幅」が 5 − A なら、「高さ」は 5 + A だ。
どちらにしても、この長方形の面積は、
(5 + A) × (5 − A)
だ。どっちが「幅」でどっちが「高さ」でも、両者の積は同じなので、幅が 5 + A、高さが 5 − A とすると:
面積 = (5 + A) × 高さ = 5 × 高さ + A ×高さ ‥‥①
高さ = 5 − A なので:
①の値 = 5 × (5 − A) + A × (5 − A)
= (5 × 5) − (5 × A) + (A × 5) − (A × A)
= 25 − (A × A) ‥‥②
A = 0 なら A × A = 0 だが、 A が 0 より大きければ A × A も 0 より大きい。だから、②の値は、
A = 0 なら 25 − 0 = 25
となり、
A ≠ 0 なら 25 − (0より大きい数) = (25より小さい数)
となる。つまり、この長方形の面積は 25 に等しいか、または 25 より小さい。 25 より大きくなる可能性はないっ！
一方、可能な最小の面積は、②で A = 5 とした場合の 25 − 25 = 0 だ。これは、幅・高さの一方が 5 − A = 0 で他方が 5 + A = 10 の場合に当たる（幅が 0 で高さが 10 の「長方形」は、本当に長方形といえるのか？というのは、異論の余地があるかもしれないが、一応「それも長方形の一種」ってことにしておく）。
〔参考〕 もし公式 (x + y)(x − y) = x2 − y2 を使うなら、
長方形の面積 = (5 + A) × (5 − A) = 25 − A2
となって、直ちに②を得る。
2次方程式編
この長方形の幅を x、高さを y とすると、 x + y = 10 つまり y = 10 − x。その面積を c とすると:
c = xy = x(10 − x) = 10x − x2
右辺を移項すると:
x2 − 10x + c = 0
従って、この長方形の幅は、
x = 5 ± √(25 − c)
となるが、この解が存在するためには 25 − c が（実数の範囲で）平方根を持たなければならない。つまり:
25 − c ≥ 0
∴ 25 ≥ c
これは「面積 c は 25 以下」という意味なので、面積の最大値は 25 cm2 だ（最小値は x = 0 または y = 0 の場合の 0 cm2）。
微分編
長方形の幅を x、高さを 10 − x として、長方形の面積 x(10 − x) = 10x − x2 を x の関数 f(x) と見ると、
導関数 f′(x) = 10 − 2x
は x = 5 のとき値が 0。 そのとき f″(x) = −2 < 0 なので、 x = 5 のときの面積 f(5) = 25 は極大。題意から 0 ≤ x ≤ 10 なので、これが面積の最大値。一方、面積の最小値は 0 だ（x = 0 または x = 10 の場合）。
〔注〕 f″(x) を使わずに、次のように考えることもできる。 f′(x) = 10 − 2x の値は、x が 5 より小さければ正、 5 より大きければ負なので、 f(x) は x が 5 になるまでは値がどんどん増え、 x が 5 より大きくなると下降（減少）に転じる。だから x = 5 の瞬間、値が一番でかい！
一般化と応用
どの解法を使うにせよ、同様に考えると、次の結論に至る。
- 「幅と高さの和」が一定の長方形は、細長ければ細長いほど（幅または高さが 0 に近ければ近いほど）面積が小さくなる。そして正方形になる場合（幅 = 高さ）に、面積が最大。
- 長方形の幅と高さに限らず、一般に2数 u, v がどちらも負でない場合、もし和 u + v が一定なら、 u = v のとき積 uv は最大になり、 u または v が 0 に近ければ近いほど積 uv は小さくなる。
応用例 u, v をどちらも 2 以上の偶数、 p を 3 以上の一定の奇数とする。「u + v が 2p 以上」という条件において uv の最小値は何か。
〔注〕 「Hardy–Wright の「定理101」を改善」の「和が 2p 以上の二つの正の偶数 u, v について、積 uv の最小値は」という部分で、この問題の答えを説明なしに使った。以下は、その補足を兼ねる。
解 u + v が一定の場合、 u または v が 0 に近ければ近いほど uv は小さい。ただし、ここでは u, v は 2 以上の偶数なので、最小でも 2。従って、この場合、一定の和 u + v に対応する uv の最小値は、
2 × ((u + v) − 2) ☆
となる。偶数の和 u + v は偶数。問題の条件から、この和は 2p 以上だが、 2p も偶数なので、 u + v は、
2p, 2p + 2, 2p + 4, ···
のどれかに等しい。 u + v が小さければ小さいほど、当然 ☆ の値は小さくなるので、 uv の値をなるべく小さくしたければ、 u + v = 2p が最善の選択肢。そのときの ☆ の値
2(2p − 2) = 4p − 4
が、与えられた条件での uv の最小値だ。∎
〔例〕 p = 7, u + v = 2p = 14 の場合、 uv の最小値は 2(2p − 2) = 2 × 12 = 24。それ以外のどんな選択肢を使っても、 uv をさらに小さくすることはできない――「u, v が正の偶数で u + v ≥ 2p」という条件下では。例えば u = 4, v = 10, u + v = 2p = 14 のときの uv = 40 や、 u = 2, v = 14, u + v = 2p + 2 = 16 のときの uv = 28 は、 24 より小さくならない。
2025-02-22 「30 の約数だが 10 の約数ではない数」は？
問題 30 の約数だが 10 の約数ではない正の整数は何か。
この問題は、答えを出すだけなら、ほとんど誰でも解くことができるだろう。 30 の約数は、
1, 2, 3, 5, 6, 10, 15, 30
の八つ、10 の約数は、
1, 2, 5, 10
の四つなので、この四つ以外の数を上の八つから抜き出せば、
答え 3, 6, 15, 30
となる。確かに 3 は「30 の約数だが 10 の約数ではない」し、 6 も「30 の約数だが 10 の約数ではない」し、 15 も 30 もそうだ。
けれど約数を一つ一つ列挙するのは面倒なので、もう少し体系的に考えてみたい。このメモの本題っつーか最終目標は、 p が素数のとき「ℓp の約数だが ℓ の約数ではないような数は、 p の倍数」っていう性質が「当たり前」と感じられるようになる、ってこと。実は全然大したことじゃないんだけど、かつて1951年に「巨大素数の世界記録」が更新されたとき、この性質は一つの鍵となった。
2 以上の数のうち、 1 と自分自身以外の約数を持たない数を素数という。 2, 3, 5, 7, 11 は素数だが 4, 6, 8, 9, 10 は素数ではない（合成数）。合成数は、二つ以上の素数の積として表される。
4 = 2 × 2 6 = 2 × 3 8 = 2 × 2 × 2
9 = 3 × 3 10 = 2 × 5 ···
のように。ある一つの数の「素数の積での表現」（素因数分解）は、掛け算の順序の違いを無視すれば、必ず一定の「素数の成分」（素因子、素因数）から成る。例えば、 100 = 4 × 25 は、
2 × 2 × 5 × 5
と素因数分解され、「成分」は 2 が二つで 5 が二つ。
100 = 2 × 2 × 5 × 5 = 2 × (2 × 5 × 5) = 2 × 50 なので、 100 が 2 の倍数であること（50倍）は明らかだろう。言い換えれば 2 は 100 の約数。
100 = 2 × 2 × 5 × 5 = (2 × 2) × (5 × 5) = 4 × 25 なので、 100 が 4 の倍数であること（25倍）も明らか。言い換えれば 4 は 100 の約数。
100 = 2 × 2 × 5 × 5 = (2 × 5) × (2 × 5) = 10 × 10 なので、 100 が 10 の倍数であること（10倍）も明らか。言い換えれば 10 は 100 の約数。
一般に、もしある数 n が A × B × C × D と分解されるとき（A, B, C, D は必ずしも相異ならない素数）、 A, B, C, D はどれも n の約数だし、 A, B, C, D のうち二つ以上（全部でも可）を好きに選んで掛け算したもの（例えば AB とか AC とか BCD など）も n の約数。
もちろん n は、ちょうど四つの素因子 A, B, C, D を持つとは限らない。素因子の数は二つかもしれないし、三つかもしれないし、五つ以上かもしれない。あるいは n が素数なら、素因子は n 自身の一つだけ。それでも考え方の原理は同じ。つまり、 n が s 個の素因子、
q1, q2, ···, qs
の積から成るとき、その一つ一つはどれも n の約数だし、 s 個の中から二つ以上（s 個全部でも可）を選んで掛け合わせたものも n の約数。最後に 1 という数も、もちろん全ての整数の約数なので、一応、次のように整理できる。
n が次のように s 個の素因子に分解されるとする。
n = q1q2···qs
このとき n の約数は、 1 か、または、
q1, q2, ···, qs
のどれかか、または、それら s 個の中から「二つ以上を選んで掛け算したもの」のどれかに等しい。
〔注〕 「二つ以上を選んで掛け算」の部分では、もちろん同じもの（例えば q1 なら q1）を 2 回以上選ぶことはできない。例えば 30 = 2 × 3 × 5 の場合、 2, 3, 5 の二つ以上を任意に選んで掛け算したもの（2 × 3 = 6 とか 2 × 5 = 10 など）は 30 の約数だが、 2 × 2 = 4 とか 3 × 3 = 9 とかは 30 の約数ではない。しかし q1, q2, ··· の中に値が等しい数があるなら、結果的に同じ素因子を 2 回以上選べることになる。例えば 20 = 2 × 2 × 5 の場合 2 × 2 = 4 もその約数。これは q1 を 2 回選んだわけではなく q1 = 2 と q2 = 2 を 1 回ずつ選んだ場合（そしてその二つは、たまたま値が等しかった）。
最初に戻って、 30 の素因数分解は 2 × 3 × 5 なので、 30 の約数は、
1 または 2, 3, 5 のどれか または 2, 3, 5 のうち二つか三つを掛け算したもの
だし、 10 の素因数分解は 2 × 5 なので、 10 の約数は、
1 または 2, 5 のどれか または 2, 5 のうち二つを掛け算したもの
に等しい。
すると「30 の約数だけど 10 の約数ではない」ということは、要するに「30 の約数のうち、約数の成分（素因子）として 3 を含むやつ」ってことになる！
次のように考えると、見通しがいい―― 30 の約数は、「10 の約数（でもあるような数）」と「10 の約数（でもあるような数）の 3 倍」に分けられる。そのうち前者は「10 の約数」なので、結局「30 の約数だけど 10 の約数ではない」ってことは、
「10 の約数（でもあるような数）」の 3 倍
に他ならない。よって 10 の約数 1, 2, 5, 10 を 3 倍して:
（答え） 3, 6, 15, 30
別の例。 70 の約数だけど 10 の約数ではない数は？
〔解〕 70 の約数は「10 の約数（でもあるような数）」と「その 7 倍」に分けられる。条件を満たすのは後者なので、 1, 2, 5, 10 をそれぞれ 7 倍して 7, 14, 35, 70 が答え。確かに 7 は「70 の約数だけど 10 の約数ではない」。 14, 35, 70 もそうだ。
別の例2。 110 の約数だけど 10 の約数ではない数は？
〔解〕 110 の約数は「10 の約数（でもあるような数）」と「その 11 倍」に分けられる。条件を満たすのは後者なので、 1, 2, 5, 10 をそれぞれ 11 倍して 11, 22, 55, 110 が答え。確かに 11 は「110 の約数だけど 10 の約数ではない」。 22, 55, 110 もそうだ。
同様に考えると、一般に ℓ が整数で p が素数のとき（ただし ℓ は p の倍数ではないとする）、「ℓp の約数だが ℓ の約数ではない数」というのは、 ℓ の約数を p 倍したものに他ならない。
〔例〕 140 の約数だが 20 の約数ではない数は何か（ℓ = 20, p = 7）。 140 の約数は「20 の約数（でもあるような数）」（1, 2, 4, 5, 10, 20）と「その 7 倍」に分けられる。答えは「20 の約数」をそれぞれ 7 倍したもの（7, 14, 28, 35, 70, 140）。
ここで重要なのは、条件を満たす数を細かくリストアップする作業ではなく、もう少し抽象的に、
「ℓp の約数だが ℓ の約数ではない数」は p の倍数である
ってこと。
上記のいろいろな具体例からも分かるように、そのような数は「ℓ の約数を p 倍したもの」なんで、もちろん p の倍数。
ここまでの具体例では、 ℓ は p の倍数ではなかった。言い換えると ℓ が素因子 p を含んでいなかった。 ℓ が素因子 p を含んでいても結論には変わりないのだが、途中の部分で微妙な違いが生じる。
例えば ℓ = 10, p = 5 の場合。「50 の約数だが 10 の約数ではない数」を知りたい。この場合、 50 の約数を、
「10 の約数（でもあるような数）」（1, 2, 5, 10） と 「その 5 倍」（5, 10, 25, 50）
に分けても、後者が条件を満たすとは言い切れない。確かに 25 と 50 は「50 の約数だが 10 の約数ではない数」だけど、 5 と 10 は「50 の約数だが 10 の約数ではない数」という条件に当てはまらない（どちらも 10 の約数だ）。
この例の場合、 ℓp の素因数分解は 50 = 2 × 5 × 5 で、 ℓ の素因数分解は 10 = 2 × 5 なので、「前者にはあるが、後者にはない素因数」というものが存在しない（前者も後者も、同じ2種類の素数 2 と 5 だけから成っている）。そのため、一つの素因数 p の有無だけによって、「50 の約数かどうか」と「10 の約数かどうか」を切り分けることができない。つまり ℓp = 50 の約数のうち「因子 5 を含むもの」を選んでも、選ばれた数は「10 の約数ではない」という条件を満たすとは限らない（ℓ = 10 の約数も因子 5 を含み得るので）。
50 = 2 × 5 × 5 の約数なら持ち得るけど 10 = 2 × 5 の約数が絶対に持ち得ない性質。それは「素因子 5 を二つ含むこと」。だからこの場合、50 の約数を「2 の約数（でもあるような数）」（1, 2）と「その 5 倍」（5, 10）と「そのさらに 5 倍」（25, 50）に分けて考えると、最初の二つのグループは 10 の約数でもある一方、三つ目のグループは 10 の約数ではない。このようにして「50 の約数だが 10 の約数ではない数」を過不足なく求めることができる。答えの 25, 50 は、単に 5 の倍数というだけでなく、実は 52 = 25 の倍数でもある。
とはいえ、「もし e が ℓp の約数だが ℓ の約数でないなら、 e は p の倍数」という本題との関連では、 ℓ が素因子 p を持つとしても持たないとしても、結論は同じなので、あまり気にする必要ないかも…
〔補足〕 ℓ が素因子 p を持つ場合、「もし e が ℓp の約数だが ℓ の約数でないなら、 e は p の倍数」というだけなく、より強く「もし e が ℓp の約数だが ℓ の約数でないなら、 e は p2 の倍数」といえる。でも p2 の倍数も p の倍数であることに変わりはないので、上述のように、 ℓ が素因子 p を持つ場合も持たない場合も、統一的に扱うことができる。
2025-02-24 1387 と 1729 6億3531万8657の秘密
341, 561, 645, 1105, 1387, 1729, 1905, ··· という偽物の素数 PSP(2) のうち、最初の四つと 1905 が本物の素数でないことは一目瞭然（末尾が 5 の数は 5 で割り切れるし、両端の桁の和が真ん中の桁に等しい3桁の数は 11 で割り切れる）。一方、 1387 と 1729 の二つは、もしかすると素数かもしれないような感じがする。
もっとも 1729 は、インドの不思議な天才ラマヌジャンのエピソードで有名な数でもあり、立方数 123 = 1728 より 1 大きいので、
恒等式 a3 + 1 = (a + 1)(a2 − a + 1)
で a = 12 と思えば、 13 で割り切れることが分かる:
1729 = 123 + 1 = (12 + 1)(122 − 12 + 1) = 13 × 133 = 13 × (7 × 19)
あるいは 1729 = 1000 + 729 = 103 + 93 ということと、
恒等式 a3 + b3 = (a + b)(a2 − ab + b2)
から:
1729 = (10 + 9)(102 − 10⋅9 + 92) = 19 × 91 = 19 × (7 × 13)
最初の恒等式は、二つ目の恒等式で b = 1 とした場合に他ならず、ラマヌジャンのエピソードというのは、
1729 = 123 + 13 = 103 + 93
という等式と関係している。ハーディーの言葉†を引用しよう。
彼は、数の個性を記憶にとどめることができた。ほとんど薄気味悪いほどであり、リトルウッドをして「一つ一つの正の整数は、どれもラマヌジャンの個人的な友達だった」と言わしめたものである。思い出すのは、パトニーで病床に伏せっていた彼を見舞いに行ったときのこと。私が乗ったタクシーのナンバーは「1729」だった。「なんだかつまらない数だね。不吉な前兆でないといいけど」と私が言うと、彼は「いいえ」と答えた。「それはとても面白い数です。二つの立方数の和として 2 通りに表現可能な、最小の数です」
自然の成り行きとして、私は彼に尋ねてみた。4乗和についての同様な問題の解が分かるか、と。彼はちょっと考えてから、「明らかな例は見つからない」と答え、そのような最初の数はとても大きいに違いないと予想した。
† https://archive.org/details/pli.kerala.rare.37877/page/n17/mode/1up
このエピソードは、しばしば「ラマヌジャンの計算能力は超人的だった」というような文脈で語られるのだが、実際には、計算自体は驚くようなことでもない（93 や 123 をいちいちその場で暗算するわけではなく、何度も使ううち、自然と覚えてしまっている）。病人の興味を引いて元気づけるため、ハーディーはわざと「つまらない数だ」ととぼけて、話を振ったのかもしれない。ラマヌジャンの奇妙さはとてもこんなレベルではないけど、その一端を垣間見ることのできる逸話ではある。
〔余談〕 エイプリルフールのジョーク記事で、質問者が「12個の3でもできるか」と尋ねて、人工知能が「自明な式は見つからない。あるとすれば、美しくないだろう」と答える部分は、上記のエピソードのパロディー。
〔参考〕 Euler は、既に4乗和バージョンの最小解 635318657 = 1334 + 1344 = 594 + 1584 を得ているばかりか、その解を得る手順を記している:
https://web.archive.org/web/20250214154157/https://scholarlycommons.pacific.edu/euler-works/716/
https://web.archive.org/web/20240415152141/https://scholarlycommons.pacific.edu/euleriana/vol3/iss2/3/
https://archive.org/details/historyoftheoryo02dickuoft/page/644/mode/1up
1000 以下の四つの数を使った解は、次の通り（より小さい解の4数をそれぞれ 2 倍・3倍···したものを除く）。
635318657 = 594 + 1584 = 1334 + 1344 Euler (1778, 1802)
3262811042 = 74 + 2394 = 1574 + 2274 Werebrusow (1912, 1913)
8657437697 = 1934 + 2924 = 2564 + 2574 Werebrusow (1912, 1913)
68899596497 = 2714 + 5024 = 2984 + 4974 Leech (1957) コンピューター使用
86409838577 = 1034 + 5424 = 3594 + 5144 Euler (1778, 1802)
160961094577 = 2224 + 6314 = 5034 + 5584 Leech (1957) コンピューター使用
一つ目・三つ目は n4 + (n+1)4 の形を持つ。常にではないが、和の末尾（最下位桁）は 7 になりやすい。第一に x4 + y4 が奇数なら x, y の一方は偶数、他方は奇数だが、末尾 0 以外の偶数の4乗は末尾 6、末尾 5 以外の奇数の4乗は末尾 1。高確率で 6 + 1 が生じ、低確率で 0 + 1 または 6 + 5 が生じる（仮定から x, y は公約数 5 を持たないので 0 + 5 は不可能）。第二に x4 + y4 が偶数なら x, y はどちらも奇数（仮定から公約数 2 を持たないので、両方偶数ではない）。この場合 1 + 1 が生じやすく、まれに 1 + 5 が生じる。単純に考えて「両方奇数」より「偶数と奇数」の方が選択肢の幅が広いので、第一のケースが多いはず。
本題の n = 1387 = 19 × 73 は、素数でないのに
2n ≡ 1 (mod n)
を満たす。この 1387 を法とする 2 の位数は e = 18 だ。実際、
218 = 262144 = 189 × 1387 + 1
なので 218 を 1387 で割った余りは 1。他方、 29 = 512 や 26 = 64 を 1387 で割っても、明らかに商は 0 であり、従って余りは 1 ではない。要するに 2 を 18 乗すれば ≡ 1 だから e は最大でも 18 で、もしかするとその約数の 9, 6 などだが、実際には 9, 6 などの指数では ≡ 1 にならないから e = 18 と確定。
今、素数 p = 3 を使って 1387 = 462p + 1 と書くと、
2462p ≡ 1 (mod 1387)
が成り立つ。位数の性質から e = 18 は 462p = 1386 の約数。しかし e = 18 は 462 の約数ではないので（18 は 32 で割り切れるが 462 は 31 でしか割り切れない）、 e = 18 は p = 3 の倍数（実際には、この場合、より強く e = 18 は p2 = 9 の倍数）。
「e が ℓp の約数だが ℓ の約数ではないとき、 e は p の倍数」という性質は、 ℓ が素因子 p を持たない場合（特に ℓ < p の場合）に最も分かりやすいが、 ℓ が素因子 p を持つ場合にも、そのまま成り立つ。より正確に言うと、「e が ℓp の約数だが ℓ の約数ではないとき、もし ℓ が素因子 p をちょうど a 個持つなら、 e は素因子 p をちょうど a+1 個持つ」。
ℓ は p で a 回割り切れるが、 a+1 回は割り切れないとしよう（a は 0 以上の整数）:
ℓ = pam ここで m は p で割り切れない整数
もしもこの条件で e が素因子 p を a 個以下しか持たなかったら（そして e の他の素因子は m にも含まれるなら）、 e は ℓ = pam の約数になってしまい前提に反するし、もしも e が素因子 p を a+2 個以上持つとしたら、 e は、
ℓp = (pam)p = pa+1m
の約数にならず、これも前提に反する（e が m に含まれないような p 以外の素因子を持つとしたら、 e は上記 ℓp の約数にならず、やはり前提に反する）。
n = 1387 = 462p + 1 = 19 × 73 = (6p + 1)(24p + 1) のように、 1387 は「3k+1型」の合成数であり、「3k+1型」の二つの素数の積に分解される（1387 自身について、そして因子の 19 と 73 については、「3k+1型」とも「6k+1型」とも言える）。
なぜ？
仮に 1387 = AB と二つの素数の積に分解されるとすれば、 Euler の定理と位数の性質から φ(1387) = (A − 1)(B − 1) は e で割り切れる。しかもその e が素数 p = 3 で割り切れるのだから、 A − 1 と B − 1 の少なくとも一方は 3 で割り切れる。前者が 3 で割り切れるとすると、 A は「3k+1型」。そこで A = 3u + 1, B = 3v + r と書くと（r は B を 3 で割った余り）、
1387 = AB = (3u + 1)(3v + r) = 3⋅3uv + 3u + 3v + r = 3(3uv + u + v) + r
となるが、 1387 = 462⋅3 + 1 自身「3k+1型」なので、 r = 1 でなければならない:
1387 = (3u + 1)(3v + 1)
どちらの因子も「3k+1型」となる！
のみならず、 3u + 1 と 3v + 1 は、どちらも奇数（積が奇数なので）。よって u, v はどちらも偶数。
u = 2u′, v = 2v′
とすると、こうなる:
1387 = (6u′ + 1)(6v′ + 1)
具体的には u = 6, v = 24; u′ = 3, v′ = 12 だ。実際、
6⋅231 + 1 = 1387 = (6⋅3 + 1)(6⋅12 + 1) = 19 × 73
となって、二つの素因子は「6k+1型」でもある。
2025-03-01 Hardy–Wright の「定理101」を拡張 定理6
2025年2月現在、知られている最大の素数 M は約4100万桁（2024年10月発見）。ところで、既知の素数を基に、桁数が約3倍の素数を見つける方法がある。1950年代に証明された定理だが、知名度は低そう。原理的には、このマイナーな定理を M に適用すれば約1億2000万桁の素数が得られ、「1億桁」の賞金15万ドルが手に入る！（笑）
原論文には分かりにくい部分があるので、なるべく簡単化した形で、整理してみたい。
Hardy–Wright の Theorem 101 の、共著者 Wright 自身による拡張。
E. M. Wright, “The Calculation of Large Primes”, The Mathematical Gazette (1953), Volume 37, Issue 320, pages 104–106
https://archive.org/details/sim_mathematical-gazette_1953-05_37_320/page/104/mode/1up
証明が簡単かはともかく、定理の内容自体は簡単。 p が奇数の素数で ℓ が「十分小さい偶数」（立方数を除く）のとき、
n = ℓp3 + 1
という数は、次の二つの条件（定理4・定理5と同じ）を満たせば、必ず素数。
第一の条件 2n−1 を n で割ると 1 余る
第二の条件 2ℓ を n で割った余りは 1 ではない
「十分小さい偶数」の定義については、後述。
〔例〕 素数 p = 13 を基に ℓp3 + 1 の形の素数を探す。 p3 = 133 = 2197 なので:
ℓ = 2 ⇒ n = 2 × 2197 + 1 = 4395 ⇒ 24394 を 4395 で割った余り 3199 は 1 でない
ℓ = 4 ⇒ n = 4 × 2197 + 1 = 8789 ⇒ 28788 を 8789 で割った余り 7054 は 1 でない
ℓ = 6 ⇒ n = 6 × 2197 + 1 = 13183 ⇒ 213182 を 13183 で割った余りは 1
最初の二つの n は、第一の条件（Fermat test）を満たさない。このような n は絶対に素数ではない。 Fermat test を行うまでもなく、最初の n が 5 で割り切れること、二つ目の n が 11 で割り切れることは、一目瞭然だろう（8789 のように、奇数番目の桁の和と偶数番目の桁の和が等しい数は、 11 で割り切れる）。三つ目の n = 13183 は第一の条件を満たすので、素数の可能性が高い。この場合、 26 = 64 を n = 13183 で割った余りは、もちろん 64 自身（商は 0）であり、 1 ではない。よって第二の条件も満たされ、 13183 は素数と確定。2桁の素数 13 を基に5桁（約3倍の長さ）の素数が得られた！
〔注〕 上の例は説明のためのミニチュアで、この大きさの数が素数かどうか調べるには、直接 2, 3, 5, 7, 11, ··· など、 √13183 ≈ 114 以下の小さい素数で割ってみて、割り切れるかどうか調べた方が手っ取り早い。
n = ℓp + 1 の場合（定理4）と、 n = ℓp2 + 1 の場合（定理5）では、有効な ℓ の限界（上界）が 4p のオーダーで（正確には定理4では ℓ < 4p + 4、定理5では ℓ < 4p − 2）、 ℓ < p であれば余裕で十分だった。 n = ℓp3 + 1 の場合、 ℓ の上界がおよそ半分の桁数の 2√(2p) のオーダー。 ℓ < 2√p あるいは ℓ < √p であれば余裕で十分。多少範囲を狭くしても、 p が巨大なら、
ℓ = 2, 4, 6, 10, 12, 14, 16, ···, 60, 62, 66, 68, ···
の選択肢は、使い切れないくらいたくさんある（注: 立方数 23 = 8, 43 = 64, 63 = 216, ··· は有効なオプションではない）。例えば p が20桁とすると √p はざっと10桁、つまり10億のオーダー†なので、それだけでも ℓ の選択肢は何億個もある。
† 「10桁」の整数が10億のオーダーだということは、「12億3456万7890」という数を考えれば明らかだろう（0～9 の数字は 10 個なので）。あるいは、同じことだが:
1 billion 234 million 567 thousand 890
以下で見るように、実はタイトな上界は ℓ < 2√(2p + 2) − 2 だ。いずれにしても、範囲の条件を満たすためには、とりあえず ℓ が p より小さいことが必要（一般には、それだけでは十分ではないが）。というのも、有効な ℓ の限界（上記の不等式の右辺）を大文字の L で表すと、
√3 = 1.732… √6 = 2.449… √7 = 2.645…
なので、
p = 5 ⇒ L = 2√12 − 2 = 4√3 − 2 ≈ 4(1.7) − 2 = 6.8 − 2 = 4.8
p = 7 ⇒ L = 2√16 − 2 = 8 − 2 = 6
p = 11 ⇒ L = 2√24 − 2 = 4√6 − 2 ≈ 4(2.4) − 2 = 9.6 − 2 = 7.6
p = 13 ⇒ L = 2√28 − 2 = 4√7 − 2 ≈ 4(2.6) − 2 = 10.4 − 2 = 8.4
···
のように、 L は p より小さい（p ≥ 5 なら）。 p = 13 の時点で p は L より 4 以上大きく、 p がさらに大きくなるとき、 p の増加よりも √(2p + 2) の増加は遅いので、 p と L の差はますます開く†。 p = 3 の場合についても、 √2 = 1.414… なので、
p = 3 ⇒ L = 2√8 − 2 = 4√2 − 2 ≈ 4(1.4) − 2 = 5.6 − 2 = 3.6
のとき、正の偶数 ℓ < L が取り得る値は ℓ = 2 に限られ、やはり p = 3 より小さい‡。
† f(p) = p − L = p − [2(2p + 2)1/2 − 2] を p について微分すると:
f′(p) = 1 − (1/2)[2(2p + 2)−1/2 × 2] = 1 − 2/√(2p + 2)
p > 1 のとき、右辺の分母は √4 = 2 より大きいから分数の値は 1 未満で f′(p) は正、よって f(p) は単調に増加。ちなみに p = 1 のとき f′(p) = 0 で −1 < p < 1 のとき f′(p) < 0 なので、 p = 1 のときの f(p) = −1 が極小値。このことは f″(p) = 2(2p + 2)−3/2 の実数値が正であることからも明らか。
‡ p = 3 のとき L = 3.65… 自体は p より大きい。しかし条件 ℓ < L を満たす正の偶数 ℓ は 2 に限られ、それは p より小さい。ちなみにこの場合、唯一の n の可能性は 2(3)3 + 1 = 2⋅27 + 1 = 55 だが、これは素数ではない。この定理による素数探しでは p = 3 は不毛で、実質 p ≥ 5 ということになる。
定理の正確な内容をまとめると、次の通り。
定理6（Wright, 1953年） p を 3 以上の素数、 ℓ を
ℓ < 2√(2p + 2) − 2
の範囲の正の偶数とする（簡略に、
ℓ ≤ √(2p + 2)
の範囲としてもいい）。 ℓ は立方数ではない、と仮定する。もし奇数 n = ℓp3 + 1 が、
2n−1 ≡ 1 (mod n)
を満たし、しかも、
2ℓ ≢ 1 (mod n)
が成り立つなら、 n は素数である。
定理4・定理5と同様に、 Fermat の定理の逆を強化して擬素数を排除している。 ℓ の範囲指定がやや複雑で、「立方数ではない」という条件も追加されている。現実的に、もし ℓ が立方数 u3 に等しいなら、
n = ℓp3 + 1 = u3p3 + 1
= (up)3 + 1 = (up + 1)[(up)2 − up + 1]
となってしまい（最後の等号は、 up を一つの文字だと思って、
恒等式 X3 + 1 = (X + 1)(X2 − X + 1)
に当てはめたもの）、 n は up + 1 の倍数なので、素数になり得ない。つまり立方数の ℓ を無視しても、素数の検出の上では無害。
〔例〕 p = 23, ℓ = 8 = 23 のとき、
n = ℓp3 + 1 = 23⋅233 + 1 = 97337
は (2⋅23 + 1)[(2⋅23)2 − 2⋅23 + 1] と分解されるので、素数のはずがない。この分解は、
(2⋅23 + 1)[(22⋅23 − 2)⋅23 + 1] = (2⋅23 + 1)(90⋅23 + 1) なので (up + 1)(vp + 1) の形を持つ。ただし v = u2p − u。
〔注〕 上の例では n の因子 up + 1 = 47 は素数だが、 ℓ が立方数の場合のこの形の分解では、一般には up + 1 は素数とは限らず、 vp + 1 も素数とは限らない（どちらも合成数になる例: ℓ = 43, p = 547）。
証明の流れは、定理3～定理5の場合と同様（定理3の証明・定理4の証明・補足説明を参照）。すなわち、奇数 n = ℓp3 + 1 が、定理6の条件を満たすとして、もしも n が合成数だったら、何らかの形で、例えば、
n = AaBb···Dd
のように、複数の素因数に分解されるはず。このとき mod n での 2 の位数 e は、 n − 1 = ℓp3 の約数だが、 ℓ の約数ではないので、 p の倍数。
φ(n) = Aa−1Bb−1···Dd−1(A − 1)(B − 1)···(D − 1)
は e の倍数なので p の倍数でもあり、従って A − 1, B − 1, ··· , D − 1 の少なくとも一つは p の倍数。その一つを U − 1 とすると、素数 U は p の倍数より 1 大きいので U = up + 1 と表現可能。 n 自身も p の倍数より 1 大きいので、余因子 V = n/U も同じ形 vp + 1 を持ち、
n = UV = (up + 1)(vp + 1) = uvp2 + up + vp + 1
となる。 U は n より小さい素数なので V は 1 より大きく、 u, v は正。のみならず、 n は奇数なので、 u, v はどちらも 2 以上の偶数。
しかし ℓ が「十分に小さい」とき、このような分解 n = UV があり得たとすると、 ℓ の範囲指定との関連で矛盾が生じる（よって実際には分解は不可能で、 n は素数）。定理6の要は、 ℓ の範囲指定のさじ加減。前述のように、定理6における ℓ の範囲指定は p > ℓ を含意しているが、それだけでは十分ではない。 ℓ の範囲をより正確に決定することで、定理が証明される。
証明 ℓp3 = n − 1 = uvp2 + up + vp の両辺を p で割ると:
ℓp2 = uvp + u + v サ
∴ ℓp2 > uvp つまり ℓp > uv シ
一般性を失うことなく v ≥ u と仮定できる。定理の前提は p > ℓ を含意するので、シから:
pp > ℓp > uv ≥ uu
∴ p > u ス
サから、
u + v = ℓp2 − uvp = (ℓp − uv)p セ
は p の倍数。便宜上、その倍率を
x = ℓp − uv ソ
と書くと、セは、
u + v = px タ
∴ v = px − u チ
となる。タの左辺は正の偶数なので（そして右辺の因子 p は正の奇数なので）、 x は正の偶数、つまり x ≥ 2。ところが、シとチとスから:
ℓp > uv = u(px − u) > u(px − p) ≥ 2(px − p) = 2px − 2p
両辺を p で割って:
ℓ > 2x − 2 ≥ x ツ
最後の不等号は 2x − x = x ≥ 2 に基づく。再び定理の前提の含意 p > ℓ を使って、ツから次の不等式を得る:
p > x テ
〔注〕 タとテ（そしてツ）は「u + v は p の偶数倍。その倍率 x は p よりも（そして ℓ よりも）小さい」って意味。素数 p を選んで固定したとき、 ℓp3 − 1 = (up + 1)(vp + 1) = uvp2 + (u + v)p + 1 の左辺は p3 と p4 の間の一定の値なので（なぜなら 2 ≤ ℓ < p）、右辺に含まれる uv や u + v が無制限に大きくはなれないことは、明らかだろう。
今、ソとチから:
ℓp = x + uv = x + u(px − u) = x + pxu − u2
∴ u2 = x + pxu − ℓp = x + p(xu − ℓ) ト
ここで、
y = xu − ℓ ナ
つまり ℓ = xu − y ヌ
と置くと、トはこうなる:
u2 = x + py ネ
ネの左辺は正なので、右辺 x + py も正。従って y は負ではない（もしも y が負だったら、テから x + py は負になってしまう）。のみならず y は 0 でもない。実際、もしも y = 0 だったらネから x = u2 となるので、ヌから ℓ = xu = u3 となってしまい、「ℓ は立方数でない」という前提に反する。従って y は正で、ナから y は正の偶数（x, u, ℓ はどれも偶数だから）。つまり y ≥ 2。
さて、定理の前提から p ≥ 3。その両辺を p 倍し、テに留意すると:
p2 ≥ 3p = 2p + p > 2p + x
ここで R = √(2p + x) と置くと、 p2 > R2 つまり R < p が成り立つ†。同時にスから u < p なので:
u + R < p + p = 2p ノ
一方、 R の定義とネから:
u2 − R2 = (x + py) − (2p + x) = py − 2p
∴ p(y − 2) = u2 − R2 ハ
不等式ノの両辺を y − 2 倍して（y ≥ 2 なので、これは 0 倍、2 倍、4 倍···に当たる。 0 倍なら、両辺とも 0 で等号成立）、ハを使うと:
(u + R)(y − 2) ≤ 2p(y − 2) = 2(u2 − R2) = 2(u + R)(u − R)
両辺を正の実数 u + R で割って、 x ≥ 2 に留意すると:
y − 2 ≤ 2(u − R) ≤ x(u − R) = xu − xR
∴ xR − 2 ≤ xu − y = ℓ ヒ
最後の等号はヌによる。ヒから、
ℓ ≥ xR − 2 = x√(2p + x) − 2 ≥ 2√(2p + 2) − 2
となるが、それは定理の前提 ℓ < 2√(2p + 2) − 2 に反する。すなわち、定理の条件下で n が合成数だとしたら、矛盾が生じる。∎
† 次のように論じることも可能。ネから:
2p + x ≤ yp + x = u2
左辺の（正の）平方根を R = √(2p + x) とすると:
R2 = 2p + x ≤ u2 つまり R ≤ u
このこととスから、 R も u も p より小さい。
x, y が正の偶数であることを導くとこまでは比較的平明だが、平方根 R を使った式変形はトリッキー。ロジックに追随すること自体は難しくないけど、あまり見通しが良くない（しかも原論文では「u, v が偶数」という事実を利用していないため、 x, y が偶数であることを導くだけでも、妙な遠回りをしている）。
簡略バージョン ℓ についての定理の前提を少し妥協して、もっと狭い範囲の
ℓ ≤ √(2p + 2) フ
で手を打つなら、次のように比較的簡潔な証明が成り立つ。 x, y が正の偶数であることを示すところまでは上記と全く同じ。その後のトリッキーな議論の代わりに、ネから、
2p + 2 ≤ yp + x = u2
∴ √(2p + 2) ≤ u ヘ
を得る。実は u < ℓ なので（☆）、ヘは
√(2p + 2) < ℓ
を含意し、直ちにフと矛盾。つまりフの条件では、 n = UV という分解はあり得ない。
〔注〕 フの条件は、 n = UV という分解から矛盾を導くためには（つまり n が素数であることを確定させるためには）十分だが、理論上「必要ぎりぎり」の条件ではない。 ℓ についての（定理6の）本来の範囲制限と比べると、やや過剰な範囲制限となっている。
（☆）の証明。ネを y について解くと:
y = (u2 − x)/p < u2/p < u2/u = u
右側の不等号の根拠は、 p > u であること（ス）、そして「分子が同じ分数」は、（分子・分母が正なら）分母が小さいほど値が大きいこと。要するに、
y < u
であり、従って y の意味（ナ）から:
xu − ℓ < u つまり xu − u < ℓ
∴ (x − 1)u < ℓ
1 以上の奇数 x − 1 で両辺を割ると、
u < ℓ/(x − 1) ≤ ℓ
となって、 u < ℓ が示される。∎
このメモの内容は大筋では正しいはずだが、まだ改良の余地もありそう。
〔参考〕 原論文では、変数 ℓ, x, y, R がそれぞれ k, g, j, U と呼ばれている（この U は、上記の U とは意味が異なる）。印刷ミスなのか、不等号について「より大きい」と「以上」の混同、「より小さい」と「未満」の混同が散見される。
2025-03-06 (4⋅3)3 + 1 = (4⋅3 + 1)(44⋅3 + 1) さざ波のささやき
ラマヌジャンの数 1729 = 123 + 1 = (12 + 1)(122 − 12 + 1) = 13 × 133 は、
(4⋅3)3 + 1 = 43⋅33 + 1 = (4⋅3 + 1)(44⋅3 + 1)
とも解釈可能。単調に、けれど微妙に揺らぎながら、繰り返される 1, 2, 3 や 4, 3, 1 のさざ波が美しい。
p = 3 として上の等式を ℓp3 + 1 = (up + 1)(vp + 1) と見ると、 u + v = 4 + 44 = 48 は p = 3 の偶数倍（16倍）。奇数がこの形の積に分解される場合、必ず u + v は p の偶数倍。
同じ 1728 = 123 を含む次の式も、なかなかいい感じ。穏やかな波の音のような…
46657 = 46656 + 1 = 2162 + 1 = 66 + 1
= 1728⋅33 + 1 = 363 + 1 = (36 + 1)(362 − 36 + 1)
= 37 × 1261 = (12⋅3 + 1)(420⋅3 + 1)
u + v = 12 + 420 = 432 は、やはり p = 3 の偶数倍（144倍、つまり 122 倍）。
上で例に挙げた 1729 と 46657 は、どちらも 2 を底とする擬素数。以下では、一般の正の奇数（擬素数とは限らない）を考える。
p を 3 以上の素数とする。 ℓp3 + 1 の形の奇数 n は、もし ℓ が
L = 2√(2p + 2) − 2
より小さいなら、決して (up + 1)(vp + 1) の形には分解されない。よって「分解されるとすれば、その形だ」と分かっている場合、分解の不可能性から n は素数と確定する（定理6）。
不等式 ℓ < L は、一般の場合には「ぎりぎり」。さらに強くすることはできない。つまり、この不等式が破れて ℓ ≥ L になると（ℓ = L を含む）、分解 n = (up + 1)(vp + 1) が可能なケースが生じる。
〔例1〕 p = 7 のとき、もし ℓ が
L = 2√(2⋅7 + 2) − 2 = 2⋅4 − 2 = 6
に等しいなら、 n = ℓp3 + 1 = 6⋅73 + 1 = 6⋅343 + 1 = 2059。この数は、
(4p + 1)(10p + 1) = 29 × 71
と分解される（因子 29, 71 はどちらも素数）。 u + v = 4 + 10 = 14 は p のちょうど 2 倍。この倍率 x は、必ず 2 以上の偶数となる。言い換えると、
ℓp3 + 1 = (up + 1)(vp + 1)
の形の任意の分解において、 u + v は最小でも 2p だ。その理由は、
ℓp2 + 1 = (up + 1)(vp + 1)
の形の分解の場合（説明）と全く同様。
〔例2〕 p = 17 で ℓ = 2√(2⋅17 + 2) − 2 = 2⋅6 − 2 = 10 のとき、 n = 10⋅173 + 1 = 10⋅4913 + 1 = 49131。この数は、
(6p + 1)(28p + 1) = 103 × 477
と分解される（小さい因子 103 は素数、大きい因子 477 = 3⋅159 は合成数）。 u + v = 6 + 28 = 34 は p のちょうど 2 倍。
〔例3〕 p = 2887 で ℓ = 2√(2⋅2887 + 2) − 2 = 2√(5776) − 2 = 2⋅76 − 2 = 150 のとき、 n = 150⋅28873 + 1 = 3609371715451。この数は、
(76p + 1)(5698p + 1) = 219413 × 16450127
と分解される（小さい因子 219413 = 313⋅701 は合成数、大きい因子は素数）。 u + v = 76 + 5698 = 5774 は p のちょうど 2 倍。
2025-03-19 x3 + y3 = 1729 のいろんな解 10⋅10⋅10 + 9⋅9⋅9 = 19⋅91
x3 + y3 = 1729 が2種類の解 {12, 1} と {10, 9} を持つことは、よく知られている（ラマヌジャンの伝説とともに）。
他にも解があるだろうか？
問題 x3 + y3 = 1729 の一般解を求めること。特に、上記の2種類以外の「自然な」実数解を例示すること。
x3 + y3 = 1729 つまり x3 = 1729 − y3 を満たす任意の y について、 y3 = c とすれば、 x3 = 1729 − c。ゆえに、
x = 3√(1729 − c), y = 3√c
は解。例えば x = 3√1700 を3乗すれば 1700、 y = 3√29 を3乗すれば 29 なので、確かに x3 + y3 = 1729 となる。
しかしこの一般解の表現は、いかにも味気ない！
恒等式 x3 + y3 = (x + y)(x2 − xy + y2) によって、話は面白くなってくる。問題の式は、
(x + y)(x2 − xy + y2) = 1729
と表現可能なので、 1729 = AB という任意の分解（例えば A = 1, B = 1729）について、
x + y = A, x2 − xy + y2 = B = 1729/A
となる。第一式から y = A − x、それを第二式に代入して:
x2 − x(A − x) + (A − x)2 = 1729/A つまり
x2 − Ax + x2 + A2 − 2Ax + x2 = 1729/A
∴ 3x2 − 3Ax + (A2 − 1729/A) = 0 ‥‥①
これは2次方程式なので、機械的に解くことができるっ！ 1729 = AB の A は（0 以外なら）どんな数にもなり得る（A を決めれば、 B = 1729/A は自動的に決まる）。とりあえず、一番シンプルな A = 1 を試してみる。そのとき①は:
3x2 − 3x + (1 − 1729) = 3x2 − 3x − 1728 = 0
両辺を 3 で割って x2 − x − 576 = 0
∴ x = (1 ± √(1 − 4(−576)))/2
=
(1 ± √(2305))/2
なぜなら 576 × 4 = (500 × 4) + (75 × 4) + (1 × 4) = 2000 + 300 + 4
よって ((1 + √(2305))/2)3 + ((1 − √(2305))/2)3 = 1729 となる。 x3 + y3 = 1729 の新しい解が一つ得られた。
〔検算〕 √2305 = 48.0104155… を約 48.0104 とすると:
[(1 + 48.0104)/2]3 + [(1 − 48.0104)/2]3 = 24.50523 + (−23.5052)3 = 1728.99888112
〔検算その2〕 w = √2305 として [(1 + w)/2]3 + [(1 − w)/2]3 = (1 + w)3/8 + (1 − w)3/8 = 1729 であることを確かめたい。代わりに両辺を 8 倍して、
(1 + w)3 + (1 − w)3 = 13832
であることを確かめる。その左辺を展開し、 w2 = 2305 に留意すると:
(1 + 3w + 3w2 + w3) + (1 − 3w + 3w2 − w3) = 2 + 6w2 = 2 + 6⋅2305 = 13832
同様に、 1729 の最小の素因数 A = 7 を使って①を解くと、次の結論に至る。
((7 + √(313))/2)3 + ((7 − √(313))/2)3 = 1729 ‥‥②
1729 の約数 A = 13 ないし A = 19 を使うと、①の解は整数になって、よく知られている関係 123 + 13 = 1729 ないし 103 + 93 = 1729 を得る。 A の値は任意だが、 AB = 1729 なのだから 1729 の約数を使うのが一番簡単で自然だろう。もっとも 19 より大きい約数（次の約数は 7⋅13 = 91 である）を使うと、①の解は非実数となる。というのも、①の判別式は、
D = (3A)2 − 4⋅3(A2 − 1729/A) = 3(−A3 + 6916)/A
なので、もし A が負なら D の分子は正、分母は負で D < 0 だし、もし A が正なら、 D の符号は 6916 − A3 の符号に一致。よって A > 3√6916 = 19.05… なら①は実数解を持たない。
いずれにしても、恒等式 x3 + y3 = (x + y)(x2 − xy + y2) を使うと、ラマヌジャンの数 1729 = 123 + 13 = 103 + 93 は、次のように分解される。
(12 + 1)(144 − 12 + 1) = 13 × 133
(10 + 9)(100 − 90 + 81) = 19 × 91
p = 3 とすると、第一の分解は、
64p3 + 1 = (4p + 1)(44p + 1)
を含意するが、第二の分解は、
64p3 + 1 = (6p + 1)(30p + 1)
を含意する。すなわち ℓp3 + 1 の形の数が (up + 1)(vp + 1) と分解されるとして（p は奇素数、 ℓ は正の偶数）、その分解の仕方は一つとは限らない。この場合、
64p3 + 1 = (2p + 1)(82p + 1) = 7 × 247
という分解の仕方もある（前記②に対応する）。
1729 のような（2 を底とする）擬素数 n が ℓp3 + 1 = (up + 1)(vp + 1) の形を持つことは、さほど珍しくない。しかし大抵の場合、この ℓ は p と比べ、とても大きい値を持つ。 1013 までの範囲の 26万4239 個の擬素数のうち、この形を持ち、かつ ℓ が 100p より小さくなる例は、六つしかないようだ。上記の 1729 の他に、 p = 3 として:
1729 = 64p3 + 1 = (6p + 1)(30p + 1) = 19* × 91
2701 = 100p3 + 1 = (12p + 1)(24p + 1) = 37* × 73*
p = 5 として:
23001 = 184p3 + 1 = (10p + 1)(90p + 1) = 51 × 451
p = 11 として:
622909 = 468p3 + 1 = (2p + 1)(2462p + 1) = 23* × 27083
1357621 = 1020p3 + 1 = (80p + 1)(140p + 1) = 881* × 1541
p = 23 として:
2628073 = 216p3 + 1 = (6p + 1)(822p + 1) = 139* × 18907
* 印の因子は素数。 1729 = 123 + 1 と 2628073 = 1383 + 1 は ℓ が立方数のケースで、 ℓ の大きさを問題にしなければ、必ずこの形式で表現可能。 1729 と 23001 と 1357621 は複数の分解を持つが、ここでは (u + v)/p が最小のものだけを記した。 2701 = 37 × 73 は半素数で、必然的に分解は1種類に限られる。 1729 = 19 × 91 と 2701 = 37 × 73 は、分解が「回文的」になるところが面白い。
2025-03-10 再びメルセンヌ数とジェルマン素数 1000京は20桁
p が素数で 2p + 1 も素数のとき、その p は Germain 素数と呼ばれる（例えば、素数 11 ―― 2 倍して 1 を足した 23 も素数だから）。今 p を「4k+3」型の素数とする。 (i) もし p が Germain 素数なら、 Mersenne 数 Mp = 2p − 1 は 2p + 1 で割り切れる。 (ii) 逆に、もし Mp が 2p + 1 で割り切れるなら、 p は Germain 素数、つまり 2p + 1 も素数。
〔例〕 p = 83 は「4k+3」型の素数。25桁のでかい数、
M83 = 283 − 1 = 9
は、実は 2p + 1 = 167 で割り切れる。よって性質 (ii) から、「167 は素数」と断定できる。逆に、もし 2p + 1 = 167 が素数と分かっているなら、 25桁の割り算をするまでもなく、性質 (i) から、「M83 は 167 で割り切れる」と断定できる。
(i) は比較的よく知られている。 (ii) はそれほど有名ではないけど、幾つかの証明法がある。
〔注〕 「4k+3」型と「4k−1」型は、同義語。前者は「4 の倍数より 3 大きい」という意味で、後者は「4 の倍数より 1 小さい」という意味だが、どっちも同じ対象――3, 7, 11 のような数――を指す。
ちなみに 283 − 1 が、ざっと 8 𥝱 = 8 × 1024 ってことは、「83 は 10 の 8 倍より 3 大きい」ってことから、容易に概算できる。すなわち 210 = 1024 は約 1000 = 103 なので:
283 = 23 × (210)8 ≈ 23 × (103)8 = 8 × 1024 ⇒ 8 から始まる25桁の数
1000兆が16桁、1000京が20桁、1000垓が24桁なんで、上記の数は8
〔例〕 A = 288 は、どのくらいの大きさか？ A は B = 280 = (210)8 ≈ (103)8 の 28 = 256 倍。 B は「1」の後ろに 0 が 3 × 8 = 24 個付く25桁の数。よって A は「256」の後ろに 0 が 24 個付く27桁の数 2.56 × 1026 ≈ 3 × 1026 と見積もられる。真の値は約 3.09 × 1026 だから、それなりに正確な見積もりだ。ちなみに、1𥝱は25桁（1024 = yotta = one septillion）なので A = 288 ≈ 3 × 1026 というのは、約300𥝱（three hundred septillion）。
実用上、 167 が素数かどうか調べるには、 13 未満の素因数を持つかどうか確かめればいい（167 < 169 = 132 なので）。 167 が 2 でも 3 でも 5 でも割り切れないことは、明白。 7 でも 11 でも割り切れないことも、容易に確認可能（実際に割ってみてもいいし、あるいは、3桁の数が 11 で割り切れるかどうかは、「両端の桁の和」が「真ん中の桁またはそれプラス 11」に等しいかどうかで、分かる）。上記 (ii) は、 2p + 1 の素数性判定の有効な手段で、理論的には興味深いが、小さな数 2p + 1 が素数かどうか調べるために巨大整数 2p − 1 を 2p + 1 で割ってみる…というのは、全く実用的でない。
p を「4k+3」型の素数とする。 (i) もし n = 2p + 1 も素数なら（つまり p が Germain 素数なら）、 2p − 1 は n で割り切れる（定理1）。
(ii) 逆に 2p − 1 が n で割り切れるなら、 n は素数。というのも n = 2p + 1 は、定理4の n = ℓp + 1 において ℓ = 2 とした場合だ。「2p − 1 は n で割り切れる」という仮定から、
2p − 1 ≡ 0 つまり 2p ≡ 1 (mod n)
∴ 2n−1 = 22p = (2p)2 ≡ 12 ≡ 1 (mod n)
となり、 n は Fermat test に合格。一方 n = 2p + 1 は 2⋅3 + 1 = 7 以上なので、 3 は n で割り切れない。よって:
2ℓ = 4 ≢ 1 なぜなら 3 ≢ 0 (mod n)
最後に ℓ = 2 は、明らかに 2 以上 4p + 4 未満の偶数。従って、定理4から n は素数だ。∎
以上は、 Hardy–Wright の定理103と実質同じ内容。あるいは、上記と同様に、仮定から 2p ≡ 1 (mod n) となり、従って 22p = 2n−1 ≡ 1 なので、定理3から直ちに同じ結論に至る。
(ii) については、次のような別証明（直接証明）も可能。奇数 n = 2p + 1 が 2p − 1 を割り切ると仮定する。もしも n が合成数だったら、 n は自分より小さい素因数 q を持つ。 n は奇数なので因子 2 を持たず、従って q は最小でも 3、最大でも n/3。よって:
q ≤ n/3 = (2p + 1)/3 < (2p + p)/3 = p ‥‥①
q は n の約数だが、仮定によりその n は 2p − 1 の約数なので、 q は 2p − 1 の約数†:
2p − 1 ≡ 0 つまり 2p ≡ 1 (mod q)
従って mod q での 2 の位数 e は、 p の約数。 p は素数なので、その約数を考えると e = 1 と e = p の二つの可能性しかない。前者は 21 ≡ 1 (mod q) を含意するが、 q は 3 以上なので、それは不可能。ゆえに e = p。
ところが Fermat の定理から、素数 q は 2q−1 ≡ 1 (mod q) を満たし、従って e は q − 1 の約数。 q − 1 の約数はもちろん q より小さいが、 q は p より小さいので（①）、 e は p より小さい。これは上記の e = p と矛盾。すなわち「n が合成数」ということは、不可能: n ≠ 1 なので、 n は素数。∎
† あるいは、同じことだが、仮定から 2p ≡ 1 (mod n) なので、 2p = nx + 1 と書くことができる（x: 整数）。もしも n = qr と分解されたなら、
2p = nx + 1 = (qr)x + 1 = q(rx) + 1
なので、 2p ≡ 1 (mod q)。
Caldwell は、微妙に違う直接証明を記している†。上と同様に n = 2p + 1 を合成数と仮定し、その最小の素因数を q とすると:
q2 ≤ n ‥‥②
上と同様に e = p は q − 1 の約数だから、 p ≤ q − 1 つまり p < q。このことと②から、
p2 < q2 ≤ n = 2p + 1
∴ p2 < 2p + 1 ≤ 2⋅3 + 1 = 7
となるが、 p ≥ 3 つまり p2 ≥ 9 だから、上の不等式は不可能。∎
不等式①を利用する方法は、平方・平方根などが絡まないという点で平明だが、②を使う方がエレガントかもしれない。
† https://t5k.org/notes/proofs/MerDiv2.html
リンク先で n = 2p + 1 ≥ q2 の代わりに (2p + 1) + 1 > q2 としているのは冗長なようだが、もしかすると、単に「より大きいかまたは等しい」の記号 ≥ の入力の手間を省くため（ASCII 文字の範囲で済むように）、そういう書き方をしたのかもしれない。実は②の不等号から、等号を除去できる――つまり奇数 n は、平方数 q2 にはなり得ない。なぜなら mod 4 において、 p ≡ ±1 なので n = 2p + 1 ≡ 3 だが、 q2 は q の偶奇に応じて ≡ 0 or 1。
性質 (i) が適用可能なら、 Mp が Mersenne 素数ではないこと、そして素因数 2p + 1 を持つことが、直ちに明らかになる。唯一の例外は p = 3 のときの M3 = 7。この 7 という数は確かに 2p + 1 = 7 で割り切れるけど、 7 は M3 自身なので、 M3 が素数でない証拠にはならない（7 はもちろん素数）。
それ以外の場合、つまり p が 3 より大きい「4k+3」型素数の場合には、
2p + 1 < Mp = 2p − 1 つまり 2p + 2 < 2p ‥‥③
なので、もし Mp が素数 2p + 1 で割り切れるなら、その約数 2p + 1 は Mp 自身ではない（もちろん 1 でもない）。よって Mp は素数ではない。
〔注〕 仮に p を整数として、その値が p = 4, 5, 6, ··· と 1 ずつ増えていくとすると、そのとき③の左辺は 10, 12, 14, ··· と 2 ずつしか増えないが、③の右辺は 16, 32, 64, ··· と倍々に増えるので、先へ行けば行くほど、ますます余裕で不等号 < が成り立つ。 3 より大きい任意の整数についてこの不等式が成り立つから、 3 より大きい任意の「4k+3」型素数 7, 11, 19, 23, 31, ··· についても、当然、同じ不等式が成り立つ。
かくして、実際に割り算するまでもなく、次のような数が素数でないことが（そしてその一つの素因子が）確定する:
M11 = 211 − 1 = 2047 ⇒ 23 で割り切れる
M23 = 223 − 1 = 8388607 ⇒ 47 で割り切れる
M83 = 283 − 1 = 9671406556917033397649407 ⇒ 167 で割り切れる
M131 = 2131 − 1 = 2722258935367507707706996859454145691647 ⇒ 263 で割り切れる
この方法で得られる素因子 q = 23 などは 2p + 1 の形を持つ。その p は「4k+3」型なので、 q は「8k+7」型。 8 の倍数より 7 大きい（言い換えると 8 の倍数より 1 小さい）。
『遊びの数論39』へ続く。
