前回に引き続き「超プーレ数」の話題です。今朝投稿されたばかりの次のYouTube動画に関する話題について、ブログでもより深く解説してみたいと思います。
前回紹介したときに現れた超プーレ数の例は
のように、平方因子を持たないものばかりでした。果たして、平方因子を持つような超プーレ数は存在するのでしょうか?
早速答えを言ってしまうと
がまさにその答えの一つになっています。
実際、3つの約数 に対応する合同式
が成り立つので、確かに超プーレ数です。
面白いことに、素因子に ヴィーフェリッヒ素数 が出てきます!
なんと超プーレ数とヴィーフェリッヒ素数(tsujimotterの大好きな素数の一つ)が関係するというのです!!
www.youtube.com
実は一般に「平方因子を持つようなプーレ数は、対応する素因子がヴィーフェリッヒ素数になる」という著しい性質があります。今日はそのことについて掘り下げてみたいと思います。
(目次)
1. ヴィーフェリッヒ素数の2乗は超プーレ数
まずは、冒頭で述べたことを一般化すると、次のような主張になります。
(証明)
はヴィーフェリッヒ素数の仮定より、 が成り立つ。両辺に をかけると
が成り立つ。ここで式 を繰り返し使うと
すなわち
が成り立つ。これは がプーレ数であることを意味する。
の約数は であるが、フェルマーの小定理より も成り立つので、式 とあわせて が超プーレ数であることが示された。
具体例を挙げたいのですが、現在知られているヴィーフェリッヒ素数は の2つだけです!
したがって、上の定理1より
がどちらも超プーレ数であるということがわかります。
実際
が成り立ちます。ぜひ確認してみてください。
・・・といって、確認するのはなかなか難しいでしょうから、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)
という箇所がありますが、これは を計算する部分ですね。Pythonは余り付きの冪乗を計算する関数が備わっています。
実行結果:
2^1194649 ≡ 2 (mod 1194649)
ぜひ手元のPCで計算してみてください。
2. プーレ数の平方因子
上の定理1の逆を考えたいと思います。つまり、素数の平方数 が超プーレ数(あるいはプーレ数)のときに、 がヴィーフェリッヒ素数になるかどうかです。
これは正しいのですが、ここではより強く、平方因子を持つようなプーレ数に対して、その平方因子の素因数がヴィーフェリッヒ素数になることを示したいと思います。
(定理2は定理3の系として示せます。)
(証明)
がプーレ数の仮定より
が成り立つ。ここで をとると
が成り立つ。
よって、 をオイラーのトーシェント関数とすると
が成り立つ。 はオイラーの定理である。
すなわち、 より、 はヴィーフェリッヒ素数であることが示された。
どうしても自力で証明できなくて、色々探した結果、Wikipedia "Fermat pseudoprime" の参考文献にあったPomeranceらの論文を見つけました。こんなに簡単に証明できたなんて・・・。
最後に、平方因子を持つプーレ数を紹介しましょう。Pomeranceらの論文によれば、該当する 以下の数は次の 6 つの数だけなのだそうです:
ちなみに、 については超プーレ数でもあるので、次が成り立ちます:
いやー、こんなところでヴィーフェリッヒ素数が顔を出すなんて、面白いですね!
3. 平方因子を持つプーレ数を作り出す
続いて平方因子を持つプーレ数をもっと作り出す方法を紹介します。
このとき,次の同値が成り立つ:
はプーレ数 は超プーレ数.
証明は最後に行いますが、ひとまず主張から言えることを確認しましょう。
がプーレ数なので、 としてはヴィーフェリッヒ素数です。
現段階でヴィーフェリッヒ素数 は2つしか知られていませんので、 の場合について がプーレ数となる素数 を探索できれば、超プーレ数 を探すことができます。
逆に という形の超プーレ数は がプーレ数のものに限られます。
リンク先の記事 によれば、2つのヴィーフェリッヒ素数に対応する の形をした超プーレ数は、2020年時点で すべて決定されています!! すごいですね!!
(次節でその理屈を説明します!!)
以下がそのリストです:
- ( は素数)型のすべての超プーレ数
- ( は素数)型のすべての超プーレ数
最後の二つは として126桁と146桁の素数が出てきていますね。
(定理4の証明)
の証明:
は超プーレ数より、定義から が成り立つ。これは がプーレ数であることを意味する。
の証明:
- を示す
フェルマーの小定理より であり、両辺 乗して
が成り立つ。一方、 はプーレ数より
も成り立つので、両方合わせて
が従う。よって に持ち上げると、 として
が成り立つ。
また、 はプーレ数より
も成り立つ。
ここから で次が成り立つ:
- を示す
フェルマーの小定理より
である。
一方で はプーレ数より
であり、 とって
であるが
であるから
である。
これを繰り返し適用すると
となり
が得られる。
と を用いると
が得られる。
以上により、 と が得られたので
が示された。すなわち、 はプーレ数である。
超プーレ数であることは、 の(合成数の)約数 がともにプーレ数であることから従う。
4. 2ᵖ - 1の素因数(p: ヴィーフェリッヒ素数)
話は変わって
を素因数分解してみましょう。 はもちろん、ヴィーフェリッヒ素数ですね。
前節にて、 がヴィーフェリッヒ素数、 がプーレ数であるときの がすべて決定できるという話をしました。実は、その鍵が上記の素因数分解にあるのです。
実際、素因数分解の結果はこうなります:
この下線を引いたところに注目してみましょう。これらの数に見覚えのある人はいませんか?
実は、前節の定理4の具体例の素数 がすべて出てきています!(ぜひ見比べてみてください。)
このことは次の定理5から分かります。
がプーレ数ならば, は を割り切る.
証明は後回しにするとして、主張の意味するところを確認しましょう。
定理5によって を固定したときに、 がプーレ数であれば が を割り切ることが言えました。一方で、定理4によって、 がヴィーフェリッヒ素数のとき「 がプーレ数」と「 が超プーレ数」は同値であることも分かりました。
以上を図にまとめるとこうなります:
つまり、 が超プーレ数であるならば、 が を割り切ることが言えるわけですね。このことは 型の超プーレ数を列挙するのに使えます。
対偶を取ると「 が を割り切らないならば、 は超プーレ数ではない」となります。
したがって、 が超プーレ数になりうる の候補は、 の素因数分解の結果に現れる素因子 だけに限られるということです。候補を有限個に絞り込むことができるわけです。
あとはこれらの候補の中から、実際に がプーレ数になるものを探せばよいわけですね。実際、それが下線部の素因数だったと言うわけです。
面白すぎません!?
(定理5の証明)
はプーレ数より
とると
である。一方、フェルマーの小定理より であるから
より
が成り立つ。 は奇素数より
であり、 が を割り切ることが示された。
それでは今日はこの辺で!
疑問点(何か情報をお持ちの方がいたらお知らせください)
ところで、参考文献の下記の記事内にある表のタイトルによれば
"Primes for which (and/or ) is a Poulet number" とあるので、 が超プーレ数ではなく単にプーレ数の場合も列挙できているような書き振りとなっています。
一方で、定理4で「 がプーレ数」と同値になるのは「 が超プーレ数」であり、「 が単にプーレ数」では十分ではありません。
あるいは何か別のアプローチで、「 がプーレ数であるような素数 」が列挙可能なのでしょうか? それとも誤植でしょうか?
私にはこの点が分からなかったので、何か知っている方がおられましたらお知らせください。
ちなみに下記2つのOEISでは、上記の記事を参照した上で、"Primes p such that at least one of 1093*p or 1093*p^2 is a Poulet number" がリストアップされています。やはり、 と のどちらもリストアップされているように見えるのですが、私の考えではそれは難しいように思います。どういうことなんでしょうか・・・。
A273471 - OEIS
A273472 - OEIS
参考文献
en.wikipedia.org
↑の「Equivalent definitions」の項を参照
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