プーレ数の平方因子とヴィーフェリッヒ素数

前回に引き続き「超プーレ数」の話題です。今朝投稿されたばかりの次のYouTube動画に関する話題について、ブログでもより深く解説してみたいと思います。

www.youtube.com

前回紹介したときに現れた超プーレ数の例は

$341 = 11 \times 31$

$1387 = 19 \times 73$

$2047 = 23 \times 89$

$2701 = 37 \times 73$

$3277 = 29 \times 113$

のように、平方因子を持たないものばかりでした。果たして、平方因子を持つような超プーレ数は存在するのでしょうか？

早速答えを言ってしまうと

$1194649 = 1093^2$

がまさにその答えの一つになっています。

実際、３つの約数 $1, \; 1093, \; 1194649$ に対応する合同式

$2^{1194649} \equiv 2 \pmod{1194649}$

$2^{1093} \equiv 2 \pmod{1093}$

$2^{1} \equiv 2 \pmod{1}$

が成り立つので、確かに超プーレ数です。

面白いことに、素因子にヴィーフェリッヒ素数が出てきます！

なんと超プーレ数とヴィーフェリッヒ素数（tsujimotterの大好きな素数の一つ）が関係するというのです！！
www.youtube.com

実は一般に「平方因子を持つようなプーレ数は、対応する素因子がヴィーフェリッヒ素数になる」という著しい性質があります。今日はそのことについて掘り下げてみたいと思います。

（目次）

1. ヴィーフェリッヒ素数の2乗は超プーレ数

2. プーレ数の平方因子

3. 平方因子を持つプーレ数を作り出す

4. 2ᵖ - 1の素因数（p: ヴィーフェリッヒ素数）

疑問点（何か情報をお持ちの方がいたらお知らせください）

参考文献

1. ヴィーフェリッヒ素数の2乗は超プーレ数

まずは、冒頭で述べたことを一般化すると、次のような主張になります。

定理１

$p$ をヴィーフェリッヒ素数とする．このとき， $p^2$ は超プーレ数．

（証明）
$p$ はヴィーフェリッヒ素数の仮定より、 $2^{p-1} \equiv 1 \pmod{p^2}$ が成り立つ。両辺に $2$ をかけると

$2^{p} \equiv 2 \pmod{p^2} \tag{1}$

が成り立つ。ここで式 $(1)$ を繰り返し使うと

$2^{p^2} \equiv (2^p)^p \equiv 2^p \equiv 2 \pmod{p^2}$

すなわち

$2^{p^2} \equiv 2 \pmod{p^2} \tag{2}$

が成り立つ。これは $p^2$ がプーレ数であることを意味する。

$p^2$ の約数は $1, \; p, \; p^2$ であるが、フェルマーの小定理より $2^p \equiv 2 \pmod{p}$ も成り立つので、式 $(2)$ とあわせて $p^2$ が超プーレ数であることが示された。

（証明終わり）

具体例を挙げたいのですが、現在知られているヴィーフェリッヒ素数は $p = 1093, \; 3511$ の２つだけです！

したがって、上の定理１より

$1093^2 = 1194649$

$3511^2 = 12327121$

がどちらも超プーレ数であるということがわかります。

実際

$2^{1194649} \equiv 2 \pmod{1194649}$

$2^{12327121} \equiv 2 \pmod{12327121}$

が成り立ちます。ぜひ確認してみてください。

・・・といって、確認するのはなかなか難しいでしょうから、Pythonだと次のように確認できます。

a = 2
m = 1093**2
x = pow(a, m, m)  #(a ** m) % m
print( str(a) + "^" + str(m) + " ≡ " + str(x) + "  (mod "+str(m)+")"

ここで

pow(a, m, m)

という箇所がありますが、これは $a^m \bmod{m}$ を計算する部分ですね。Pythonは余り付きの冪乗を計算する関数が備わっています。

実行結果：

2^1194649 ≡ 2  (mod 1194649)

ぜひ手元のPCで計算してみてください。

2. プーレ数の平方因子

上の定理１の逆を考えたいと思います。つまり、素数の平方数 $p^2$ が超プーレ数（あるいはプーレ数）のときに、 $p$ がヴィーフェリッヒ素数になるかどうかです。

定理２

$p^2$ （ $p$ は奇素数）がプーレ数であるとする．このとき， $p$ はヴィーフェリッヒ素数．

これは正しいのですが、ここではより強く、平方因子を持つようなプーレ数に対して、その平方因子の素因数がヴィーフェリッヒ素数になることを示したいと思います。
（定理２は定理３の系として示せます。）

定理３

$m = p^2 m'$ （ $p$ は奇素数）がプーレ数であるとする．このとき， $p$ はヴィーフェリッヒ素数．

（証明）
$m$ がプーレ数の仮定より

$2^{m} \equiv 2 \pmod{m}$

が成り立つ。ここで $\bmod{p^2}$ をとると

$2^{m} \equiv 2 \pmod{p^2} \tag{3}$

が成り立つ。

よって、 $\varphi$ をオイラーのトーシェント関数とすると

$\begin{align} 2^{p-1} &\equiv (2^m)^{p-1} \\ &\equiv 2^{m(p-1)} \\ &\equiv 2^{m'p\cdot p(p-1)} \\ &\equiv 2^{m'p\cdot \varphi(p^2)} \\ &\equiv (2^{\varphi(p^2)})^{m'p} \\ &\equiv 1 \pmod{p^2} \end{align}$

が成り立つ。 $2^{\varphi(p^2)} \equiv 1 \pmod{p^2}$ はオイラーの定理である。

すなわち、 $2^{p-1} \equiv 1 \pmod{p^2}$ より、 $p$ はヴィーフェリッヒ素数であることが示された。

（証明終わり）

ところでこの定理、あっさり証明していますが、この証明が思いつかなくて３日ぐらい悩んでおりました。
どうしても自力で証明できなくて、色々探した結果、Wikipedia "Fermat pseudoprime" の参考文献にあったPomeranceらの論文を見つけました。こんなに簡単に証明できたなんて・・・。

最後に、平方因子を持つプーレ数を紹介しましょう。Pomeranceらの論文によれば、該当する $25\times 10^9$ 以下の数は次の 6 つの数だけなのだそうです：

$\begin{align} 1194649 &= \mathbf{1093^2} \\ 12327121 &= \mathbf{3511^2} \\ 3914864773 &= 29 \times 113 \times \mathbf{1093^2} \\ 5654273717 &= \mathbf{1093^2} \times 4733 \\ 6523978189 &= 43 \times 127 \times \mathbf{1093^2} \\ 22178658685 &= 5 \times 47 \times 79 \times \mathbf{1093^2} \end{align}$

ちなみに、 $5654273717 = 1093^2 \times 4733$ については超プーレ数でもあるので、次が成り立ちます：

$2^{5654273717} \equiv 2 \pmod{5654273717}$

$2^{5173169} \equiv 2 \pmod{5173169}$

$2^{1194649} \equiv 2 \pmod{1194649}$

$2^{1093} \equiv 2 \pmod{1093}$

$2^{4733} \equiv 2 \pmod{4733}$

$2^{1} \equiv 2 \pmod{1}$

いやー、こんなところでヴィーフェリッヒ素数が顔を出すなんて、面白いですね！

3. 平方因子を持つプーレ数を作り出す

続いて平方因子を持つプーレ数をもっと作り出す方法を紹介します。

定理４

$p, q$ を相異なる奇素数とする．また， $p^2$ はプーレ数とする．

このとき，次の同値が成り立つ：
$pq$ はプーレ数 $\;\; \Longleftrightarrow \;\;$ $p^2 q$ は超プーレ数．

証明は最後に行いますが、ひとまず主張から言えることを確認しましょう。

$p^2$ がプーレ数なので、 $p$ としてはヴィーフェリッヒ素数です。

現段階でヴィーフェリッヒ素数 $1093, 3511$ は２つしか知られていませんので、 $p = 1093, 3511$ の場合について $pq$ がプーレ数となる素数 $q$ を探索できれば、超プーレ数 $p^2 q$ を探すことができます。

逆に $p^2q$ という形の超プーレ数は $pq$ がプーレ数のものに限られます。

リンク先の記事によれば、2つのヴィーフェリッヒ素数に対応する $1093^2q, \; 3511^2 q$ の形をした超プーレ数は、2020年時点ですべて決定されています！！　すごいですね！！
（次節でその理屈を説明します！！）

以下がそのリストです：

$1093^2 q$ （ $q$ は素数）型のすべての超プーレ数

$\begin{align} 1093^2 &\times 4733, \\ 1093^2 &\times 21841, \\ 1093^2 &\times 503413, \\ 1093^2 &\times 1948129, \\ 1093^2 &\times 112901153, \\ 1093^2 &\times 23140471537, \\ 1093^2 &\times 467811806281, \\ 1093^2 &\times 4093204977277417, \\ 1093^2 &\times 8861085190774909, \\ 1093^2 &\times 556338525912325157, \\ 1093^2 &\times 86977595801949844993, \\ 1093^2 &\times 275700717951546566946854497, \\ 1093^2 &\times 3194753987813988499397428643895659569 \end{align}$

$3511^2 q$ （ $q$ は素数）型のすべての超プーレ数

$\begin{align} 3511^2 &\times 10531, \\ 3511^2 &\times 1024921, \\ 3511^2 &\times 1969111, \\ 3511^2 &\times 4633201, \\ 3511^2 &\times 409251961, \\ 3511^2 &\times 21497866557571, \\ 3511^2 &\times 194900834792501371, \\ 3511^2 &\times 4242734772486358591, \\ 3511^2 &\times 85488365519409100951, \\ 3511^2 &\times 255375215316698521591, \\ 3511^2 &\times 1439538040790707946401, \\ 3511^2 &\times 5302306226370307681801, \\ 3511^2 &\times 2728334536034592865339299805712535332071, \\ 3511^2 &\times 1514527568177848809210967221069334182785475908756709327091, \\ 3511^2 &\times 559791068131697034376217936561708451475280017605178661418575551, \\ 3511^2 &\times 656640320787712008058581244241126148909602076298405712103045387152988908318802087128873347971063698441918022286945981375193401, \\ 3511^2 &\times 25006596829256741460214169653933852849128490077459890197421900490545433220443136638425782879171530372521984642165350019685875922245867185516694881 \end{align}$

最後の二つは $q$ として126桁と146桁の素数が出てきていますね。

（定理４の証明）
$\Longleftarrow$ の証明：
$p^2 q$ は超プーレ数より、定義から $2^{pq} \equiv 2 \pmod{pq}$ が成り立つ。これは $pq$ がプーレ数であることを意味する。

$\Longrightarrow$ の証明：

$2^{p^2 q} \equiv 2 \pmod{p^2}$ を示す

フェルマーの小定理より $2^p \equiv 2 \pmod{p}$ であり、両辺 $q$ 乗して

$2^{pq} \equiv 2^q \pmod{p}$

が成り立つ。一方、 $pq$ はプーレ数より

$2^{pq} \equiv 2 \pmod{p}$

も成り立つので、両方合わせて

$2^{q} \equiv 2 \pmod{p}$

が従う。よって $\bmod{p^2}$ に持ち上げると、 $0\leq k < p$ として

$2^{q} \equiv 2 + kp \pmod{p^2}$

が成り立つ。

また、 $p^2$ はプーレ数より

$2^{p^2} \equiv 2 \pmod{p^2}$

も成り立つ。

ここから $\bmod{p^2}$ で次が成り立つ：

$\begin{align} 2^{p^2q} &\equiv (2^q)^{p^2} \\ &\equiv (2 + kp)^{p^2} \\ &\equiv 2^{p^2} + p^2 2^{p^2-1} (kp)^1 + (\text{2次以上}) \\ &\equiv 2^{p^2} \\ &\equiv 2 \pmod{p^2} \end{align}$

$2^{p^2 q} \equiv 2 \pmod{q}$ を示す

フェルマーの小定理より

$2^q \equiv 2 \pmod{q}$

である。

一方で $pq$ はプーレ数より

$2^{pq} \equiv 2 \pmod{pq}$

であり、 $\bmod{q}$ とって

$2^{pq} \equiv 2 \pmod{q}$

であるが

$2^{pq} \equiv (2^q)^p \equiv 2^p \pmod{q}$

であるから

$2^{p} \equiv 2 \pmod{q}$

である。

これを繰り返し適用すると

$2^{p^2} \equiv (2^p)^p \equiv 2^p \equiv 2 \pmod{q}$

となり

$2^{p^2} \equiv 2 \pmod{q}$

が得られる。

$2^q \equiv 2 \pmod{q}$ と $2^{p^2} \equiv 2 \pmod{q}$ を用いると

$2^{p^2q} \equiv (2^{p^2})^q \equiv 2^q \equiv 2 \pmod{q}$

が得られる。

以上により、 $p^2 \mid 2^{p^2q} - 2$ と $q \mid 2^{p^2q} - 2$ が得られたので

$2^{p^2 q} \equiv 2 \pmod{p^2 q}$

が示された。すなわち、 $p^2 q$ はプーレ数である。

超プーレ数であることは、 $p^2q$ の（合成数の）約数 $pq, p^2$ がともにプーレ数であることから従う。

（定理４の証明終わり）

4. 2ᵖ - 1の素因数（p: ヴィーフェリッヒ素数）

話は変わって

$2^{1092} - 1$

$2^{3510} - 1$

を素因数分解してみましょう。 $1092, 3510$ はもちろん、ヴィーフェリッヒ素数 $-1$ ですね。

前節にて、 $p$ がヴィーフェリッヒ素数、 $pq$ がプーレ数であるときの $q$ がすべて決定できるという話をしました。実は、その鍵が上記の素因数分解にあるのです。

実際、素因数分解の結果はこうなります：

$\begin{align} 2^{1092} - 1 &= 3^2 \times 5 \times 7^2 \times 13^2 \times 29 \times 43 \times 53 \times 79 \times 113 \times 127 \times 157 \times 313 \\ & \times 337 \times 547 \times 911 \times 1093^2 \times 1249 \times 1429 \times 1613 \times 2731 \times 3121 \\ & \times \underline{4733} \times 5419 \times 8191 \times 14449 \times \underline{21841} \times 121369 \times 224771 \times \underline{503413} \\ & \times 1210483 \times \underline{1948129} \times 22366891 \times 108749551 \times \underline{112901153} \\ & \times 25829691707 \times \underline{23140471537} \times 105310750819 \times \underline{467811806281} \\ & \times \underline{4093204977277417} \times \underline{8861085190774909} \times \underline{556338525912325157} \\ & \times \underline{86977595801949844993} \times \underline{275700717951546566946854497} \\ & \times 292653113147157205779127526827 \\ & \times \underline{3194753987813988499397428643895659569} \end{align}$

$\begin{align} 2^{3510} - 1 &= 3^4 \times 7 \times 11 \times 19 \times 31 \times 73 \times 79 \times 131 \times 151 \times 271 \times 331 \times 631 \\ &\times 811 \times 937 \times 1171 \times 2731 \times 3511^2 \times 6553 \times 8191 \times \underline{10531} \times 15121 \\ &\times 23311 \times 65521 \times 86113 \times 87211 \times 107251 \times 121369 \times 262657 \\ & \times 348031 \times 409891 \times 446473 \times \underline{1024921} \times \underline{1969111} \times \underline{4633201} \\ & \times 7623851 \times 18837001 \times 22366891 \times 29121769 \times \underline{409251961} \\ & \times 2400314671 \times 7830118297 \times 26959262851 \times \underline{21497866557571} \\ & \times 49971617830801 \times 145295143558111 \times 385838642647891 \\ & \times 571890896913727 \times 93715008807883087 \times \underline{194900834792501371} \\ & \times 339175003117573351 \times \underline{4242734772486358591} \times \underline{85488365519409100951} \\ & \times 150832426800173710177 \times \underline{255375215316698521591} \\ & \times \underline{1439538040790707946401} \times \underline{5302306226370307681801} \\ & \times 571403921126076957182161 \times 4247713303224552237738169 \\ & \times 43725552532343303477113703251 \\ & \times 134304196845099262572814573351 \\ & \times \underline{2728334536034592865339299805712535332071} \\ & \times 4897406518564079146139572699835240681611 \\ & \times 24841125429051585062538961751269988364169 \\ & \times \underline{1514527568177848809210967221069334182785475908756709327091} \\ & \times \underline{559791068131697034376217936561708451475280017605178661418575551} \\ & \times \underline{656640320787712008058581244241126148909602076298405712103045387152988908318802087128873347971063698441918022286945981375193401} \\ & \times \underline{25006596829256741460214169653933852849128490077459890197421900490545433220443136638425782879171530372521984642165350019685875922245867185516694881} \end{align}$

この下線を引いたところに注目してみましょう。これらの数に見覚えのある人はいませんか？

実は、前節の定理４の具体例の素数 $q$ がすべて出てきています！（ぜひ見比べてみてください。）

このことは次の定理５から分かります。

定理５

$p, q$ を相異なる奇素数とする．
$pq$ がプーレ数ならば， $q$ は $2^{p-1} - 1$ を割り切る．

証明は後回しにするとして、主張の意味するところを確認しましょう。

定理５によって $p$ を固定したときに、 $pq$ がプーレ数であれば $q$ が $2^{p-1} - 1$ を割り切ることが言えました。一方で、定理４によって、 $p$ がヴィーフェリッヒ素数のとき「 $pq$ がプーレ数」と「 $p^2q$ が超プーレ数」は同値であることも分かりました。

以上を図にまとめるとこうなります：

つまり、 $p^2 q$ が超プーレ数であるならば、 $q$ が $2^{p-1} - 1$ を割り切ることが言えるわけですね。このことは $p^2 q$ 型の超プーレ数を列挙するのに使えます。

対偶を取ると「 $q$ が $2^{p-1} - 1$ を割り切らないならば、 $p^2 q$ は超プーレ数ではない」となります。

したがって、 $p^2 q$ が超プーレ数になりうる $q$ の候補は、 $2^{p-1} - 1$ の素因数分解の結果に現れる素因子 $q$ だけに限られるということです。候補を有限個に絞り込むことができるわけです。

あとはこれらの候補の中から、実際に $pq$ がプーレ数になるものを探せばよいわけですね。実際、それが下線部の素因数だったと言うわけです。

面白すぎません！？

（定理５の証明）
$pq$ はプーレ数より

$2^{pq} \equiv 2 \pmod{pq}$

$\bmod{q}$ とると

$2^{pq} \equiv 2 \pmod{q}$

である。一方、フェルマーの小定理より $2^q \equiv 2 \pmod{q}$ であるから

$2 \equiv 2^{pq} \equiv (2^{q})^p \equiv 2^p \pmod{q}$

より

$2^p \equiv 2 \pmod{q}$

が成り立つ。 $q$ は奇素数より

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

であり、 $q$ が $2^{p-1} - 1$ を割り切ることが示された。

（定理５の証明終わり）

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

疑問点（何か情報をお持ちの方がいたらお知らせください）

ところで、参考文献の下記の記事内にある表のタイトルによれば
"Primes $q$ for which $pq$ (and/or $p^2q$ ) is a Poulet number" とあるので、 $p^2 q$ が超プーレ数ではなく単にプーレ数の場合も列挙できているような書き振りとなっています。

www.numericana.com

一方で、定理４で「 $pq$ がプーレ数」と同値になるのは「 $p^2 q$ が超プーレ数」であり、「 $p^2q$ が単にプーレ数」では十分ではありません。

あるいは何か別のアプローチで、「 $p^2q$ がプーレ数であるような素数 $q$ 」が列挙可能なのでしょうか？　それとも誤植でしょうか？
私にはこの点が分からなかったので、何か知っている方がおられましたらお知らせください。

ちなみに下記2つのOEISでは、上記の記事を参照した上で、"Primes p such that at least one of 1093*p or 1093*p^2 is a Poulet number" がリストアップされています。やはり、 $pq$ と $p^2 q$ のどちらもリストアップされているように見えるのですが、私の考えではそれは難しいように思います。どういうことなんでしょうか・・・。
A273471 - OEIS
A273472 - OEIS

参考文献

素数の世界―その探索と発見

作者:Paulo Ribenboim
共立出版

Amazon

en.wikipedia.org
↑の「Equivalent definitions」の項を参照

oeis.org

Pomerance, Carl; Selfridge, John L.; Wagstaff, Samuel S. Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.
http://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf