最近こんなニュースが話題になっているようです。中国人の一般男性が「カーマイケル数」を導出する方法を再発見した、とのこと。
news.livedoor.com
一部引用すると
河南省の青年・余建春さんは短大卒でここ数年は、アルバイトで生計を立てている。そんな余さんは数学が大好きで、「カーマイケル数」を導く新たな計算法を発見したという。米ミズーリ大学の数学者は、「この計算方法で、正しいカーマイケル数が導けることを確認できれば、大発見」としている。中青在線が報じた。
とのことです。
CNNの記事もみつけました。どうやらこっちが元ネタのようです。
edition.cnn.com
実は、これらのニュースで登場する「カーマイケル数」が、前回投稿したばかりの「フェルマーの小定理」と非常に縁が深いのです。これはよいタイミングだなと思いましたので、今回はカーマイケル数についてご紹介したいと思います。
フェルマーの小定理,オイラーの定理(復習)
まず、フェルマーの小定理の復習です。フェルマーの小定理といっても、前回ご紹介した群論的な方です。
tsujimotter.hatenablog.com
ただし, は の単位元.
任意の有限群 に成り立つ一般的な定理です。この に具体的な群を代入すると、いろいろな定理が系として導かれます。
を素数として とすると、以下の数論的なフェルマーの小定理が導かれます。
もう少しだけ一般的に を正整数として について述べたものが、以下のオイラーの定理です。
ただし, はオイラーのトーシェント関数で, と互いに素な 以下の正整数の個数を表す.
ここまでが復習です。ここから本題に移ります。
カーマイケルの定理
次に、上のオイラーの定理をより洗練させた カーマイケルの定理 を紹介しましょう。
オイラーの定理では、べき乗の指数に を用いていましたが、これが最善ではありません。もっと小さい指数において、 のすべての元のべき乗が単位元になるような指数が存在するかもしれません。実際、そのような指数は存在することを
示したのが以下のカーマイケルの定理です。
ただし, は以下で定義される数論的関数.
上で定義される は、オイラーの定理の指数 よりもよい評価を与えます。しかし、それにしてもけったいな関数ですね。
この指数について調べるためには の具体的な構造に踏み込んで考える必要があります。
の群構造については,せきゅーんさんの以下の記事が大変参考になります。
integers.hatenablog.com
こちらの記事の結果を用いていきましょう。
まず が
と素因数分解できるとき、 は以下のような同型によって表現できます。
これは「中国剰余定理」と呼ばれる定理で、「 の合同式」は「 の素因子で表される合同式」によって分解できることを主張しています。中国剰余定理についてちゃんと触れたことはありませんが、いずれこのブログで紹介したいですね。
せきゅーんさんの記事では、この の形の群の、さらなる同型を与えています。 が か 奇素数か で場合分けをします。
のとき:
1番目のケースでは「自明な群」となり群の位数は です。2番目のケースでは位数 の巡回群、3番目のケースでは「位数 の巡回群」と「位数 の巡回群」の直積となります。
のとき:
が成り立ちます。形は難しそうですが、要するに位数 の巡回群です。
さて、以上の場合分けによって を巡回群の直積によって表すことができました。
たとえば、 としてみると
と素因数分解されるので
のように巡回群の直積で表せました。それぞれ、位数が となっています。
話をカーマイケルの定理に戻すと、それぞれの巡回群の位数を掛け合わせると
になるわけですが、これではオイラーの定理と同じになってしまいますね。実際
となって一致します。でも、これでは大きすぎるというわけです。
ここで掛け合わせずに、それぞれの巡回群の位数の 最小公倍数(LCM) を取ってあげましょう。これでも、すべての生成元が単位元に戻ることがわかります。すなわち「分解された巡回群のそれぞれの位数の最小公倍数」だけべき乗すると、すべての元が単位元になってしまうのです。
これこそがカーマイケルの定理における数論的関数 の正体だったわけですね。
先ほどの具体例をもう一度持ち出すと
における右辺の巡回群の位数はそれぞれ ですから
したがって、 の任意の元は 乗すると、単位元になることがわかりました(ほんまかいな)。
カーマイケル数
ようやく カーマイケル数 の話です。
フェルマーの小定理を使った素数判定法の1つで「フェルマーテスト」という手法があります。
を満たすかどうか,を判定するテストのことをフェルマーテストという.
が素数であれば、 と互いに素な任意の に対して、 はフェルマーテストを通ります。合成数でも、 によってはフェルマーテストを通るかもしれません。しかし、いくつかの異なる を試せば、必ずしも1にならないことは分かるでしょう。
一般に、フェルマーテストで試す の個数が増えれば、合成数を素数と誤判定する確率は下がります。このように、確率的に素数かどうか判定する方法を「確率的素数判定法」といいます。フェルマーテストは確率的素数判定法の1つです。
ところが、どんな に対してもフェルマーテストを通ってしまうような、タチの悪い合成数が存在します。このような「偽物の素数」のことを「カーマイケル数」といいます。
という数は、どんな に互いに素な をもってきても、フェルマーテストを通ってしまいます。つまり、 はカーマイケル数です。
がカーマイケル数であることを、カーマイケルの定理を用いて示すことができます。やってみましょう。
のように素因数分解されるので、中国剰余定理より
という同型が得られる。それぞれの群は
となるので、よって より、 となる。
したがってカーマイケルの定理により、 と互いに素な に対して
が成り立ちます。
よって
のように式変形できる。
すなわち、 は自分自身と互いに素なすべての に対してフェルマーテストを通過する、カーマイケル数であることが示せました。
一般に が を割り切るとき、 がカーマイケル数となります。
最後に、カーマイケル数を小さい順にいくつか列挙してみましょう。 を で割りきれることを確認してみてください。
カーマイケル数は、以下のオンライン整数列大辞典(OEIS)から持ってきました。
上の表を眺めながら、MathWorld におけるカーマイケル数の記事 を読んでみると、いくつか面白いことがわかります。
まず、カーマイケル数は無数にあることが知られているのだとか(予想:R. D. Carmichael (1910),証明:Alford-Granville-Pomerance (1994))。
また、カーマイケル数には判定法があります。
となっていて、それぞれの因子がすべて素数になっているときは、 はカーマイケル数になるのだそうです(証明:Korselt (1899), Ore (1988), Guy (1994))。
実際 のとき
となって、 はすべて素数ですね。
残念ながら、すべてのカーマイケル数がこの形式に該当するわけではないようなので、列挙には向かないのですが。
参考までに、カーマイケル自身の 1910 年の論文は以下でみることができます。MathWorld の記事によると、この論文で 15 個のカーマイケル数が例示されているそうなのですが、私にはよくわかりませんでした。読み解けた方がいましたら教えてください。
projecteuclid.org
おわりに
今日は巷で話題の「カーマイケル数」について、特に「カーマイケルの定理」と「 の群構造」の観点でご紹介しました。
前回の記事もそうだったのですが「群の構造」から「数論的な問題の解」が導けるのって、なんとも面白いですよね!
それでは、今日はこの辺で!