Carmichael数

前提知識: Fermatの小定理, 合同式, 中国剰余定理, 原始根

Fermatの小定理 によると、$p$ が素数で $a$ が $p$ で割り切れなければ $a^{p-1}\equiv1\pmod p$ である。これを逆に使えば、$a^{n-1}\not\equiv1\pmod n$ となる $a$ を 1 つ見せるだけで、$n$ が合成数であることが分かる。ところが $561=3\cdot11\cdot17$ は合成数なのに、$561$ と互いに素などの整数 $a$ についても $a^{560}\equiv1\pmod{561}$ となり、このやり方ではいつまでも合成数だと見抜けない。このような合成数を Carmichael数 という。
Carmichael 数かどうかは、何百もの $a$ を試さなくても、素因数分解だけで判定できる。$n$ が平方因子をもたず、$n$ を割る各素数 $p$ について $p-1$ が $n-1$ を割ること、これが必要十分である（Korselt の判定法）。$561$ なら $2,10,16$ がどれも $560$ を割る。この記事では Carmichael 数を定義し、Korselt の判定法を証明し、そこから「奇数である」「相異なる素因数を 3 個以上もつ」「どの素因数も $\sqrt n$ より小さい」などの性質と、Carmichael 数を作る Chernick の構成を導く。Carmichael 数が無限個あること（Alford–Granville–Pomerance）は、この記事では証明しないが、所在を示して述べる。

定義

素数 $p$ は、Fermat の小定理により $p$ と互いに素なすべての $a$ で $a^{p-1}\equiv1\pmod p$ を満たすので、定義で「合成数」を仮定しないと素数がすべて含まれてしまう。$1$ は素数でも合成数でもないので Carmichael 数ではない。
1 つの底 $a$ について「$\gcd(a,n)=1$ かつ $a^{n-1}\equiv1\pmod n$」を満たす合成数 $n$ を、底 $a$ の 擬素数（Fermat 擬素数、擬素数）という。Carmichael 数は、$n$ と互いに素な すべての 底について擬素数である合成数であり、絶対擬素数（absolute pseudoprime）とも呼ばれる。
文献によって定義の形が 2 通りある。

• Ste17 §2.4（p. 37）は本記事と同じく「$\gcd(a,n)=1$ なるすべての $a$ で $a^{n-1}\equiv1\pmod n$ となる合成数」とする。
• Cri24 Definition 12.2.9（p. 192）は「すべての整数 $a$ で $a^n\equiv a\pmod n$ となる合成数」とする（$a$ に $n$ と互いに素という条件を付けない）。
  2 つの定義は同値である（prop-cmn-all-integers）。Sho08 §10.2（p. 308）は奇数の合成数に限って定義しているが、Carmichael 数はもともとすべて奇数なので（prop-cmn-odd）、これも同じものを定める。

直感

$n=p_1p_2\cdots p_k$ を相異なる素数の積とすると、中国剰余定理により、$a^{n-1}\equiv1\pmod n$ は「各 $i$ で $a^{n-1}\equiv1\pmod{p_i}$」と同じことである。法 $p_i$ では、$a$ を何乗すれば $1$ に戻るかは $p_i-1$ の約数で決まり、すべての $a$ について $1$ に戻る最小の指数はちょうど $p_i-1$ である（法 $p_i$ の 原始根 がそれを実現する）。したがって「すべての $a$ で $a^{n-1}\equiv1$」は「指数 $n-1$ が各 $p_i-1$ の倍数」と言い換えられる。Carmichael 数とは、素因数 $p_i$ の「周期」$p_i-1$ がそろって $n-1$ を割るように、素因数がうまく組み合わさった合成数である。平方因子 $p^2$ があると、法 $p^2$ の周期 $p(p-1)$ が $p$ で割り切れ、$n-1$（$p$ で割り切れない）の約数になりえないので、Carmichael 数にはなれない。

例と反例

一方、$a=3$ は $561$ と互いに素でないので定義の対象外であり、実際 $3^{560}\equiv375\not\equiv1\pmod{561}$ である（計算機で確かめた値）。$3$ で割り切れる数の冪は $3$ で割り切れるので、$1$ と合同になりえない。

次の表は、Carmichael 数の定義と Korselt の判定法から条件を 1 つずつ外したときの反例である。

最後の行は反例というより定理の言い換えで、相異なる 2 素数の積は決して Carmichael 数にならない。5 行目は、定義の「$n$ と互いに素な」を落とした形「すべての $a$ で $a^{n-1}\equiv1\pmod n$」は、どの合成数も満たさないことを示している。$n$ の素因数 $p$ を $a$ にとれば $a^{n-1}$ は $p$ で割り切れ、$1$ と合同にならないからである。互いに素でない $a$ まで含めるなら、prop-cmn-all-integers のように $a^n\equiv a$ の形にする必要がある。

性質

Korselt の判定法

最初に、偶数が Carmichael 数になりえないことを示す。これは判定法の証明で素因数 $2$ を除くのに使う。

証明の 1 ⇒ 2 で使ったのは、$n$ と互いに素な底のうち、法 $p^e$ で原始根に、ほかの素因数の法で $1$ になる 1 つの底 $b$ だけである。つまり Carmichael 数でない奇数の合成数 $n$ については、Korselt の条件を破る素因数 $p$（$p^2\mid n$ となるもの、または $p-1\nmid n-1$ となるもの）について同じ構成をすれば、「$\gcd(b,n)=1$ かつ $b^{n-1}\not\equiv1\pmod n$」となる $b$ を具体的に作れる（偶数の合成数 $n$ では、prf-cmn-odd のとおり $b=n-1$ がその役をする）。$n=9$ なら法 $9$ の原始根 $2$ がそれであり（ex-cmn-prime-square）、$n=105$ なら法 $7$ の原始根 $3$ を使って $b\equiv3\pmod7$、$b\equiv1\pmod{15}$ から $b=31$ をとると、$31^{104}\equiv31^{104\bmod 6}=31^2\equiv3^2\equiv2\pmod 7$ なので $31^{104}\not\equiv1\pmod{105}$ である。
既約剰余類群 の言葉では、既約剰余類群 の記事の命題「Carmichael 関数による判定」により、合成数 $n$ が Carmichael 数であることは $\lambda(n)\mid n-1$ と同値である。ここで $\lambda(n)$ は $n$ と互いに素なすべての $a$ で $a^{m}\equiv1\pmod n$ となる最小の正の整数 $m$（Carmichael 関数）である。同じ記事の系「Carmichael 関数の公式」により、平方因子のない奇数 $n=p_1\cdots p_k$ では $\lambda(n)=\operatorname{lcm}(p_1-1,\dots,p_k-1)$ なので、Korselt の条件は「$\operatorname{lcm}(p_1-1,\dots,p_k-1)\mid n-1$」とも書ける。$561$ では $\lambda(561)=\operatorname{lcm}(2,10,16)=80$ で、$560=7\cdot80$ である。

素因数についての制約

Korselt の判定法から、Carmichael 数の素因数の並び方にいくつもの制約が出てくる。

$561=3\cdot11\cdot17$ では、1 の $m$ は $187,51,33$ で、それぞれ $187\equiv1\pmod2$、$51\equiv1\pmod{10}$、$33\equiv1\pmod{16}$ であり、最大の素因数 $17$ は $\sqrt{561}=23.6\ldots$ より小さい。3 については $\varphi(561)=2\cdot10\cdot16=320$ で $\gcd(561,320)=1$ である。3 から、たとえば $3$ で割り切れる Carmichael 数のほかの素因数 $q$ は $3\nmid q-1$、すなわち $q\equiv2\pmod3$ を満たす（$561$ の $11,17$）。同じ理由で、$n$ の素因数に $p$ と $2p+1$、$p$ と $2kp+1$ の形の組が同時に現れることはない。
2 は「2 素数の積 $pq$ は Carmichael 数でない」ことを言っている。$341=11\cdot31$ が底 $2$ の擬素数でありながら Carmichael 数になれなかったのは、この一般的な理由による（$31-1=30$ は $340$ を割らない）。

同値な言い換え

2 ⇒ 1 は Korselt の判定法を使わない。1 ⇒ 2 の向きでは、$n$ の素因数 $p$ で割り切れる $a$ についても $a^n\equiv a\pmod p$（両辺とも $0$）となることを、平方因子がないことを使って $\pmod n$ に集めている。平方因子があると、たとえば $n=9$、$a=3$ で $3^9\equiv0\not\equiv3\pmod9$ となり、2 は成り立たない。

Chernick の構成

Korselt の判定法を使うと、素数の組から Carmichael 数を作れる。

$k=1$ で $7\cdot13\cdot19=1729$、$k=6$ で $37\cdot73\cdot109=294409$、$k=35$ で $211\cdot421\cdot631=56052361$ が得られる（$k\le200$ で条件を満たす $k$ は $1,6,35,45,51,55,56,100,\dots$。計算機で確かめた）。この構成は Chernick（1939）による（AGP94 p. 704）。$6k+1,12k+1,18k+1$ が同時に素数になる $k$ は、素数の組についての Hardy–Littlewood の予想によれば無限にあるはずだが（同頁）、これは証明されておらず、この構成から Carmichael 数の無限性は出てこない。

素数判定との関係

Carmichael 数は、「$a^{n-1}\not\equiv1\pmod n$ となる $a$ を探して合成数を見抜く」方法（Fermat テスト）が原理的に失敗する合成数である。$n$ の素因数と互いに素でない $a$ を引き当てれば合成数だと分かるが、それは $n$ の素因数を見つけることと同じくらい難しい。そこで実際の素数判定では、Fermat の小定理をもう一段細かくした判定が使われる。
$n$ が奇素数なら、$x^2\equiv1\pmod n$ の解は $x\equiv\pm1$ だけである（$n\mid(x-1)(x+1)$ から $n$ は $x-1$ か $x+1$ を割る）。したがって、$n-1=2^st$（$t$ は奇数）と書き、$a^t,a^{2t},a^{4t},\dots,a^{2^st}=a^{n-1}$ を法 $n$ で順に計算したとき、$\pm1$ 以外の数の 2 乗が $1$ になる箇所が現れたら、$n$ は合成数である。$n=561$、$a=2$ では $560=2^4\cdot35$ で
$$ 2^{35}\equiv263,\quad 263^2\equiv166,\quad 166^2\equiv67,\quad 67^2\equiv1\pmod{561} $$
となり（$67^2=4489=8\cdot561+1$）、$67\not\equiv\pm1$ の 2 乗が $1$ なので $561$ は合成数だと分かる。さらに $561\mid(67-1)(67+1)$ で $561$ はどちらの因数も割らないので、$\gcd(66,561)=33$、$\gcd(68,561)=17$ から $561$ の約数が得られる。
この判定（Miller の判定、Miller–Rabin 法）については、奇数の合成数 $n$ は $1\le a\le n-1$ のうち高々 $(n-1)/4$ 個の底でしか判定を通過しないことが知られている（Cri24 Theorem 12.4.6、p. 197。この記事では証明しない）。つまり Fermat テストにとっての Carmichael 数にあたる「すべての底を通過する合成数」は、この判定には存在しない。

無限性と分布

$x$ 以下の Carmichael 数の個数を $C(x)$ と書く。上の計算では $C(10^3)=1$、$C(10^4)=7$、$C(10^5)=16$、$C(10^6)=43$ である。Pinch の計算によれば $C(10^{12})=8241$、$C(10^{15})=105212$ である（AGP94 p. 704）。

この定理はこの記事では証明しない（AGP94 Theorem 1 と直後の注意、p. 705）。証明の筋は次のとおりである（同論文 p. 706）。ある整数 $L$ について、$p-1\mid L$ となる素数 $p$ を非常に多く用意する。そのうちいくつかの積 $C=p_1\cdots p_k$ が $C\equiv1\pmod L$ を満たせば、各 $p_j-1$ が $L$ を割り、$L$ が $C-1$ を割るので、Korselt の判定法により $C$ は Carmichael 数である。そのような積の存在は、有限アーベル群 $(\mathbb Z/L\mathbb Z)^\times$ の元の長い列には積が単位元になる空でない部分列がある、という群論の定理（同論文 Theorem 2）で保証する。$L$ をうまく選ぶために、$q-1$ の素因数がどれも小さい素数 $q$ の個数や、等差数列の中の素数の個数についての評価を使う（pp. 704–706）。
一方、Carmichael 数は整数の中では非常にまれで、$C(x)\le x^{1-\{1+o(1)\}\log\log\log x/\log\log x}$（$x\to\infty$）という上からの評価が知られている（同論文 p. 704 に文献とともに挙げられている）。

補足

関連項目

• 前提: Fermatの小定理, 中国剰余定理, 原始根, 合成数
• 比較: 擬素数, Carmichael関数, 既約剰余類群
• 直後に読む: Miller–Rabin素数判定法, 素数判定法
• 発展: 素数定理, Eulerの定理(整数論)