tsujimotterのノートブック

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

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

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


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

 341 = 11 \times 31
 1387 = 19 \times 73
 2047 = 23 \times 89
 2701 = 37 \times 73
 3277 = 29 \times 113

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




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

 1194649 = 1093^2

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

実際、3つの約数  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乗は超プーレ数

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

定理1
 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 の2つだけです!

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

 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. プーレ数の平方因子

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


定理2
 p^2 p は奇素数)がプーレ数であるとする.このとき, p はヴィーフェリッヒ素数.


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


定理3
 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 はヴィーフェリッヒ素数であることが示された。

(証明終わり)

ところでこの定理、あっさり証明していますが、この証明が思いつかなくて3日ぐらい悩んでおりました。
どうしても自力で証明できなくて、色々探した結果、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. 平方因子を持つプーレ数を作り出す

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

定理4
 p, q を相異なる奇素数とする.また, p^2 はプーレ数とする.

このとき,次の同値が成り立つ:
 pq はプーレ数  \;\; \Longleftrightarrow \;\;  p^2 q は超プーレ数.

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


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

現段階でヴィーフェリッヒ素数  1093, 3511 は2つしか知られていませんので、 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桁の素数が出てきていますね。



(定理4の証明)
 \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の証明終わり)


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*}


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

実は、前節の定理4の具体例の素数  q がすべて出てきています!(ぜひ見比べてみてください。)


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

定理5
 p, q を相異なる奇素数とする.
 pq がプーレ数ならば, q 2^{p-1} - 1 を割り切る.

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


定理5によって  p を固定したときに、 pq がプーレ数であれば  q 2^{p-1} - 1 を割り切ることが言えました。一方で、定理4によって、 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 がプーレ数になるものを探せばよいわけですね。実際、それが下線部の素因数だったと言うわけです。


面白すぎません!?


(定理5の証明)
 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 を割り切ることが示された。

(定理5の証明終わり)


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


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

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

www.numericana.com


一方で、定理4で「 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


参考文献


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


www.numericana.com