tsujimotterのノートブック

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

巷で話題のカーマイケル数・カーマイケルの定理について

最近こんなニュースが話題になっているようです。中国人の一般男性が「カーマイケル数」を導出する方法を再発見した、とのこと。
news.livedoor.com

一部引用すると

河南省の青年・余建春さんは短大卒でここ数年は、アルバイトで生計を立てている。そんな余さんは数学が大好きで、「カーマイケル数」を導く新たな計算法を発見したという。米ミズーリ大学の数学者は、「この計算方法で、正しいカーマイケル数が導けることを確認できれば、大発見」としている。中青在線が報じた。

とのことです。

CNNの記事もみつけました。どうやらこっちが元ネタのようです。
edition.cnn.com


実は、これらのニュースで登場する「カーマイケル数」が、前回投稿したばかりの「フェルマーの小定理」と非常に縁が深いのです。これはよいタイミングだなと思いましたので、今回はカーマイケル数についてご紹介したいと思います。

フェルマーの小定理,オイラーの定理(復習)

まず、フェルマーの小定理の復習です。フェルマーの小定理といっても、前回ご紹介した群論的な方です。
tsujimotter.hatenablog.com


(群論的な)フェルマーの小定理
 G を(有限の要素をもつ)群としたとき, g\in G に対して,以下が成り立つ.
 g^{\#G} = e

ただし, e G の単位元.


任意の有限群  G に成り立つ一般的な定理です。この  G に具体的な群を代入すると、いろいろな定理が系として導かれます。


 p を素数として  G = (\mathbb{Z}/p\mathbb{Z})^{\times} とすると、以下の数論的なフェルマーの小定理が導かれます。

(数論的な)フェルマーの小定理
 p を素数としたとき, g\in (\mathbb{Z}/p\mathbb{Z})^{\times} に対して,以下が成り立つ.
 g^{p-1} = \overline{1}


もう少しだけ一般的に  m を正整数として  G = (\mathbb{Z}/m\mathbb{Z})^{\times} について述べたものが、以下のオイラーの定理です。

オイラーの定理
 m を正整数としたとき, g\in (\mathbb{Z}/m\mathbb{Z})^{\times} に対して,以下が成り立つ.
 g^{\varphi(m)} = \overline{1}

ただし, \varphi(m) はオイラーのトーシェント関数で, m と互いに素な  m 以下の正整数の個数を表す.


ここまでが復習です。ここから本題に移ります。

カーマイケルの定理

次に、上のオイラーの定理をより洗練させた カーマイケルの定理 を紹介しましょう。

オイラーの定理では、べき乗の指数に  \varphi(m) を用いていましたが、これが最善ではありません。もっと小さい指数において、 (\mathbb{Z}/p\mathbb{Z})^\times のすべての元のべき乗が単位元になるような指数が存在するかもしれません。実際、そのような指数は存在することを
示したのが以下のカーマイケルの定理です。

カーマイケルの定理
 m を正整数としたとき, g\in (\mathbb{Z}/m\mathbb{Z})^{\times} に対して,以下が成り立つ.
 g^{\lambda(m)} = \overline{1}


ただし, \lambda(m) は以下で定義される数論的関数.

 \lambda(m) \; := \; \begin{cases} 1 & m = 2^{e}, \; e = 1 \\ 
 2 & m = 2^{e}, \; e = 2 \\ 
 \text{LCM}\left(2, 2^{e-2}\right) & m = 2^{e}, \; e \geq 3 \\ 
 p^{e-1} (p-1) & m=p^e, \; p >= 3  \\ 
 \text{LCM}\left(\lambda(2^{e_2}), \lambda(3^{e_3}), \lambda(5^{e_5}), \cdots \right) & m=2^{e_2} \cdot 3^{e_3} \cdot 5^{e_5} \cdots  \end{cases}


上で定義される  \lambda(m) は、オイラーの定理の指数  \varphi(m) よりもよい評価を与えます。しかし、それにしてもけったいな関数ですね。


この指数について調べるためには  G = (\mathbb{Z}/m\mathbb{Z})^\times の具体的な構造に踏み込んで考える必要があります。


 G = (\mathbb{Z}/m\mathbb{Z})^\times の群構造については,せきゅーんさんの以下の記事が大変参考になります。
integers.hatenablog.com


こちらの記事の結果を用いていきましょう。

まず  m

 m = 2^{e_2} \cdot 3^{e_3} \cdot 5^{e_5} \cdot \; \cdots \cdot p^{e_p} \cdot \; \cdots

と素因数分解できるとき、(\mathbb{Z}/m\mathbb{Z})^\times は以下のような同型によって表現できます。

 (\mathbb{Z}/m\mathbb{Z})^\times \; \simeq \; (\mathbb{Z}/2^{e_2}\mathbb{Z})^\times \times (\mathbb{Z}/3^{e_3}\mathbb{Z})^\times \times (\mathbb{Z}/5^{e_5}\mathbb{Z})^\times \times \cdots \times (\mathbb{Z}/p^{e_p}\mathbb{Z})^\times \times \cdots

これは「中国剰余定理」と呼ばれる定理で、「 \mod{m} の合同式」は「 m の素因子で表される合同式」によって分解できることを主張しています。中国剰余定理についてちゃんと触れたことはありませんが、いずれこのブログで紹介したいですね。


せきゅーんさんの記事では、この  (\mathbb{Z}/p^{e_p}\mathbb{Z})^\times の形の群の、さらなる同型を与えています。 p 2 か 奇素数か で場合分けをします。


 p = 2 のとき:

 (\mathbb{Z}/2^{e}\mathbb{Z})^\times \simeq \begin{cases} \{e\} & (e = 1) \\ 
 \mathbb{Z}/2\mathbb{Z} & (e = 2) \\ 
 \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{e-2}\mathbb{Z} & (e \geq 3) \end{cases}

1番目のケースでは「自明な群」となり群の位数は  1 です。2番目のケースでは位数  2 の巡回群、3番目のケースでは「位数  2 の巡回群」と「位数  2^{e-2} の巡回群」の直積となります。


 p \geq 3 のとき:

 (\mathbb{Z}/p^{e}\mathbb{Z})^\times \; \simeq \; \mathbb{Z}/\left(p^{e-1} (p-1)\right)\mathbb{Z}

が成り立ちます。形は難しそうですが、要するに位数  p^{e-1} (p-1) の巡回群です。



さて、以上の場合分けによって  (\mathbb{Z}/m\mathbb{Z})^\times を巡回群の直積によって表すことができました。


たとえば、 m = 2016 としてみると

 2016 = 2^5 \times 3^2 \times 7

と素因数分解されるので

 (\mathbb{Z}/2016\mathbb{Z})^\times \; \simeq \;  \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/8\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z}

のように巡回群の直積で表せました。それぞれ、位数が  2, 8, 6, 6 となっています。


話をカーマイケルの定理に戻すと、それぞれの巡回群の位数を掛け合わせると

 \#(\mathbb{Z}/m\mathbb{Z})^\times = \varphi(m)

になるわけですが、これではオイラーの定理と同じになってしまいますね。実際

 2\times 8\times 6\times 6 = 576 = \varphi(2016)

となって一致します。でも、これでは大きすぎるというわけです。


ここで掛け合わせずに、それぞれの巡回群の位数の 最小公倍数(LCM) を取ってあげましょう。これでも、すべての生成元が単位元に戻ることがわかります。すなわち「分解された巡回群のそれぞれの位数の最小公倍数」だけべき乗すると、すべての元が単位元になってしまうのです。

これこそがカーマイケルの定理における数論的関数  \lambda(m) の正体だったわけですね。


先ほどの具体例をもう一度持ち出すと

 (\mathbb{Z}/2016\mathbb{Z})^\times \; \simeq \;  \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/8\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z}

における右辺の巡回群の位数はそれぞれ  2, 8, 6, 6 ですから

 \lambda(2016) = \text{LCM}(2, 8, 6, 6) = 24

したがって、 (\mathbb{Z}/2016\mathbb{Z})^\times の任意の元は  24 乗すると、単位元になることがわかりました(ほんまかいな)。

カーマイケル数

ようやく カーマイケル数 の話です。

フェルマーの小定理を使った素数判定法の1つで「フェルマーテスト」という手法があります。

フェルマーテスト
 m と互いに素な整数  a を1つ選び,その  m-1 乗を計算する.それが  \mod{m} において  1 に合同であるかどうか,すなわち
 a^{m-1} \equiv 1 \pmod{m}

を満たすかどうか,を判定するテストのことをフェルマーテストという.

 m が素数であれば、 m と互いに素な任意の  a に対して、 m はフェルマーテストを通ります。合成数でも、 a によってはフェルマーテストを通るかもしれません。しかし、いくつかの異なる  a を試せば、必ずしも1にならないことは分かるでしょう。

一般に、フェルマーテストで試す  a の個数が増えれば、合成数を素数と誤判定する確率は下がります。このように、確率的に素数かどうか判定する方法を「確率的素数判定法」といいます。フェルマーテストは確率的素数判定法の1つです。


ところが、どんな  a に対してもフェルマーテストを通ってしまうような、タチの悪い合成数が存在します。このような「偽物の素数」のことを「カーマイケル数」といいます。

 561 という数は、どんな  m に互いに素な  a をもってきても、フェルマーテストを通ってしまいます。つまり、 561 はカーマイケル数です。


 561 がカーマイケル数であることを、カーマイケルの定理を用いて示すことができます。やってみましょう。

 561 = 3\times 11 \times 17

のように素因数分解されるので、中国剰余定理より

 (\mathbb{Z}/561\mathbb{Z})^\times \; \simeq \; (\mathbb{Z}/3^{1}\mathbb{Z})^\times \times (\mathbb{Z}/11^{1}\mathbb{Z})^\times \times (\mathbb{Z}/17^{1}\mathbb{Z})^\times

という同型が得られる。それぞれの群は

 (\mathbb{Z}/3^{1}\mathbb{Z})^\times 3^{1-1}\cdot (3-1) = 2 次の巡回群
 (\mathbb{Z}/11^{1}\mathbb{Z})^\times 11^{1-1}\cdot (11-1) = 10 次の巡回群
 (\mathbb{Z}/17^{1}\mathbb{Z})^\times 17^{1-1}\cdot (17-1) = 16 次の巡回群

となるので、よって  \text{LCM}(2, 10, 16) = 80 より、 \lambda(561) = 80 となる。


したがってカーマイケルの定理により、 561 と互いに素な  a に対して

 a^{80} \equiv 1 \pmod{561}

が成り立ちます。


よって

 a^{561-1} = \left(a^{80}\right)^{7} \equiv 1 \pmod{561}

のように式変形できる。

すなわち、 561 は自分自身と互いに素なすべての  a に対してフェルマーテストを通過する、カーマイケル数であることが示せました。


一般に  \lambda(m) m-1 を割り切るとき、 m がカーマイケル数となります。


最後に、カーマイケル数を小さい順にいくつか列挙してみましょう。 m-1 \lambda(m) で割りきれることを確認してみてください。

 m (\mathbb{Z}/m\mathbb{Z})^{\times} \lambda(m) m-1
 561 = 3^{1}\cdot 11^{1} \cdot 17^{1} \simeq \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/10\mathbb{Z} \times \mathbb{Z}/16\mathbb{Z} 80 560
 1105 = 5^{1}\cdot 13^{1} \cdot 17^{1} \simeq \mathbb{Z}/4\mathbb{Z}\times \mathbb{Z}/12\mathbb{Z} \times \mathbb{Z}/16\mathbb{Z} 48 1104
 1729 = 7^{1}\cdot 13^{1} \cdot 19^{1} \simeq \mathbb{Z}/6\mathbb{Z}\times \mathbb{Z}/12\mathbb{Z} \times \mathbb{Z}/18\mathbb{Z} 36 1728
 2465 = 5^{1}\cdot 17^{1} \cdot 29^{1} \simeq \mathbb{Z}/4\mathbb{Z}\times \mathbb{Z}/16\mathbb{Z} \times \mathbb{Z}/28\mathbb{Z} 112 2464
 2821 = 7^{1}\cdot 13^{1} \cdot 31^{1} \simeq \mathbb{Z}/6\mathbb{Z}\times \mathbb{Z}/12\mathbb{Z} \times \mathbb{Z}/30\mathbb{Z} 60 2820
 6601 = 7^{1}\cdot 23^{1} \cdot 41^{1} \simeq \mathbb{Z}/6\mathbb{Z}\times \mathbb{Z}/22\mathbb{Z} \times \mathbb{Z}/40\mathbb{Z} 1320 6600
 8911 = 7^{1}\cdot 19^{1} \cdot 67^{1} \simeq \mathbb{Z}/6\mathbb{Z}\times \mathbb{Z}/18\mathbb{Z} \times \mathbb{Z}/66\mathbb{Z} 198 8910
 10585 = 5^{1}\cdot 29^{1} \cdot 73^{1} \simeq \mathbb{Z}/4\mathbb{Z}\times \mathbb{Z}/28\mathbb{Z} \times \mathbb{Z}/72\mathbb{Z} 504 10584
 15841 = 7^{1}\cdot 31^{1} \cdot 73^{1} \simeq \mathbb{Z}/6\mathbb{Z}\times \mathbb{Z}/30\mathbb{Z} \times \mathbb{Z}/72\mathbb{Z} 360 15840
 29341 = 13^{1}\cdot 37^{1} \cdot 61^{1} \simeq \mathbb{Z}/12\mathbb{Z}\times \mathbb{Z}/36\mathbb{Z} \times \mathbb{Z}/60\mathbb{Z} 180 29340
 41041 = 7^{1}\cdot 11^{1} \cdot 13^{1} \cdot 41^{1} \simeq \mathbb{Z}/6\mathbb{Z}\times \mathbb{Z}/10\mathbb{Z} \times \mathbb{Z}/12\mathbb{Z} \times \mathbb{Z}/40\mathbb{Z} 120 41040
 46657 = 13^{1}\cdot 37^{1} \cdot 97^{1} \simeq \mathbb{Z}/12\mathbb{Z}\times \mathbb{Z}/36\mathbb{Z} \times \mathbb{Z}/96\mathbb{Z} 288 46656
 52633 = 7^{1}\cdot 73^{1} \cdot 103^{1} \simeq \mathbb{Z}/6\mathbb{Z}\times \mathbb{Z}/72\mathbb{Z} \times \mathbb{Z}/102\mathbb{Z} 1224 52632
 62745 = 3^{1}\cdot 5^{1} \cdot 47^{1} \cdot 89^{1} \simeq \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/46\mathbb{Z} \times \mathbb{Z}/88\mathbb{Z} 2024 62744

カーマイケル数は、以下のオンライン整数列大辞典(OEIS)から持ってきました。

A002997 - OEIS

上の表を眺めながら、MathWorld におけるカーマイケル数の記事 を読んでみると、いくつか面白いことがわかります。

まず、カーマイケル数は無数にあることが知られているのだとか(予想:R. D. Carmichael (1910),証明:Alford-Granville-Pomerance (1994))。

また、カーマイケル数には判定法があります。

 m = (6k+1)(12k+1)(18k+1)

となっていて、それぞれの因子がすべて素数になっているときは、 m はカーマイケル数になるのだそうです(証明:Korselt (1899), Ore (1988), Guy (1994))。

実際  k = 1 のとき

 1729 = (6+1)(12+1)(18+1) = 7 \cdot 13 \cdot 19

となって、 7, \; 13, \; 19 はすべて素数ですね。

残念ながら、すべてのカーマイケル数がこの形式に該当するわけではないようなので、列挙には向かないのですが。


参考までに、カーマイケル自身の 1910 年の論文は以下でみることができます。MathWorld の記事によると、この論文で 15 個のカーマイケル数が例示されているそうなのですが、私にはよくわかりませんでした。読み解けた方がいましたら教えてください。
projecteuclid.org


おわりに

今日は巷で話題の「カーマイケル数」について、特に「カーマイケルの定理」と「 (\mathbb{Z}/m\mathbb{Z})^{\times} の群構造」の観点でご紹介しました。

前回の記事もそうだったのですが「群の構造」から「数論的な問題の解」が導けるのって、なんとも面白いですよね!

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

追記:こんな動画みつけました

「カーマイケル数とは何か?」が簡単にまとまっている動画です。難しい概念はほとんど出てこないので、初学者にはこちらがわかりやすそう。

www.nicovideo.jp