Fermatテスト
Fermatテストと呼ばれるお手軽な素数判定法があります。まず、Fermatの小定理を思い出しましょう。
この定理を使えば、と互いに素な整数に対して、がを法としてと合同でなければは合成数であると判定することができます。
例えば、なので、は合成数であると判定できます。これが、Fermatテストです。
しかしながら、Fermatテストには欠陥があって、
は真なのですが、
とは必ずしも言えないという点です。実際、WolframAlphaなどで計算してみると分かりますが、合成数について
が成り立ちます。このような合成数のことを擬素数と呼びます。素数になりすましているというわけですね。擬素数であっても、としてはと互いに素な整数であれば何でもよいので、を取り替えることによって合成数であることが証明できる場合があります。
実際、
なので、は合成数であると判定できます。
Carmichaelの関数
Fermatの小定理を拡張したのがEulerの定理でした:
そういえば、このブログでは多分これらの定理の証明をしたことはないのですが、Lagrangeの定理から自明です(Q.E.D.)。さて、今回はEulerの定理の精密化であるCarmichaelの定理を紹介します。
, . 整数に対して、.
奇素数と整数に対して、.
整数に対するはを素因数分解とするときにによって定義する。
次は、素因数分解して考えれば、定義より明らかです:
トーシェント関数の代わりに関数でも同様の定理が成立するというのがCarmichaelの定理です:
証明. まず、が素数冪であるときに確認する。のときは自明。のときは、奇数に対して、
よって、に対して、が奇数であれば
が成り立つことはに関する帰納法で証明できる。が奇素数である場合は、正整数に対して なので、Eulerの定理より が成り立つ。
一般のについては、と素因数分解される場合、であることから、の任意の素因数に対して
が成り立つことがわかる(はと互いに素な整数)。よって、が成立する。 Q.E.D.
定義から明らかになので、Carmichaelの定理はEulerの定理の精密化であることがわかります。しかし、重要なのは単なる精密化ということではなく、optimalな精密化であるということです。
証明. とする。からが従い、がわかる*1。同様に、なので、が示された。よって、の最小性から、後はを示せばよい。これが とから従うことはとが互いに素であることからわかる。 Q.E.D.
optimalな精密化とは、次の定理が成り立つことです:
証明. をの素因数分解とする(は奇素数)。をを法とする原始根とする。原始根の存在は(Z/nZ)*の群構造 - INTEGERSで証明している。このとき、中国式剰余定理によって、と互いに素な整数であって
が成り立つようなものが存在する。上記記事の1.2において、としても同じ合同式が成立するので*2、
が成り立つ。また、の取り方から
が成り立つ。あとは、関数の定義と補題からが従う。 Q.E.D.
証明. であれば、Carmichaelの定理より がと互いに素な任意の整数に対して成立する。次に、と互いに素な任意の整数に対して合同式 が成り立つと仮定する。すると、指数の定義よりが成り立つ。定理より、なるが存在するので、が従う。 Q.E.D.
素数に対しては なので、この系はFermatの小定理と両立的であることが確認できます。
Carmichael数
冒頭のFermatテストの解説において、はに対しては擬素数として振る舞うが に対しては合成数と判定されるという現象を見ました。或るに対して擬素数であるような合成数について、必ず別のに対しては合成数と判定されるということが言えればFermatテストは正確な素数判定法となるのですが、事実はそうではありません。どんなをとってきても擬素数となってしまう、絶対擬素数と呼ばれる合成数達が存在するのです。
まずわかることとして、二つの素数の積であるような絶対擬素数は存在しません。理由: なる二つの素数を考える。このとき、
は整数ではないため、がわかる。一方、であれば でなければならない。も明らか。
一方、三つの素数の積であるような合成数を考えると絶対擬素数が出現し始めます。Carmichaelの論文には
の四つが書かれています。実際、
なので、これらの数は絶対擬素数です。
また、正整数に対して が全て素数であるような場合については、は絶対擬素数です。実際、
となっています。この形の最小の絶対擬素数はの場合のです。ちなみに、絶対擬素数かつラマヌジャンのタクシー数であるは素数大富豪においてラマヌジャン革命という特殊能力を有しています*3。
絶対擬素数は素因数を三つしか持たないというわけではありません。
などは
なので、絶対擬素数です。
絶対擬素数を小さい順に100個列挙すると次のようになります:
もし、絶対擬素数が有限個しかなければ、それらをあらかじめ排除しておくことによってFermatテストは正確な素数判定法になれます。が、実は絶対擬素数は無数に存在します。
W. R. Alford, A. Granville, C. Pomerance, There are Infinitely Many Carmichael Numbers, Annals of Mathematics. 139 (1994), 703–722.
数の世界は実に奥が深いです。
最後にKorseltによる絶対擬素数の判定法を紹介してこの記事を終えます。Korseltはこの定理をCarmichaelより10年以上前に証明していましたが、絶対擬素数の具体例を見つけることはできなかったため、Carmichael数という名前になってしまいました。cf. スティグラーの法則。
証明. この記事では既に系という形で絶対擬素数の判定法を証明しているので、示すべきことは「絶対擬素数は必ず無平方である」ということのみである。を絶対擬素数とし、という分解を持つと仮定する(は素数、は以上の整数、はと互いに素な整数)。中国式剰余定理によって
が成り立つような整数が存在し、それはと互いに素である。すると、が絶対擬素数であるという仮定から が成り立つ。これは
を導くが、一方で
なので矛盾が生じる。よって、は無平方である。 Q.E.D.
この記事内容はブログ仲間tsujimotter氏による記事
とかなりの部分が重複してしまっています。ですが、関数は今後も扱う予定なので、self-containedを目指す当ブログの性格上、私も記事にすることにしました。
*1:割り算の原理を使って最小性から余りがとなるよくやるやつ。
*2:ただし、については直接確認して、帰納法をから始める。
*3:みうらさんの記事 togetter.com も参考になります。ちなみに、「以外の絶対擬素数を素数として出した場合は、素因数の数だけペナルティとして山札から手札にカードを追加するが、出したカードはそのまま場に残してゲームを続行する」という新ルールを思いついたことをここに報告致します。
*4:GranvilleさんとPomeranceさんは特に尊敬する数学者です。このブログのヘッダーの文章はPomeranceさんのものです(注: 昔のヘッダー)。この定理は彼の研究の中でもかなり大きい仕事と言えるでしょう。